dfs算法有向图c语言邻接矩阵
时间: 2023-07-26 11:11:45 浏览: 55
以下是使用深度优先搜索(DFS)算法遍历有向图的 C 语言代码示例,其中使用邻接矩阵来存储有向图:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
int adj[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES] = {0};
void DFS(int start, int numVertices) {
visited[start] = 1;
printf("%d ", start);
for (int i = 0; i < numVertices; i++) {
if (adj[start][i] && !visited[i]) {
DFS(i, numVertices);
}
}
}
int main() {
int numVertices, numEdges;
printf("Enter the number of vertices and edges: ");
scanf("%d%d", &numVertices, &numEdges);
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
adj[i][j] = 0;
}
}
int src, dest;
printf("Enter the edges (source, destination):\n");
for (int i = 0; i < numEdges; i++) {
scanf("%d%d", &src, &dest);
adj[src][dest] = 1;
}
int startVertex;
printf("Enter the starting vertex for DFS: ");
scanf("%d", &startVertex);
printf("DFS traversal starting from vertex %d: ", startVertex);
DFS(startVertex, numVertices);
return 0;
}
```
这段代码使用邻接矩阵来存储有向图,其中 `adj[i][j]` 表示从节点 `i` 到节点 `j` 是否有一条有向边。然后使用 DFS 算法遍历图中所有节点。其中,`DFS` 函数用于递归遍历所有与当前节点相连的未访问过的节点。最后,用户需要输入起始节点,程序将从该节点开始遍历整个图,并输出遍历的结果。