请用C语言代码编写程序按邻接矩阵的方法创建图,并分别用深度优先和广度优先两种方法遍历这张图。
时间: 2024-02-22 21:59:15 浏览: 78
建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历.doc
5星 · 资源好评率100%
好的,我来为您编写按邻接矩阵的方法创建图,并分别用深度优先和广度优先两种方法遍历这张图的代码,如下所示:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
typedef struct {
int vertices[MAX_VERTICES][MAX_VERTICES];
int numVertices;
} Graph;
void initGraph(Graph *graph, int numVertices) {
graph->numVertices = numVertices;
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
graph->vertices[i][j] = 0;
}
}
}
void addEdge(Graph *graph, int u, int v) {
if (u < 0 || u >= graph->numVertices || v < 0 || v >= graph->numVertices) {
printf("Error: Invalid vertex index!\n");
exit(-1);
}
graph->vertices[u][v] = 1;
graph->vertices[v][u] = 1;
}
void dfs(Graph *graph, int v, int visited[]) {
visited[v] = 1;
printf("%d ", v);
for (int i = 0; i < graph->numVertices; i++) {
if (graph->vertices[v][i] && !visited[i]) {
dfs(graph, i, visited);
}
}
}
void bfs(Graph *graph, int v, int visited[]) {
int queue[MAX_VERTICES];
int front = 0, rear = 0;
visited[v] = 1;
printf("%d ", v);
queue[rear++] = v;
while (front != rear) {
int u = queue[front++];
for (int i = 0; i < graph->numVertices; i++) {
if (graph->vertices[u][i] && !visited[i]) {
visited[i] = 1;
printf("%d ", i);
queue[rear++] = i;
}
}
}
}
int main() {
int numVertices, numEdges;
printf("Enter the number of vertices: ");
scanf("%d", &numVertices);
Graph graph;
initGraph(&graph, numVertices);
printf("Enter the number of edges: ");
scanf("%d", &numEdges);
for (int i = 0; i < numEdges; i++) {
int u, v;
printf("Enter edge %d: ", i + 1);
scanf("%d %d", &u, &v);
addEdge(&graph, u, v);
}
int visited[MAX_VERTICES] = {0};
printf("Depth First Traversal: ");
for (int i = 0; i < numVertices; i++) {
if (!visited[i]) {
dfs(&graph, i, visited);
}
}
printf("\n");
for (int i = 0; i < numVertices; i++) {
visited[i] = 0;
}
printf("Breadth First Traversal: ");
for (int i = 0; i < numVertices; i++) {
if (!visited[i]) {
bfs(&graph, i, visited);
}
}
printf("\n");
return 0;
}
```
代码中,我们使用结构体 `Graph` 来表示图,其中 `vertices` 是一个二维数组,表示邻接矩阵,`numVertices` 表示图中顶点的个数。初始化函数 `initGraph` 将邻接矩阵中的所有元素都初始化为 0。`addEdge` 函数用于添加边,将邻接矩阵中对应的元素设为 1。深度优先遍历函数 `dfs` 从给定的顶点 `v` 开始遍历图,将 `visited` 数组中对应的元素设为 1,然后递归地遍历与 `v` 相邻的未被访问过的顶点。广度优先遍历函数 `bfs` 使用队列来存储待访问的顶点,从给定的顶点 `v` 开始遍历图,将 `visited` 数组中对应的元素设为 1,然后将 `v` 加入队列中,循环取出队头元素,并将与其相邻的未被访问过的顶点加入队列中。
在 `main` 函数中,我们首先读入图的顶点个数和边的个数,然后初始化图并添加边。接着使用 `visited` 数组来记录已经访问过的顶点,分别调用深度优先遍历函数 `dfs` 和广度优先遍历函数 `bfs`,对未被访问过的顶点进行遍历。
阅读全文