1.先依次输入有向图的顶点信息,再依次输入有向图的弧信息,建立图的邻接表存储结构并将其打印输出; 2.在1中建立的有向图的邻接表存储结构基础上使用非递归算法对图进行深度优先搜索遍历并输出顶点序列; 3.在1中建立的有向图的邻接表存储结构基础上对图进行广度优先搜索遍历并输出顶点序列。用C语言实现
时间: 2024-02-11 16:06:15 浏览: 24
好的,我将回答你的问题,同时给出 C 语言的实现。
首先,我们需要定义有向图的邻接表结构:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
// 边表结点
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;
```
接下来,我们可以按照你的要求,先依次输入有向图的顶点信息和弧信息,然后建立邻接表存储结构:
```c
// 创建邻接表存储的有向图
void CreateGraph(ALGraph *G) {
printf("请输入顶点数和弧数:");
scanf("%d%d", &(G->vexnum), &(G->arcnum));
getchar(); // 消耗回车符
// 输入顶点信息
printf("请输入%d个顶点:\n", G->vexnum);
int i;
for (i = 0; i < G->vexnum; ++i) {
printf("第%d个顶点:", i + 1);
scanf("%c", &(G->vertices[i].data));
getchar(); // 消耗回车符
G->vertices[i].firstarc = NULL;
}
// 输入弧信息
printf("请输入%d条弧:\n", G->arcnum);
for (i = 0; i < G->arcnum; ++i) {
char v1, v2;
int j, k;
// 输入弧的起点和终点
printf("第%d条弧:", i + 1);
scanf("%c%c", &v1, &v2);
getchar(); // 消耗回车符
// 在顶点数组中查找起点和终点的下标
for (j = 0; j < G->vexnum; ++j) {
if (G->vertices[j].data == v1) {
break;
}
}
for (k = 0; k < G->vexnum; ++k) {
if (G->vertices[k].data == v2) {
break;
}
}
// 将弧插入到邻接表中
ArcNode *p = (ArcNode *) malloc(sizeof(ArcNode));
p->adjvex = k;
p->nextarc = G->vertices[j].firstarc;
G->vertices[j].firstarc = p;
}
}
```
接下来,我们可以打印输出邻接表存储结构:
```c
// 打印邻接表存储的有向图
void PrintGraph(ALGraph G) {
printf("有向图的邻接表存储结构如下:\n");
int i;
for (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");
}
}
```
现在,我们可以测试一下创建和打印邻接表的函数:
```c
int main() {
ALGraph G;
CreateGraph(&G);
PrintGraph(G);
return 0;
}
```
接下来,我们需要实现非递归算法对图进行深度优先搜索遍历:
```c
// 非递归算法实现深度优先搜索遍历
void DFS(ALGraph G, int v, int *visited) {
// 栈初始化
int top = -1;
int stack[MAX_VERTEX_NUM];
stack[++top] = v;
visited[v] = 1;
printf("%c ", G.vertices[v].data);
// 搜索
while (top != -1) {
int w = stack[top];
ArcNode *p = G.vertices[w].firstarc;
while (p != NULL && visited[p->adjvex] == 1) {
p = p->nextarc;
}
if (p != NULL) {
stack[++top] = p->adjvex;
visited[p->adjvex] = 1;
printf("%c ", G.vertices[p->adjvex].data);
} else {
--top;
}
}
}
```
最后,我们需要实现广度优先搜索遍历:
```c
// 广度优先搜索遍历
void BFS(ALGraph G, int v, int *visited) {
// 队列初始化
int front = 0, rear = 0;
int queue[MAX_VERTEX_NUM];
queue[rear++] = v;
visited[v] = 1;
// 搜索
while (front < rear) {
int w = queue[front++];
printf("%c ", G.vertices[w].data);
ArcNode *p = G.vertices[w].firstarc;
while (p != NULL) {
if (visited[p->adjvex] == 0) {
queue[rear++] = p->adjvex;
visited[p->adjvex] = 1;
}
p = p->nextarc;
}
}
}
```
完整代码如下: