根据图的邻接表的类型定义,创建一个无向图,并输出该图 结论
时间: 2024-06-13 10:07:29 浏览: 118
根据图的邻接表的类型定义,创建一个无向图的步骤如下:
1. 定义一个邻接表类型的结构体变量,包括顶点集合、边集合、顶点数、边数和图的类型等信息。
2. 读入顶点数和边数,并根据顶点数动态分配存储空间。
3. 读入每个顶点的信息,并将其存储在邻接表的头结点中。
4. 读入每条边的信息,根据边的信息在邻接表中添加相应的边。
5. 输出邻接表中每个顶点的邻接点信息,即与该顶点相邻的所有顶点。
下面是一个无向图的创建和输出过程的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 20 /*最大顶点数*/
typedef enum{DG,DN,UDG,UDN} GraphKind; /*有向图,有向网,无向图,无向网*/
typedef struct ENode /*表结点类型*/
{
int adjvex;
struct ENode *nextarc;
int weight;
}ENode;
typedef int VexType;
typedef struct VNode /*头结点类型*/
{
VexType vex;
ENode *firstarc;
}VNode, AdjList[MAXVEX]; /*邻接表类型定义*/
typedef struct {
AdjList vertices; /*用邻接表存储顶点集合及边集合*/
int vexnum,edgenum;
GraphKind kind;
}ALGraph; /*邻接表存储的图的类型定义*/
void CreateGraph(ALGraph *G)
{
int i, j, k, w;
ENode *e;
printf("请输入顶点数和边数:");
scanf("%d%d", &G->vexnum, &G->edgenum);
printf("请输入顶点信息:");
for (i = 0; i < G->vexnum; i++)
{
scanf("%d", &G->vertices[i].vex);
G->vertices[i].firstarc = NULL;
}
printf("请输入边信息:");
for (k = 0; k < G->edgenum; k++)
{
printf("请输入第%d条边的起点和终点:", k + 1);
scanf("%d%d", &i, &j);
printf("请输入第%d条边的权值:", k + 1);
scanf("%d", &w);
e = (ENode*)malloc(sizeof(ENode));
e->adjvex = j;
e->weight = w;
e->nextarc = G->vertices[i].firstarc;
G->vertices[i].firstarc = e;
e = (ENode*)malloc(sizeof(ENode));
e->adjvex = i;
e->weight = w;
e->nextarc = G->vertices[j].firstarc;
G->vertices[j].firstarc = e;
}
}
void PrintGraph(ALGraph G)
{
int i;
ENode *p;
printf("该无向图的邻接表为:\n");
for (i = 0; i < G.vexnum; i++)
{
printf("%d: ", G.vertices[i].vex);
p = G.vertices[i].firstarc;
while (p != NULL)
{
printf("%d(%d) ", p->adjvex, p->weight);
p = p->nextarc;
}
printf("\n");
}
}
int main()
{
ALGraph G;
CreateGraph(&G);
PrintGraph(G);
return 0;
}
```
输出结果如下:
```
请输入顶点数和边数:5 6
请输入顶点信息:0 1 2 3 4
请输入边信息:
请输入第1条边的起点和终点:0 1
请输入第1条边的权值:1
请输入第2条边的起点和终点:0 2
请输入第2条边的权值:2
请输入第3条边的起点和终点:1 2
请输入第3条边的权值:3
请输入第4条边的起点和终点:1 3
请输入第4条边的权值:4
请输入第5条边的起点和终点:2 4
请输入第5条边的权值:5
请输入第6条边的起点和终点:3 4
请输入第6条边的权值:6
该无向图的邻接表为:
0: 2(2) 1(1)
1: 3(4) 2(3) 0(1)
2: 4(5) 1(3) 0(2)
3: 4(6) 1(4)
4: 3(6) 2(5)
```
因此,该无向图的结论为:该无向图的邻接表为:
0: 2(2) 1(1)
1: 3(4) 2(3) 0(1)
2: 4(5) 1(3) 0(2)
3: 4(6) 1(4)
4: 3(6) 2(5)
阅读全文