7-201 列出连通集 (25 分)
给定一个有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 }
结尾无空行
#include<iostream> #include<queue> using namespace std; const int maxn = 15; int G[maxn][maxn], vis[maxn]; int n, k; void dfs(int step) { for(int i = 0; i < n; i++) if(!vis[i] && G[step][i]) { vis[i] = 1; cout << ' ' << i; dfs(i); } } void bfs(int step) { queue<int>q; q.push(step); while(!q.empty()) { int x = q.front(); q.pop(); for(int i = 0; i < n; i++) if(!vis[i] && G[x][i]) { vis[i] = 1; cout << ' ' << i; q.push(i); } } } int main() { cin >> n >> k; //DFS部分 //赋值 for(int i = 0; i < k; i++) { int x, y; cin >> x >> y; G[x][y] = G[y][x] = 1; } //遍历 for(int i = 0; i < n; i++) { if(vis[i] == 0) { vis[i] = 1; cout << "{ " << i; dfs(i); cout << " }\n"; } } //bfs部分 //初始化 memset(vis, 0, sizeof(vis)); for(int i = 0; i < n; i++) { if(vis[i] == 0) { vis[i] = 1; cout << "{ " << i; bfs(i); cout << " }\n"; } } return 0; }
#include <stdio.h> #include <stdlib.h> #define MaxVertexNum 10 int Visited[MaxVertexNum]; int N; typedef int Vertex; /* 用顶点下标表示顶点,为整型 */ /*边的定义*/ typedef struct ENode *Edge; struct ENode{ Vertex V1,V2; }; /*邻接点的定义*/ typedef struct AdjNode *PtrToAdjNode; struct AdjNode{ Vertex AdjV; PtrToAdjNode Next; }; /*邻接表头结点定义*/ typedef struct VNode{ PtrToAdjNode FirstEdge; }AdjList[MaxVertexNum]; /*图结点的定义*/ typedef struct GNode *LGraph; struct GNode{ int Nv,Ne; AdjList G; }; typedef struct QueueNode *Queue; struct QueueNode{ int Front,Rear; Vertex *Elements; }; LGraph CreatGraph(int VexterNum); void InsertEdge(LGraph Graph,Edge E); LGraph BuildGraph(); void DFS(LGraph Graph,Vertex V,void (*Visit)(Vertex)); void BFS(LGraph Graph,Vertex S,void (*Visit)(Vertex)); Queue CreatQuene(int MaxSize); void AddQ(Queue Q,Vertex V); Vertex DeleteQ(Queue Q); int IsEmpty(Queue Q); void Visit(Vertex V); int main() { Vertex V; LGraph Graph = BuildGraph(); for(V=0;V<MaxVertexNum;V++) Visited[V] = 0; for(V=0;V<N;V++) { if(!Visited[V]) { printf("{ "); DFS(Graph,V,Visit); printf("}\n"); } } for(V=0;V<MaxVertexNum;V++) Visited[V] = 0; for(V=0;V<N;V++) { if(!Visited[V]) { printf("{ "); BFS(Graph,V,Visit); printf("}\n"); } } return 0; } LGraph CreatGraph(int VexterNum) {/* 初始化一个有VertexNum个顶点但没有边的图 */ LGraph Graph; Graph = (LGraph)malloc(sizeof(struct GNode)); Graph->Ne = 0; Graph->Nv = VexterNum; for(int V=0;V<Graph->Nv;V++) { Graph->G[V].FirstEdge = NULL; } return Graph; } void InsertEdge(LGraph Graph,Edge E) { PtrToAdjNode NewNode,W; /* 插入边 <V1, V2> ,在V1为下标的链表中，插入结点V2,表示v1->v2*/ NewNode = (PtrToAdjNode)malloc(sizeof(struct AdjNode)); NewNode->AdjV = E->V2; /*remark:注意题目要求是按照编号递增的顺序访问邻接点， 所以邻接表插入新结点的时候要注意按照下标从小到大插入； 这部分用邻接矩阵存储的话会比较简便*/ if(!Graph->G[E->V1].FirstEdge) { NewNode->Next = Graph->G[E->V1].FirstEdge; Graph->G[E->V1].FirstEdge = NewNode; } else if(Graph->G[E->V1].FirstEdge&&!Graph->G[E->V1].FirstEdge->Next) { if(NewNode->AdjV < Graph->G[E->V1].FirstEdge->AdjV) { NewNode->Next = Graph->G[E->V1].FirstEdge; Graph->G[E->V1].FirstEdge = NewNode; }else{ NewNode->Next = Graph->G[E->V1].FirstEdge->Next; Graph->G[E->V1].FirstEdge->Next = NewNode; } } else{ for(W = Graph->G[E->V1].FirstEdge;W;W=W->Next) { if(!W->Next||(W->Next->AdjV > NewNode->AdjV)) { NewNode->Next = W->Next; W->Next = NewNode; break; } } } } LGraph BuildGraph() { Edge E1,E2; scanf("%d",&N); LGraph Graph = CreatGraph(N); scanf("%d",&Graph->Ne); E1 = (Edge)malloc(sizeof(struct ENode)); E2 = (Edge)malloc(sizeof(struct ENode)); for(int i=0;i<Graph->Ne;i++) { scanf("%d %d",&E1->V1,&E1->V2); InsertEdge(Graph,E1); E2->V1 = E1->V2; E2->V2 = E1->V1; InsertEdge(Graph,E2); } return Graph; } void Visit(Vertex V) { printf("%d ",V); } void DFS(LGraph Graph,Vertex V,void (*Visit)(Vertex)) { PtrToAdjNode W; Visit(V); Visited[V] = 1; for(W = Graph->G[V].FirstEdge;W;W = W->Next) { if(!Visited[W->AdjV]) DFS(Graph,W->AdjV,Visit); } } void BFS(LGraph Graph,Vertex S,void (*Visit)(Vertex)) { Vertex V; PtrToAdjNode W; Queue Q = CreatQuene(MaxVertexNum); Visit(S); Visited[S] = 1; AddQ(Q,S); while(!IsEmpty(Q)) { V = DeleteQ(Q); for(W = Graph->G[V].FirstEdge;W;W = W->Next) { if(!Visited[W->AdjV]) { Visit(W->AdjV); Visited[W->AdjV] = 1; AddQ(Q,W->AdjV); } } } } Queue CreatQuene(int MaxSize) { Queue Q = (Queue)malloc(sizeof(struct QueueNode)); Q->Elements = (int *)malloc(sizeof(int)*MaxSize); Q->Front = Q->Rear = 0; return Q; } void AddQ(Queue Q,Vertex V) { Q->Elements[Q->Rear++] = V; } Vertex DeleteQ(Queue Q) { return Q->Elements[Q->Front++]; } int IsEmpty(Queue Q) { return Q->Front==Q->Rear; }
