浙大陈越何钦铭数据结构06-图1 列出连通集

题目

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

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

输出格式:
按照"{ v
1
​
v
2
​
… v
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 <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_VERTEX_NUM 10
#define ELEMENT_TYPE int
#define ERROR -1
#define QUEUE_SIZE 10typedef int Vertex;struct _Queue
{ELEMENT_TYPE *data;int front, rear;int size;
};
typedef struct _Queue *Queue;struct _Edge
{int v, w;
};
typedef struct _Edge *Edge;struct _MGraph
{int nv, ne;int graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
};
typedef struct _MGraph *MGraph;Queue createQueue(ELEMENT_TYPE size);
bool isFull(Queue q);
bool isEmpty(Queue q);
bool addQ(Queue q, ELEMENT_TYPE x);
ELEMENT_TYPE delQ(Queue q);void initVisited(bool visited[]);
bool isEdge(MGraph g, Vertex v, Vertex w);
MGraph createGraph(int numVertices);
void insertEdge(MGraph g, Edge e);
MGraph buildGraph();
void dfs(MGraph g, Vertex v);
void bfs(MGraph g, Vertex s);
void listComponentsViaDFS(MGraph g);
void listComponentsViaBFS(MGraph g);bool visited[MAX_VERTEX_NUM] = {false};/*
06-图1 列出连通集难度：1星
重要度：3星，必须掌握的2种图的遍历方式。无向图，用0,1表示顶点间是否有边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 }*/
int main()
{MGraph g = buildGraph();listComponentsViaDFS(g);initVisited(visited);listComponentsViaBFS(g);free(g);return 0;
}// 初始化Visited数组，将所有顶点的访问状态初始化为false
void initVisited(bool visited[])
{Vertex v;for (v = 0; v < MAX_VERTEX_NUM; v++)visited[v] = false;
}bool isEdge(MGraph g, Vertex v, Vertex w)
{return g->graph[v][w] == 1;
}MGraph createGraph(int numVertices)
{MGraph g = (MGraph)malloc(sizeof(struct _MGraph));g->nv = numVertices;g->ne = 0;Vertex v, w;for (v = 0; v < g->nv; v++)for (w = 0; w < g->nv; w++)g->graph[v][w] = 0; // 初始化为0，表示无边return g;
}void insertEdge(MGraph g, Edge e)
{ //(V,W)之间双向置为1，表示无向有边g->graph[e->v][e->w] = 1;g->graph[e->w][e->v] = 1;
}MGraph buildGraph()
{MGraph g;Edge e;Vertex v;int nv, ne;scanf("%d %d", &nv, &ne);g = createGraph(nv);if (ne){g->ne = ne;e = (Edge)malloc(sizeof(struct _Edge));for (v = 0; v < g->ne; v++){scanf("%d %d", &e->v, &e->w);insertEdge(g, e);}free(e);}return g;
}void dfs(MGraph g, Vertex v)
{visited[v] = true;printf("%d ", v);Vertex w;for (w = 0; w < g->nv; w++){if (!visited[w] && isEdge(g, v, w)){dfs(g, w);}}
}// 使用深度优先搜索列出连通集
void listComponentsViaDFS(MGraph g)
{Vertex v;for (v = 0; v < g->nv; v++){if (!visited[v]){printf("{ ");dfs(g, v);printf("}\n");}}
}// 广度优先搜索
void bfs(MGraph g, Vertex s)
{Vertex v, w;Queue q = createQueue(g->nv);printf("%d ", s);visited[s] = true;addQ(q, s);while (!isEmpty(q)){v = delQ(q);for (w = 0; w < g->nv; w++){if (!visited[w] && isEdge(g, v, w)){printf("%d ", w);visited[w] = true;addQ(q, w);}}}free(q->data);free(q);
}// 使用广度优先搜索列出连通集
void listComponentsViaBFS(MGraph g)
{Vertex v;for (v = 0; v < g->nv; v++){if (!visited[v]){printf("{ ");bfs(g, v);printf("}\n");}}
}// 创建队列，Size为队列的最大容量
Queue createQueue(ELEMENT_TYPE size)
{Queue q = (Queue)malloc(sizeof(struct _Queue));q->data = (ELEMENT_TYPE *)malloc(size * sizeof(ELEMENT_TYPE));q->front = q->rear = 0;q->size = QUEUE_SIZE;return q;
}// 判断队列是否已满
bool isFull(Queue q)
{return (q->rear + 1) % q->size == q->front;
}// 判断队列是否为空
bool isEmpty(Queue q)
{return q->front == q->rear;
}// 入队操作
bool addQ(Queue q, ELEMENT_TYPE x)
{if (isFull(q)){printf("Full.\n");return false;}else{q->rear = (q->rear + 1) % q->size; // 队尾索引加1，并考虑循环的情况q->data[q->rear] = x;              // 将X存入队尾位置return true;}
}// 出队操作
ELEMENT_TYPE delQ(Queue q)
{if (isEmpty(q)){printf("Empty.\n");return ERROR;}else{q->front = (q->front + 1) % q->size; // 队头索引加1，并考虑循环的情况return q->data[q->front];            // 返回队头元素}
}

执行结果

小结

基础的对图的两种方式的遍历，需要熟练掌握。