实验要求: 要建立的是有向图(1)还是无向图(0),请选择(输入1或0):1 =======将建立一个无向图======= 请输入图的顶点数:8 请输入图的边数:9 请输入图的各顶点信息: 第1个顶点信息:A 第2个顶点信息:B 第3个顶点信息:C 第4个顶点信息:D 第5个顶点信息:E 第6个顶点信息:F 第7个顶点信息:G 第8个顶点信息:H 请输入边的信息,格式为:序号1,序号2(序号依次为0、1、2……): 请输入第0条边:0,1 请输入第2条边:0,2 请输入第3条边:1,3 请输入第4条边:1,4 请输入第5条边:2,5 请输入第6条边:2,6 请输入第7条边:3,7 请输入第8条边:4,7 请输入第9条边:5,6用C语言实现
时间: 2024-03-09 13:46:49 浏览: 75
图的创建(有向图,无向图,有向网,无向网)及输出
4星 · 用户满意度95%
好的,以下是用C语言实现建立有向图的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
#define INFINITY 65535 // 无穷大
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 InitGraph(ALGraph *G) {
int i;
G->vexnum = G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertices[i].data = '\0';
G->vertices[i].firstarc = NULL;
}
}
// 获取顶点在邻接表中的位置
int LocateVex(ALGraph *G, VertexType v) {
int i;
for (i = 0; i < G->vexnum; i++) {
if (G->vertices[i].data == v) {
return i;
}
}
return -1;
}
// 添加顶点
void AddVex(ALGraph *G, VertexType v) {
if (G->vexnum >= MAX_VERTEX_NUM) {
printf("Error: The graph is full!\n");
return;
}
G->vertices[G->vexnum].data = v;
G->vertices[G->vexnum++].firstarc = NULL;
}
// 添加边
void AddArc(ALGraph *G, VertexType v, VertexType w) {
int vidx, widx;
ArcNode *p;
vidx = LocateVex(G, v);
widx = LocateVex(G, w);
if (vidx == -1 || widx == -1) {
printf("Error: Vex does not exist!\n");
return;
}
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = widx;
p->nextarc = G->vertices[vidx].firstarc;
G->vertices[vidx].firstarc = p;
G->arcnum++;
}
// 输出邻接表
void PrintGraph(ALGraph *G) {
int i;
ArcNode *p;
for (i = 0; i < G->vexnum; i++) {
printf("%c: ", G->vertices[i].data);
p = G->vertices[i].firstarc;
while (p) {
printf("%c ", G->vertices[p->adjvex].data);
p = p->nextarc;
}
printf("\n");
}
}
int main() {
ALGraph G;
InitGraph(&G);
AddVex(&G, 'A');
AddVex(&G, 'B');
AddVex(&G, 'C');
AddVex(&G, 'D');
AddVex(&G, 'E');
AddVex(&G, 'F');
AddVex(&G, 'G');
AddVex(&G, 'H');
AddArc(&G, 'A', 'B');
AddArc(&G, 'A', 'C');
AddArc(&G, 'B', 'D');
AddArc(&G, 'B', 'E');
AddArc(&G, 'C', 'F');
AddArc(&G, 'C', 'G');
AddArc(&G, 'D', 'H');
AddArc(&G, 'E', 'H');
AddArc(&G, 'F', 'G');
PrintGraph(&G);
return 0;
}
```
这个代码实现了建立一个有向图,顶点数为8,边数为9,顶点分别为A、B、C、D、E、F、G、H,边的信息为0,1、0,2、1,3、1,4、2,5、2,6、3,7、4,7、5,6。这个程序的输出结果是:
```
A: B C
B: E D
C: G F
D: H
E: H
F: G
G:
H:
```
即按照邻接表的形式输出了该有向图的结构。
阅读全文