先依次输入有向图的顶点信息,再依次输入有向图的弧信息,建立图的邻接表存储结构并将其打印输出; 接下来在建立的有向图的邻接表存储结构基础上使用非递归算法对图进行深度优先搜索遍历并输出顶点序列; 最后在建立的有向图的邻接表存储结构基础上对图进行广度优先搜索遍历并输出顶点序列。用C语言实现
时间: 2024-02-12 22:04:45 浏览: 22
好的,以下是C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
typedef char VertexType; // 顶点类型
typedef struct ArcNode {
int adjvex; // 邻接点在顶点数组中的位置下标
struct ArcNode *nextarc; // 指向下一条弧的指针
} ArcNode;
typedef struct VNode {
VertexType data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; // 顶点数组
int vexnum, arcnum; // 图的当前顶点数和弧数
} ALGraph;
// 创建有向图的邻接表存储结构
void CreateGraph(ALGraph *G) {
printf("请输入顶点数和弧数:");
scanf("%d %d", &(G->vexnum), &(G->arcnum));
printf("请输入顶点信息:");
for (int i = 0; i < G->vexnum; i++) {
scanf(" %c", &(G->vertices[i].data));
G->vertices[i].firstarc = NULL;
}
printf("请输入弧信息:");
for (int k = 0; k < G->arcnum; k++) {
printf("请输入第%d条弧的两个端点:", k + 1);
VertexType v1, v2;
scanf(" %c %c", &v1, &v2);
int i, j;
for (i = 0; i < G->vexnum; i++) {
if (G->vertices[i].data == v1) {
break;
}
}
for (j = 0; j < G->vexnum; j++) {
if (G->vertices[j].data == v2) {
break;
}
}
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = G->vertices[i].firstarc;
G->vertices[i].firstarc = p;
}
}
// 深度优先搜索遍历
void DFS(ALGraph G, int v, int visited[]) {
visited[v] = 1;
printf("%c ", G.vertices[v].data);
ArcNode *p = G.vertices[v].firstarc;
while (p != NULL) {
int w = p->adjvex;
if (visited[w] == 0) {
DFS(G, w, visited);
}
p = p->nextarc;
}
}
void DFSTraverse(ALGraph 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");
}
// 广度优先搜索遍历
void BFSTraverse(ALGraph G) {
int visited[MAX_VERTEX_NUM] = {0};
int queue[MAX_VERTEX_NUM];
int front = 0, rear = 0;
printf("广度优先搜索遍历顶点序列为:");
for (int i = 0; i < G.vexnum; i++) {
if (visited[i] == 0) {
visited[i] = 1;
printf("%c ", G.vertices[i].data);
queue[rear++] = i;
}
while (front != rear) {
int j = queue[front++];
ArcNode *p = G.vertices[j].firstarc;
while (p != NULL) {
int k = p->adjvex;
if (visited[k] == 0) {
visited[k] = 1;
printf("%c ", G.vertices[k].data);
queue[rear++] = k;
}
p = p->nextarc;
}
}
}
printf("\n");
}
int main() {
ALGraph G;
CreateGraph(&G);
printf("邻接表存储结构为:\n");
for (int i = 0; i < G.vexnum; i++) {
printf("%c -> ", G.vertices[i].data);
ArcNode *p = G.vertices[i].firstarc;
while (p != NULL) {
printf("%c -> ", G.vertices[p->adjvex].data);
p = p->nextarc;
}
printf("NULL\n");
}
DFSTraverse(G);
BFSTraverse(G);
return 0;
}
```
在程序中,我们首先定义了结构体 `ArcNode`(表示弧)和 `VNode`(表示顶点),并将 `VNode` 数组定义为 `AdjList`。`ALGraph` 结构体包含了 `AdjList` 数组、图的顶点数 `vexnum` 和弧数 `arcnum`。
`CreateGraph` 函数用于创建有向图的邻接表存储结构。我们先输入顶点数和弧数,然后输入每个顶点的信息,最后输入每条弧的信息。在输入弧的信息时,我们需要找到它们在顶点数组中的下标,然后将弧插入到相应的邻接表中。
`DFS` 函数用于进行深度优先搜索遍历。我们首先将当前顶点标记为已访问,并输出它的信息。然后遍历它的邻接表,对于每个未访问的邻接点,递归调用 `DFS` 函数。这样,我们就可以依次遍历图中所有连通的顶点。
`DFSTraverse` 函数用于对整个图进行深度优先搜索遍历。我们从第一个未访问的顶点开始,依次调用 `DFS` 函数。
`BFSTraverse` 函数用于进行广度优先搜索遍历。我们使用一个队列来存储已访问的顶点,以便按照广度优先的顺序访问它们。首先将第一个未访问的顶点标记为已访问,并输出它的信息。然后将它加入队列中。接下来,从队列中取出一个顶点,遍历它的邻接表,并将未访问的邻接点加入队列中。这样,我们就可以依次遍历图中所有连通的顶点。
最后,我们在 `main` 函数中依次调用上述函数,即可完成有向图的建立和遍历。