5-6 列出连通集 (25分)

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

输入格式:

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

输出格式:

按照"{ v_1v​1​​ v_2v​2​​ ... v_kv​k​​ }"的格式，每行输出一个连通集。先输出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 }

#include<iostream> #define MAX_VERTEX_NUM 10 using namespace std; //数据结构 typedef struct ArcNode{//依附结点 int adjvex; //弧所指的顶点的位置 struct ArcNode* nextatc;//下一条弧的指针 } ArcNode; typedef struct VNode{//头结点 int seque;//顶点信息 ArcNode *firstarc;//指向第一条弧的指针 }VNode, AdjList[MAX_VERTEX_NUM]; //生成指针 ArcNode*newArc(int node) { ArcNode*tmp = new ArcNode; tmp->adjvex = node; tmp->nextatc = NULL; return tmp; } //插入结点 void insert(VNode &vnode, int node) { if (!vnode.firstarc)//首次插入 vnode.firstarc = newArc(node); else//按序插入 { //插入在头结点和第一个子节点的情况 if (node<vnode.firstarc->adjvex) { ArcNode*tmp = newArc(node); tmp->nextatc = vnode.firstarc; vnode.firstarc = tmp; return; } ArcNode *adj = vnode.firstarc;//判断大小 ArcNode*pre = adj;//前一个指针 while (node > adj->adjvex && adj->nextatc!=NULL)//找到插入位置 { pre = adj; adj = adj->nextatc; } if (adj->adjvex < node)//按从小到大的顺序插入，邻接表 adj->nextatc = newArc(node); else { pre->nextatc = newArc(node); pre->nextatc->nextatc = adj; return; } } } void traverse(const AdjList list, int seq, int*flag) { if (!flag[seq])//判断标志位，0则输出 { cout <<" "<<list[seq].seque;//打印头结点 flag[seq] = 1; if (list[seq].firstarc){//判断第一个子结点是否为0 traverse(list, list[seq].firstarc->adjvex, flag); ArcNode*tmp = list[seq].firstarc; tmp = tmp->nextatc; while (tmp)//子节点的遍历 { traverse(list, tmp->adjvex, flag); tmp = tmp->nextatc; } } } } void DFS(const AdjList list, int num,int*flag) { //深度遍历求连通集 for (int i = 0; i < num; i++) { if (!flag[i])//判断标志位，0则输出 { cout << "{"; traverse(list, i, flag); cout << " }" << endl; } } } void traverseBFS(const AdjList list, int seq, int*flag,int *stack,int &left,int&right) { if (!flag[seq])//判断标志位，0则输出 { cout << " " << list[seq].seque;//打印头结点 flag[seq] = 1; } if (list[seq].firstarc){//判断第一个子结点是否为0 ArcNode*tmp = list[seq].firstarc; while (tmp)//子节点的遍历 { if (!flag[tmp->adjvex])//为打印的子结点入栈 stack[right++] = tmp->adjvex; tmp = tmp->nextatc; } }//if (list[seq].firstarc) while (left != right)//子结点出栈 { traverseBFS(list, stack[left++], flag, stack,left, right); } } void BFS(const AdjList list, int num, int*flag) { //广度遍历，求连通集 int stack[100] = { 0 }; int left = 0,right = 0; for (int i = 0; i < num; i++) { if (!flag[i])//判断标志位，0则输出 { cout << "{"; traverseBFS(list, i, flag,stack,left,right); cout << " }" << endl; } } } int main() { AdjList list; //输入弧 int N, E;//输入顶点数和边数 cin >> N >>E; //构造表头向量并初始化指针 for (int i = 0; i < N; i++) { list[i].seque = i; list[i].firstarc = NULL; } //输入各弧 构造无向图 int fir, sec; for (int i = 0; i < E; i++) { cin >> fir >> sec; insert(list[fir], sec); insert(list[sec], fir); } //深度遍历 int flag[MAX_VERTEX_NUM] = { 0 };//访问标志数组 int flag1[MAX_VERTEX_NUM] = { 0 };//访问标志数组 DFS(list,N, flag); BFS(list, N, flag1); //释放内存 system("pause"); return 0; }

//使用邻接矩阵 更快速，注意不要使用头结点