在C语言中如何用邻接矩阵表示一个无向图,并利用深度优先搜索(DFS)遍历所有节点?请提供详细的代码实现。
时间: 2024-11-01 13:23:17 浏览: 4
为了帮助你解决图的邻接矩阵表示以及深度优先搜索(DFS)遍历问题,我们推荐参考《湖北工业大学自动化技术学院:图基本操作C语言编程实践》这份资料。该资料深入浅出地讲解了图论在计算机编程中的应用,特别是邻接矩阵的构建以及如何通过DFS算法遍历图中的所有节点。
参考资源链接:[湖北工业大学自动化技术学院:图基本操作C语言编程实践](https://wenku.csdn.net/doc/6tczvminhk?spm=1055.2569.3001.10343)
首先,定义一个无向图的邻接矩阵表示。在C语言中,可以使用二维数组来实现。例如,如果图有V个顶点,那么创建一个V x V的二维数组,并初始化为0。如果顶点i和顶点j之间存在一条边,则将邻接矩阵的element[i][j]和element[j][i]设置为1。代码示例如下:
```c
#define MAX_VERTICES 10
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
void initializeGraph(int vertices) {
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
adjMatrix[i][j] = 0;
}
}
}
void addEdge(int start, int end, int vertices) {
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1; // 对无向图来说,需要设置两个方向
}
```
接下来,实现深度优先搜索(DFS)算法。DFS可以递归或使用栈实现。这里给出一个递归的DFS实现示例:
```c
void DFSUtil(int v, int vertices, int visited[]) {
visited[v] = 1;
printf(
参考资源链接:[湖北工业大学自动化技术学院:图基本操作C语言编程实践](https://wenku.csdn.net/doc/6tczvminhk?spm=1055.2569.3001.10343)
阅读全文