用C++实现图的深度优先搜索
时间: 2023-03-25 22:01:29 浏览: 79
可以使用递归或栈来实现图的深度优先搜索。具体实现方法可以参考以下代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *nextarc; // 指向下一条弧的指针
} ArcNode;
typedef struct VNode {
int data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 顶点数和弧数
} ALGraph;
void DFS(ALGraph *G, int v, int visited[]) {
visited[v] = 1; // 标记该顶点已被访问
printf("%d ", G->vertices[v].data); // 输出该顶点的信息
ArcNode *p = G->vertices[v].firstarc;
while (p) {
int w = p->adjvex;
if (!visited[w]) { // 如果该顶点未被访问,则递归访问它
DFS(G, w, visited);
}
p = p->nextarc;
}
}
void DFSTraverse(ALGraph *G) {
int visited[MAX_VERTEX_NUM] = {}; // 初始化所有顶点为未访问状态
for (int i = ; i < G->vexnum; i++) {
if (!visited[i]) { // 如果该顶点未被访问,则从该顶点开始深度优先搜索
DFS(G, i, visited);
}
}
}
int main() {
ALGraph G;
printf("请输入顶点数和弧数:");
scanf("%d%d", &G.vexnum, &G.arcnum);
printf("请输入顶点信息:");
for (int i = ; i < G.vexnum; i++) {
scanf("%d", &G.vertices[i].data);
G.vertices[i].firstarc = NULL;
}
printf("请输入弧的信息:");
for (int k = ; k < G.arcnum; k++) {
int i, j;
scanf("%d%d", &i, &j);
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p;
}
printf("深度优先搜索结果为:");
DFSTraverse(&G);
printf("\n");
return ;
}
```