图的深度优先搜索(邻接表存储)c實現
时间: 2023-09-29 11:03:08 浏览: 54
下面是图的深度优先搜索(邻接表存储)的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXV 1000 // 最大顶点数
/* 邻接表结构体定义 */
typedef struct node {
int adjvex; // 邻接点编号
struct node *next; // 链域
} EdgeNode;
/* 顶点结构体定义 */
typedef struct vnode {
int vertex; // 顶点编号
EdgeNode *first; // 指向第一个相邻顶点的指针
} VertexNode;
/* 图结构体定义 */
typedef struct graph {
VertexNode adjList[MAXV]; // 邻接表
int n, e; // 图的顶点数和边数
} Graph;
int visited[MAXV]; // 标记数组,记录每个顶点是否被访问过
/* 初始化图 */
void initGraph(Graph *G, int n) {
G->n = n;
G->e = 0;
for (int i = 0; i < n; i++) {
G->adjList[i].vertex = i;
G->adjList[i].first = NULL;
}
}
/* 添加边 */
void addEdge(Graph *G, int u, int v) {
EdgeNode *p = (EdgeNode *) malloc(sizeof(EdgeNode));
p->adjvex = v;
p->next = G->adjList[u].first;
G->adjList[u].first = p;
G->e++;
}
/* 深度优先搜索 */
void DFS(Graph *G, int v) {
visited[v] = 1;
printf("%d ", v); // 访问顶点v
EdgeNode *p = G->adjList[v].first;
while (p != NULL) {
int w = p->adjvex;
if (!visited[w]) {
DFS(G, w); // 递归访问相邻顶点w
}
p = p->next;
}
}
int main() {
Graph G;
int n = 5; // 顶点数
initGraph(&G, n);
addEdge(&G, 0, 1);
addEdge(&G, 0, 2);
addEdge(&G, 1, 3);
addEdge(&G, 1, 4);
printf("DFS: ");
DFS(&G, 0);
printf("\n");
return 0;
}
```
这段代码实现了图的深度优先搜索(邻接表存储),可以根据需要进行修改和扩展。