c语言dfs算法 邻接矩阵
时间: 2023-11-17 17:58:20 浏览: 64
C语言中的DFS算法是一种图遍历算法,它可以用来遍历和搜索图中的所有节点。DFS算法的基本思想是从一个起始节点开始,沿着一条路径一直走到底,直到不能再走为止,然后回溯到上一个节点,继续走其他的路径,直到遍历完整个图。在实现DFS算法时,邻接矩阵可以用来表示图的结构,方便进行遍历和搜索。
具体实现DFS算法时,可以使用递归或者栈来实现。递归实现DFS算法时,需要定义一个visited数组来记录每个节点是否已经被访问过,然后从起始节点开始递归遍历它的邻居节点,直到所有节点都被访问过为止。栈实现DFS算法时,需要定义一个栈来存储待访问的节点,然后从起始节点开始,将它的邻居节点依次入栈,再从栈中取出一个节点进行访问,直到所有节点都被访问过为止。
邻接矩阵是一种表示图结构的方法,它可以用一个二维数组来表示图中节点之间的关系。在邻接矩阵中,数组的行和列分别表示图中的节点,数组中的元素表示节点之间的关系,如果两个节点之间有边相连,则对应的数组元素为1,否则为0。邻接矩阵可以方便地进行图的遍历和搜索,同时也可以用来计算图的一些性质,比如连通性、最短路径等。
相关问题
dfs算法有向图c语言邻接矩阵
以下是使用深度优先搜索(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` 函数用于递归遍历所有与当前节点相连的未访问过的节点。最后,用户需要输入起始节点,程序将从该节点开始遍历整个图,并输出遍历的结果。
c语言邻接矩阵bfs和dfs
以下是C语言中邻接矩阵实现的BFS和DFS算法的示例代码:
BFS算法:
```c
#include <stdio.h>
#include <stdlib.h>
#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;
typedef struct {
VerTexType vexs[MVNum];
ArcType arcs[MVNum][MVNum];
int vexnum, arcnum;
} AMGraph;
int visited[MVNum];
void BFS(AMGraph G, int v) {
int queue[MVNum], front = 0, rear = 0;
int i, j, w;
printf("%c ", G.vexs[v]);
visited[v] = 1;
queue[rear++] = v;
while (front != rear) {
i = queue[front++];
for (j = 0; j < G.vexnum; j++) {
if (G.arcs[i][j] != MaxInt && !visited[j]) {
printf("%c ", G.vexs[j]);
visited[j] = 1;
queue[rear++] = j;
}
}
}
}
int main() {
AMGraph G;
int i, j;
printf("请输入顶点数和边数:");
scanf("%d%d", &G.vexnum, &G.arcnum);
printf("请输入顶点信息:");
for (i = 0; i < G.vexnum; i++) {
scanf("%c", &G.vexs[i]);
}
printf("请输入邻接矩阵:");
for (i = 0; i < G.vexnum; i++) {
for (j = 0; j < G.vexnum; j++) {
scanf("%d", &G.arcs[i][j]);
if (G.arcs[i][j] == 0) {
G.arcs[i][j] = MaxInt;
}
}
}
printf("请输入遍历起点:");
int v;
scanf("%d", &v);
printf("BFS遍历结果:");
BFS(G, v);
return 0;
}
```
DFS算法:
```c
#include <stdio.h>
#include <stdlib.h>
#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;
typedef struct {
VerTexType vexs[MVNum];
ArcType arcs[MVNum][MVNum];
int vexnum, arcnum;
} AMGraph;
int visited[MVNum];
void DFS(AMGraph G, int v) {
int i;
printf("%c ", G.vexs[v]);
visited[v] = 1;
for (i = 0; i < G.vexnum; i++) {
if (G.arcs[v][i] != MaxInt && !visited[i]) {
DFS(G, i);
}
}
}
int main() {
AMGraph G;
int i, j;
printf("请输入顶点数和边数:");
scanf("%d%d", &G.vexnum, &G.arcnum);
printf("请输入顶点信息:");
for (i = 0; i < G.vexnum; i++) {
scanf("%c", &G.vexs[i]);
}
printf("请输入邻接矩阵:");
for (i = 0; i < G.vexnum; i++) {
for (j = 0; j < G.vexnum; j++) {
scanf("%d", &G.arcs[i][j]);
if (G.arcs[i][j] == 0) {
G.arcs[i][j] = MaxInt;
}
}
}
printf("请输入遍历起点:");
int v;
scanf("%d", &v);
printf("DFS遍历结果:");
DFS(G, v);
return 0;
}
```