首先先依次输入有向图的顶点信息,再依次输入有向图的弧信息,建立图的邻接表存储结构并将其打印输出; 然后在建立的有向图的邻接表存储结构基础上使用非递归算法对图进行深度优先搜索遍历并输出顶点序列; 最后在建立的有向图的邻接表存储结构基础上对图进行广度优先搜索遍历并输出顶点序列。用C语言实现
时间: 2024-02-11 11:06:04 浏览: 58
C语言 输入无向图连通图的顶点数、顶点信息、边数、顶点对序列及遍历的起始点序号,输出深度优先遍历序列
5星 · 资源好评率100%
好的,以下是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
typedef struct ArcNode {
int adjvex; // 该弧指向的顶点的位置
struct ArcNode *nextarc; // 指向下一条弧的指针
} ArcNode;
typedef struct VNode {
char data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 顶点数和弧数
} ALGraph;
// 初始化邻接表
void InitGraph(ALGraph *G) {
printf("请输入顶点数和弧数: ");
scanf("%d %d", &G->vexnum, &G->arcnum);
getchar(); // 处理缓冲区
// 输入顶点信息
for (int i = 0; i < G->vexnum; i++) {
printf("请输入第 %d 个顶点的信息: ", i);
scanf("%c", &G->vertices[i].data);
getchar(); // 处理缓冲区
G->vertices[i].firstarc = NULL; // 初始化指向第一条依附该顶点的弧的指针
}
// 输入弧信息
for (int i = 0; i < G->arcnum; i++) {
int h, t;
printf("请输入第 %d 条弧的头尾顶点位置: ", i);
scanf("%d %d", &h, &t);
ArcNode *arcNode = (ArcNode*)malloc(sizeof(ArcNode));
arcNode->adjvex = t;
arcNode->nextarc = G->vertices[h].firstarc;
G->vertices[h].firstarc = arcNode;
}
}
// 非递归深度优先遍历
void DFS(ALGraph *G, int v, int *visited) {
int stack[MAX_VERTEX_NUM], top = -1;
stack[++top] = v;
while (top >= 0) {
int w = stack[top--];
if (visited[w] == 0) {
printf("%c ", G->vertices[w].data);
visited[w] = 1;
for (ArcNode *p = G->vertices[w].firstarc; p != NULL; p = p->nextarc) {
if (visited[p->adjvex] == 0) {
stack[++top] = p->adjvex;
}
}
}
}
}
// 广度优先遍历
void BFS(ALGraph *G, int v, int *visited) {
int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
queue[rear++] = v;
while (front != rear) {
int w = queue[front++];
printf("%c ", G->vertices[w].data);
visited[w] = 1;
for (ArcNode *p = G->vertices[w].firstarc; p != NULL; p = p->nextarc) {
if (visited[p->adjvex] == 0) {
queue[rear++] = p->adjvex;
visited[p->adjvex] = 1;
}
}
}
}
int main() {
ALGraph G;
InitGraph(&G);
printf("邻接表结构如下:\n");
for (int i = 0; i < G.vexnum; i++) {
printf("%c -> ", G.vertices[i].data);
for (ArcNode *p = G.vertices[i].firstarc; p != NULL; p = p->nextarc) {
printf("%c -> ", G.vertices[p->adjvex].data);
}
printf("NULL\n");
}
printf("非递归深度优先遍历结果: ");
int visited1[MAX_VERTEX_NUM] = {0};
for (int i = 0; i < G.vexnum; i++) {
if (visited1[i] == 0) {
DFS(&G, i, visited1);
}
}
printf("\n");
printf("广度优先遍历结果: ");
int visited2[MAX_VERTEX_NUM] = {0};
for (int i = 0; i < G.vexnum; i++) {
if (visited2[i] == 0) {
BFS(&G, i, visited2);
}
}
printf("\n");
return 0;
}
```
这段代码实现了输入顶点信息和弧信息,并建立有向图的邻接表存储结构。然后,通过非递归深度优先遍历和广度优先遍历算法分别输出了顶点序列。注意,我将邻接表数组定义为了 `AdjList[MAX_VERTEX_NUM]`,其中 `MAX_VERTEX_NUM` 表示顶点数的最大值。这样定义的好处是,可以避免在输入顶点数时再次输入数组大小。
阅读全文