数据结构之图-创建邻接矩阵图结构-学习笔记-65

引入

我们知道如何构建一个图的数据结构,那么现在,我们看看如何根据一棵图的图形,创建一张图到内存中去。

创建数据结构

1
2
3
4
5
6
7
8
#define MAX_VEX_NUM 50  //最大的容量暂定为50
typedef enum {DG, UDG} GraphType; //选择有向图还是无向图
typedef struct {
char vexs[MAX_VEX_NUM]; //一维数组存储顶点
int arcs[MAX_VEX_NUM][MAX_VEX_NUM]; //二维数组(邻接矩阵)存储边
int vexnum, arcnum; //记录顶点的数量和边的数量,等下用作循环判断条件
GraphType type; //记录图得类型
} MGraph;

数据结构中

  • 记录顶点的数量和边的数量,等下用作循环判断条件
  • 记录图得类型,等下用于写入矩阵

获取数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void create_MG(MGraph *MG)
{

int type; //存储图得类型
printf("请输入图的类型,有向图(输入0)无向图(输入1) :");
scanf("%d", &type);
//如果是0,那就是有向图,如果是1那就是无向图
if (type == 0)
MG->type = DG;
else if (type == 1)
MG->type = UDG;
else
{
printf("请输入正确的图类型,有向图(输入0)无向图(输入1)");
return;
}

//获取数值
printf("请输入顶点个数:");
scanf("%d", &MG->vexnum); //数值赋值给 MG 的 vexnum
printf("请输入边个数:");
scanf("%d", &MG->arcnum);
getchar(); //接收最后那个回车

int i;
int v1, v2;
//有多少个顶点,就输入多少次
for (i = 1; i <= MG->vexnum; i++)
{
printf("请输入第%d个顶点的值:", i);
scanf("%c", &MG->vexs[i]);
getchar();
}
//以上就完成了所有信息的获取

我们一部分一部分的讲

  • 先输入1或0判断图类型,然后存到结构体中
  • 然后输入顶点数和边树,方便下面判断循环次数
  • 接着根据顶点数,接收每个顶点得值
  • 所有数据获取完毕

初始化矩阵

1
2
3
4
5
6
7
8
//初始化邻接矩阵,双层循环将二维数组都填充为0
for (i = 1; i <= MG->vexnum; i++)
{
for (j = 1; j <= MG->vexnum; j++)
{
MG->arcs[i][j] = 0;
}
}

这里我们先把矩阵创建出来

  • 判断条件就是顶点的个数,有多少顶点创建多大的矩阵
  • 矩阵中默认的值为0

在矩阵中定位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//定位
// 输入矩阵指针和顶点得值,判断在一维数组中这是第几号,并返回
int getIndexOfVexs(char vex, MGraph *MG)
{
int i;
//有多少结点循环多少次
for (i = 1; i <= MG->vexnum; i++)
{
//如果值等于输入的值,那么就把在一维数组中的位置返回
if (MG->vexs[i] == vex)
{
return i;
}
}
return 0;
}

这个定位的函数,主要是

  • 将用户输入的值,在一维数组中找到它的位置
  • 然后将这个位置返回
  • 我们就能通过这个位置在矩阵中定位到它了

处理边的信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//输入边的信息,建立邻接矩阵,有多少边执行多少次
char c1, c2;
int j, k;
for (k = 1; k <= MG->arcnum; k++) {
printf("请输入第%d个边: ", k);
scanf("%c %c", &c1, &c2);
//利用上面的定位函数,找到输入的顶点在一维数组中的位置
v1 = getIndexOfVexs(c1, MG);
v2 = getIndexOfVexs(c2, MG);

if (MG->type == 1) //如果是y无向图,则对称矩阵,把对称位置上的值同时赋值为1
MG->arcs[v1][v2] = MG->arcs[v2][v1] = 1;
else //如果是有向图,则只在指定位置赋值。
MG->arcs[v1][v2] = 1;
getchar();
}

有多少个顶点就循环多少次

  • 接收到构成边的两个顶点
  • 然后利用上面的定位函数,返回在一维数组中的位置
  • 接着判断图得类型
  • 无向图,那么矩阵对称,则在对称位置同时赋值 1
  • 有向图,矩阵不对称,所以只在对应位置赋值 1

总代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <stdio.h>
#include <stdlib.h>
#define MAX 50

typedef enum{DG,UDG} GraphType;

typedef struct {
char vex[MAX]; //定义一维数组存储顶点
int arcs[MAX][MAX]; //定义二维数组存储边
int vexnum,arcnum; //存储顶点和边的数量
GraphType type; //存储图的类型
}Graph;

int position(char c , Graph *G){
int i;
for(i=1;i<=G->vexnum;i++){
if(G->vex[i]==c){
return i;
}
}
return 0;
}

void Create(Graph * G){
//获取图的类型
int type;
printf("请输入图的类型,有向图输入1,无向图输入0:");
scanf("%d",&type);
if(type==1){
G->type=DG;
}else if(type==0){
G->type=UDG;
}else{
printf("输入的类型不正确!\n");
return;
}
//获取图得顶点数和边数
printf("图有几个顶点:");
scanf("%d",&G->vexnum);
printf("图有几条边:");
scanf("%d",&G->arcnum);
getchar();
//获得每个顶点得值

for(int k=1;k<=G->vexnum;k++){
printf("请输入第%d个结点的值:",k);
scanf("%s",&G->vex[k]);
getchar();
}
//值全部获得完毕

//矩阵初始化
int i,j;
for (i = 1; i <= G->vexnum; i++)
{
for (j = 1; j <= G->vexnum; j++)
{
G->arcs[i][j] = 0;
}
}
//有多少个结点循环多少次
char V1,V2;
int V1p,V2p;
for(int l=1;l<=G->arcnum;l++){
printf("请输第%d个边的信息:",l);
scanf("%c %c",&V1,&V2);
V1p=position(V1,G);
V2p=position(V2,G);

if(G->type==UDG){
G->arcs[V1p][V2p]=G->arcs[V2p][V1p]=1;
}else{
G->arcs[V1p][V2p]=1;
}
getchar();
}
}


void print_MG(Graph MG){
printf("-------------------------------\n");
int i, j;
if(MG.type == DG)
{
printf("图类型 : 有向图\n");
}
else
{
printf("图类型:无向图\n");
}
printf("图中的顶点有: %d 个\n",MG.vexnum);
printf("图中的边/弧有: %d 个\n",MG.arcnum);

printf("顶点的集合:");
for (i = 1; i <= MG.vexnum; i++){
printf("%c ", MG.vex[i]);
}
printf("\n");
printf("邻接矩阵:\n");

for (i = 1; i <= MG.vexnum; i++)
{
printf("%c ", MG.vex[i]);
j = 1;
for (; j < MG.vexnum; j++)
{
printf("%d ", MG.arcs[i][j]);
}
printf("%d ", MG.arcs[i][j]);
printf("\n");
}
}
int main()
{
Graph MG;
Create(&MG);
print_MG(MG);
return 0;
}

V0 V1 v2 v3
V0 0 1 1 1
V1 1 0 1 0
V2 1 1 0 1
V3 1 0 1 0

我们将上面的图输入程序,我们用 a、b、c、d 代替v1、v2、v3、v4

运行结果
请输入图的类型,有向图输入1,无向图输入0:0
图有几个顶点:4
图有几条边:5
请输入第1个结点的值:a
请输入第2个结点的值:b
请输入第3个结点的值:c
请输入第4个结点的值:d
请输第1个边的信息:a b
请输第2个边的信息:b c
请输第3个边的信息:c d
请输第4个边的信息:d a

请输第5个边的信息:a c

图类型:无向图
图中的顶点有: 4 个
图中的边/弧有: 5 个
顶点的集合:a b c d
邻接矩阵:
a 0 1 1 1
b 1 0 1 0
c 1 1 0 1
d 1 0 1 0

运行结果同矩阵相同,成功!

尾巴

这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。


-------------The End-------------
欢迎请我喝咖啡哦~!