【图】遍历图DFS,BFS 列出连通集

一、题目 给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

输入格式 输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

输出格式 按照"{ v1 v2…vk }"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。

输入样例

8 6 0 7 0 1 2 0 4 1 2 4 3 5

输出样例

{ 0 1 4 2 7 } { 3 5 } { 6 } { 0 1 2 7 4 } { 3 5 } { 6 }

二。思路

1. 根据输入信息建立图的邻接表
2. 分别DFS，BFS遍历 （图的DFS和BFS：）
3. 其中DFS时，每次都要找该与顶点有关的最小的边节点信息。BFS时要对该顶点的边表节点里存储的下标进行从小到大排序，排好序然后再依次入队。
4. 图并不是全部连通，要找到一些没有被访问到的顶点，然后依次对这些进行访问。

三、代码 代码中的p->next所对应的下标就等于G->adjlist[p->next].data。DFS遍历时用的是后面那种麻烦的表达，BFS时嫌麻烦用的是前者。但是数值都一样，用哪种表达都不影响。

#include<iostream>
#include<algorithm>
#include<string.h>
#define maxsize 10
using namespace std;
int visit[maxsize];
typedef struct ArcNode //边表，存放边信息
{
          
   
	int index;
	struct ArcNode *next;
}ArcNode;
typedef struct VNode {
          
   
	int data;
	ArcNode *firstarc;
}VNode;
typedef struct AGraph {
          
   
	VNode adjlist[maxsize];
	int n, e;
}AGraph;
void DFS(AGraph *G, int v) {
          
   
	cout << " " << G->adjlist[v].data;
	visit[v] = 1;
	ArcNode *p,*q;
	p = G->adjlist[v].firstarc;
	while (p != NULL) {
          
   
		int min = G->adjlist[p->index].data;
		q = p;
		int flag = 0;
		while (q != NULL) {
          
   
			if (min > G->adjlist[q->index].data
				&& visit[q->index] == 0)
			{
          
   
				min = G->adjlist[q->index].data;
				flag = 1;
			}
			q = q->next;
		}
		if(visit[min]==0)
		DFS(G, min);
		if(flag==0)
		p = p->next;
	}
}
void BFS(AGraph *G, int v) {
          
   
	ArcNode *p,*q;
	int que[maxsize]; 
	int front = -1, rear = -1;
	visit[v] = 1;
	int j;
	rear = (rear + 1) % maxsize;
	que[rear] = v;
	while (front != rear) {
          
   
		front = (front + 1) % maxsize;
		j = que[front];
		cout << " " << G->adjlist[j].data;
		p = G->adjlist[j].firstarc;
		q = p;
		int arry[maxsize]; int k = 0;
		while (q != NULL) {
          
   
			if (visit[q->index] == 0)
			{
          
   
				arry[k++] = q->index;
				visit[q->index] = 1;
			}
			q = q->next;
		}
		sort(arry, arry + k);
		for (int n = 0; n < k; n++) {
          
   
			rear = (rear + 1) % maxsize;
			que[rear] = arry[n];
		}
	}
}
void initial(AGraph *&g) {
          
   
	for (int i = 0; i < maxsize; i++) {
          
   
		g->adjlist[i].firstarc = NULL;
		g->adjlist[i].data = i;
	}
}
int main() {
          
   
	memset(visit, 0, sizeof(visit));
	int N, E;
	int a[3];
	cin >> N >> E;
	AGraph *g;
	g = (AGraph*)malloc(sizeof(AGraph));
	initial(g);
	g->n = N;
	g->e = E;
	for (int i = 0; i < E; i++) {
          
   
		cin >> a[0] >> a[1];
		for (int j = 0; j < 2; j++) {
          
   
			ArcNode *p, *q;
			p = (ArcNode*)malloc(sizeof(ArcNode));
			p->index = a[(j+1)%2];
			p->next = NULL;
			if (g->adjlist[a[j]].firstarc == NULL)
			{
          
   
				g->adjlist[a[j]].firstarc = p; continue;
			}
			q = g->adjlist[a[j]].firstarc;
			while (q->next != NULL) {
          
    q = q->next; }
			q->next = p;
		}
	}
	for (int i = 0; i < N; i++) {
          
   
		if (visit[i] == 0)
		{
          
   
			cout << "{";
			DFS(g, i);
			cout << " }" << endl;
		}
	}
	memset(visit, 0, sizeof(visit));
	for (int i = 0; i < N; i++) {
          
   
		if (visit[i] == 0) {
          
   
			cout << "{";
			BFS(g, i);
			cout << " }" << endl;
		}
	}
	return 0;
}