用C语言先依次输入有向图的顶点信息,再依次输入有向图的弧信息,建立图的邻接表存储结构并将其打印输出这个代码中建立的有向图的邻接表存储结构基础上使用非递归算法对图进行深度优先搜索遍历并输出顶点序列并举例
时间: 2024-02-13 11:00:41 浏览: 25
好的,下面是您要的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
// 定义边表结构体
typedef struct ArcNode {
int adjvex; // 邻接点下标
struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;
// 定义顶点表结构体
typedef struct VertexNode {
char data; // 顶点信息
ArcNode *firstarc; // 指向第一个邻接点的指针
} VertexNode;
// 定义图结构体
typedef struct {
VertexNode vexs[MAX_VERTEX_NUM]; // 顶点表
int vexnum, arcnum; // 顶点数和弧数
} Graph;
// 初始化图
void InitGraph(Graph *G) {
printf("请输入顶点数和弧数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
getchar(); // 把回车符吃掉
// 读入顶点信息,建立顶点表
printf("请输入%d个顶点的信息:", G->vexnum);
for (int i = 0; i < G->vexnum; i++) {
scanf("%c", &G->vexs[i].data);
G->vexs[i].firstarc = NULL;
}
// 建立边表
printf("请输入%d条弧的信息(格式为:起点 终点):\n", G->arcnum);
for (int i = 0; i < G->arcnum; i++) {
int head, tail;
scanf("%d%d", &head, &tail);
ArcNode *arc = (ArcNode *) malloc(sizeof(ArcNode));
arc->adjvex = tail;
arc->nextarc = G->vexs[head].firstarc;
G->vexs[head].firstarc = arc;
}
}
// 打印邻接表
void PrintGraph(Graph G) {
printf("邻接表内容如下:\n");
for (int i = 0; i < G.vexnum; i++) {
printf("%c -> ", G.vexs[i].data);
ArcNode *arc = G.vexs[i].firstarc;
while (arc != NULL) {
printf("%c ", G.vexs[arc->adjvex].data);
arc = arc->nextarc;
}
printf("\n");
}
}
// 深度优先搜索
void DFS(Graph G, int v, int *visited) {
int stack[MAX_VERTEX_NUM]; // 定义栈
int top = -1; // 栈顶指针
visited[v] = 1; // 标记该节点已经被访问
printf("%c ", G.vexs[v].data);
// 将起点入栈
stack[++top] = v;
while (top != -1) {
int w = stack[top--]; // 出栈
ArcNode *arc = G.vexs[w].firstarc;
while (arc != NULL) {
int u = arc->adjvex;
if (visited[u] == 0) {
visited[u] = 1;
printf("%c ", G.vexs[u].data);
stack[++top] = u;
}
arc = arc->nextarc;
}
}
}
int main() {
Graph G;
InitGraph(&G);
PrintGraph(G);
int visited[MAX_VERTEX_NUM] = {0}; // 标记节点是否被访问过
printf("深度优先搜索遍历结果为:");
for (int i = 0; i < G.vexnum; i++) {
if (visited[i] == 0) {
DFS(G, i, visited);
}
}
printf("\n");
return 0;
}
```
下面是一个例子,假设我们要建立以下这个图的邻接表存储结构:
```
A -> B C
B -> C D
C -> D
D -> C E
E -> D
```
运行程序后,输入顶点和弧信息,可以得到以下输出:
```
请输入顶点数和弧数:5 6
请输入5个顶点的信息:ABCDE
请输入6条弧的信息(格式为:起点 终点):
0 1
0 2
1 2
1 3
3 2
3 4
邻接表内容如下:
A -> B C
B -> C D
C -> D
D -> C E
E -> D
深度优先搜索遍历结果为:A B C D E
```
其中,最后一行为深度优先搜索遍历的结果。