1.先依次输入有向图的顶点信息,再依次输入有向图的弧信息,建立图的邻接表存储结构并将其打印输出; 2.在1中建立的有向图的邻接表存储结构基础上使用非递归算法对图进行深度优先搜索遍历并输出顶点序列; 3.在1中建立的有向图的邻接表存储结构基础上对图进行广度优先搜索遍历并输出顶点序列。用C语言实现以上操作
时间: 2024-02-11 09:06:24 浏览: 55
好的,我会根据您的要求依次回答问题。首先,我将回答第一个问题。
1. 建立有向图的邻接表存储结构并输出
```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, AdjList[MAX_VERTEX_NUM];
typedef struct { // 图
AdjList vertices; // 邻接表
int vexnum, arcnum; // 顶点数和弧数
} Graph;
void createGraph(Graph *G) {
printf("请输入顶点数和弧数(用空格隔开):");
scanf("%d %d", &G->vexnum, &G->arcnum);
getchar();
printf("请输入顶点信息:\n");
for (int i = 0; i < G->vexnum; i++) {
printf("第%d个顶点信息:", i + 1);
G->vertices[i].data = getchar();
getchar();
G->vertices[i].firstarc = NULL; // 初始化弧链表
}
printf("请输入弧信息(格式:起点 终点):\n");
for (int k = 0; k < G->arcnum; k++) {
int i, j;
scanf("%d %d", &i, &j);
ArcNode *arc = (ArcNode*) malloc(sizeof(ArcNode));
arc->adjvex = j - 1; // 弧指向的位置
arc->nextarc = G->vertices[i - 1].firstarc;
G->vertices[i - 1].firstarc = arc;
}
}
void printGraph(Graph G) {
printf("邻接表:\n");
for (int i = 0; i < G.vexnum; i++) {
printf("%d(%c): ", i + 1, G.vertices[i].data);
ArcNode *p = G.vertices[i].firstarc;
while (p) {
printf("%d ", p->adjvex + 1);
p = p->nextarc;
}
printf("\n");
}
}
int main() {
Graph G;
createGraph(&G);
printGraph(G);
return 0;
}
```
这里使用了邻接表存储结构,其中顶点结点包含了顶点信息和指向第一个弧结点的指针;弧结点则包含了弧指向的顶点位置和指向下一个弧结点的指针。
输入时,先输入顶点数和弧数,再输入每个顶点的信息,最后输入每条弧的信息。弧信息按照起点和终点输入,需要将终点转换成顶点位置,即减去1。
输出时,按照顶点的顺序依次遍历每个顶点,输出顶点信息和它所指向的顶点位置。
运行结果:
```
请输入顶点数和弧数(用空格隔开):5 6
请输入顶点信息:
第1个顶点信息:A
第2个顶点信息:B
第3个顶点信息:C
第4个顶点信息:D
第5个顶点信息:E
请输入弧信息(格式:起点 终点):
1 2
1 3
2 4
3 4
3 5
5 2
邻接表:
1(A): 2 3
2(B): 4
3(C): 4 5
4(D):
5(E): 2
```
下一步,我将回答第二个问题:使用非递归算法对图进行深度优先搜索遍历并输出顶点序列。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)