用c语言针对给定的无向图,实现图的深度优先遍历和广度优先遍历算法,并输出相应遍历的结果
时间: 2023-07-16 09:15:24 浏览: 132
无向图建立、深度优先遍历和广度优先遍历实现算法[借鉴].pdf
5星 · 资源好评率100%
下面是针对给定的无向图实现图的深度优先遍历和广度优先遍历算法的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
typedef struct Graph {
int numVertices; // 图中顶点的个数
int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵,表示任意两个顶点之间是否有连接
} Graph;
void initGraph(Graph *g, int numVertices) {
g->numVertices = numVertices;
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
g->adjMatrix[i][j] = 0;
}
}
}
void addEdge(Graph *g, int src, int dest) {
g->adjMatrix[src][dest] = 1;
g->adjMatrix[dest][src] = 1;
}
void depthFirstTraversal(Graph *g, int v, int visited[]) {
visited[v] = 1;
printf("%d ", v);
for (int i = 0; i < g->numVertices; i++) {
if (g->adjMatrix[v][i] == 1 && visited[i] == 0) {
depthFirstTraversal(g, i, visited);
}
}
}
void depthFirstSearch(Graph *g, int start) {
int visited[MAX_VERTICES] = {0};
depthFirstTraversal(g, start, visited);
}
void breadthFirstSearch(Graph *g, int start) {
int visited[MAX_VERTICES] = {0};
int queue[MAX_VERTICES];
int front = -1;
int rear = -1;
visited[start] = 1;
queue[++rear] = start;
while (front != rear) {
int v = queue[++front];
printf("%d ", v);
for (int i = 0; i < g->numVertices; i++) {
if (g->adjMatrix[v][i] == 1 && visited[i] == 0) {
visited[i] = 1;
queue[++rear] = i;
}
}
}
}
int main() {
Graph g;
initGraph(&g, 6); // 图中有6个顶点
addEdge(&g, 0, 1);
addEdge(&g, 0, 2);
addEdge(&g, 1, 3);
addEdge(&g, 1, 4);
addEdge(&g, 2, 4);
addEdge(&g, 3, 4);
addEdge(&g, 3, 5);
addEdge(&g, 4, 5);
printf("Depth First Search: ");
depthFirstSearch(&g, 0);
printf("\nBreadth First Search: ");
breadthFirstSearch(&g, 0);
return 0;
}
```
以上代码中,我们首先定义了一个结构体 `Graph`,用于存储图的信息。其中,`numVertices` 表示图中顶点的个数,`adjMatrix` 表示任意两个顶点之间是否有连接。接着,我们实现了以下函数:
- `initGraph()`:用于初始化图,将邻接矩阵中的所有元素都设置为0。
- `addEdge()`:用于在两个顶点之间添加一条边。
- `depthFirstTraversal()`:用于深度优先遍历图。其中,`visited` 数组用于记录每个顶点是否被访问过。
- `depthFirstSearch()`:用于深度优先搜索图。它调用 `depthFirstTraversal()` 函数遍历整个图。
- `breadthFirstSearch()`:用于广度优先搜索图。它使用一个队列来存储待访问的顶点。
在 `main()` 函数中,我们创建了一个具有6个顶点的图,并向其中添加了一些边。接着,我们分别调用 `depthFirstSearch()` 和 `breadthFirstSearch()` 函数进行深度优先搜索和广度优先搜索。最后,输出它们的搜索结果。
阅读全文