用C语言实现,从0号顶点出发对该图进行 深度优先搜索,按顺序输出所访问的顶点
时间: 2024-02-13 08:07:26 浏览: 77
好的,我了解了您的问题。以下是C语言实现深度优先搜索的代码,可以对给定的图进行遍历并输出所访问的顶点:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct AdjNode{ // 邻接表中的边结点
int adjvex; // 邻接点的下标
struct AdjNode *next; // 指向下一个邻接点的指针
}AdjNode;
typedef struct VNode{ // 邻接表中的顶点结点
int vertex; // 顶点编号
AdjNode *first_edge; // 指向第一个邻接点的指针
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct{ // 邻接表
AdjList adj_list;
int vertex_num, edge_num; // 顶点数和边数
}Graph;
void create_graph(Graph *G){
printf("请输入图的顶点数和边数:\n");
scanf("%d%d", &(G->vertex_num), &(G->edge_num));
printf("请输入%d个顶点的编号:\n", G->vertex_num);
for(int i=0; i<G->vertex_num; i++){
G->adj_list[i].vertex = i;
G->adj_list[i].first_edge = NULL;
}
printf("请输入%d条边的顶点对应的编号:\n", G->edge_num);
for(int i=0; i<G->edge_num; i++){
int u, v;
scanf("%d%d", &u, &v);
AdjNode *node = (AdjNode*)malloc(sizeof(AdjNode));
node->adjvex = v;
node->next = G->adj_list[u].first_edge;
G->adj_list[u].first_edge = node;
node = (AdjNode*)malloc(sizeof(AdjNode));
node->adjvex = u;
node->next = G->adj_list[v].first_edge;
G->adj_list[v].first_edge = node;
}
}
void DFS(Graph *G, int v, int *visited){
visited[v] = 1;
printf("%d ", v);
AdjNode *p = G->adj_list[v].first_edge;
while(p != NULL){
if(!visited[p->adjvex]){
DFS(G, p->adjvex, visited);
}
p = p->next;
}
}
int main(){
Graph G;
create_graph(&G);
int visited[MAX_VERTEX_NUM] = {0};
printf("深度优先搜索访问的顶点为:\n");
for(int i=0; i<G.vertex_num; i++){
if(!visited[i]){
DFS(&G, i, visited);
}
}
return 0;
}
```
在这段代码中,首先定义了邻接表的数据结构,并定义了一个函数create_graph用于创建图。然后定义了一个函数DFS用于实现深度优先搜索,其中visited数组用于记录每个顶点是否被访问过。最后,在主函数中遍历每个顶点,如果该顶点未被访问过,则以该顶点为起点进行深度优先搜索并输出访问的顶点。
阅读全文
相关推荐















