根据图的邻接表的类型定义,创建一个无向图,并输出该图 思路
时间: 2024-06-13 17:07:29 浏览: 119
无向图的邻接表存储及输出
4星 · 用户满意度95%
根据图的邻接表的类型定义,创建一个无向图的步骤如下:
1. 定义一个邻接表类型的结构体变量,包括顶点集合、边集合、顶点数、边数和图的类型。
2. 读入顶点数和边数,并将其赋值给邻接表类型的结构体变量。
3. 读入每个顶点的值,并将其存储在邻接表类型的结构体变量的顶点集合中。
4. 读入每条边的信息,包括起点、终点和权值(如果有),并将其存储在邻接表类型的结构体变量的边集合中。
5. 根据边集合中的信息,构建每个顶点的邻接表,将邻接表存储在邻接表类型的结构体变量的顶点集合中。
6. 输出邻接表类型的结构体变量,即可得到创建的无向图。
下面是一个示例代码,用于创建一个无向图并输出该图:
```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);
e = (ENode*)malloc(sizeof(ENode));
e->adjvex = j;
e->nextarc = G->vertices[i].firstarc;
G->vertices[i].firstarc = e;
e = (ENode*)malloc(sizeof(ENode));
e->adjvex = i;
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 ", G.vertices[p->adjvex].vex);
p = p->nextarc;
}
printf("\n");
}
}
int main()
{
ALGraph G;
CreateGraph(&G);
PrintGraph(G);
return 0;
}
```
阅读全文