用c语言对无向图采用邻接矩阵进行存储,完成以下操作 (1) 建立无向图的邻接矩阵存储 (2) 输出邻接矩阵 (3) 基于图邻接矩阵的深度优先遍历 (4) 基于图邻接矩阵的广度优先遍历
时间: 2024-06-23 19:02:27 浏览: 106
在C语言中,我们可以使用二维数组或动态分配的二维指针结构来创建无向图的邻接矩阵存储。这里我会提供一个基本的示例,并解释如何执行上述操作:
1. **建立无向图的邻接矩阵存储**:
```c
#define V 5 // 图中的顶点数
int graph[V][V]; // 初始化一个二维数组,用于存储邻接矩阵
// 添加边的功能
void addEdge(int src, int dest) {
graph[src][dest] = 1; // 如果src到dest有边,将对应位置设置为1(无向图)
graph[dest][src] = 1; // 对称地,dest到src也有边
}
```
2. **输出邻接矩阵**:
```c
void printMatrix() {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
printf("%d ", graph[i][j]);
}
printf("\n");
}
}
```
3. **基于图邻接矩阵的深度优先遍历(DFS)**:
```c
void DFS(int start) {
int visited[V] = {0}; // 初始化访问数组
DFSUtil(start, visited, graph);
}
void DFSUtil(int v, int visited[], int graph[]) {
visited[v] = 1;
printf("%d ", v);
// 访问v的所有未访问的邻居
for (int i = 0; i < V; i++) {
if (visited[i] == 0 && graph[v][i] == 1) {
DFSUtil(i, visited, graph);
}
}
}
```
4. **基于图邻接矩阵的广度优先遍历(BFS)**:
```c
void BFS(int start) {
int queue[V]; // 用于BFS的队列
int level[V] = {0}; // 记录每个节点的层级
int front = -1, rear = -1;
// 初始化
queue[++rear] = start;
level[start] = 0;
while (front != rear) {
int u = queue[++front]; // 取出队首节点
printf("%d ", u);
// 将u的所有未访问的邻居加入队列,并更新它们的层级
for (int i = 0; i < V; i++) {
if (graph[u][i] == 1 && level[i] == 0) {
queue[++rear] = i;
level[i] = level[u] + 1;
}
}
}
}
```
阅读全文