一、邻接矩阵
1.邻接矩阵表示法
邻接矩阵是用于表示图的数据结构之一,可以用二维数组来表示。在邻接矩阵中,每个顶点都对应矩阵的一行和一列,矩阵中的值表示相应两个顶点之间的连通性。如果两个顶点之间存在一条边,则矩阵中对应位置为1;否则为0。如果是网 ,则矩阵中对应位置为权值;否则为(计算机允许、大于所以边上的数)。对于无向图而言,邻接矩阵是对称的;而对于有向图而言,则不一定对称。邻接矩阵可以方便地进行图的遍历、查找和修改等操作,但是对于稀疏图(边数较少)来说,邻接矩阵会浪费大量的空间。
用邻接矩阵表示法表示图除了一个用于储存邻接矩阵的二维数组外,还需要一个一维数组储存顶点信息。
储存结构如下:
#define MVNum 100//最大顶点数
#define MaxInt 66666//表示极大值
typedef struct {
char vexs[MVNum];//顶点表(顶点为字符型)
int arcs[MVNum][MVNum];//邻接矩阵(权值为整型)
int vexnum, arcnum;//图的当前点数和边数
}AMGraph;
2.采用邻接矩阵表示法创建无向网
//定位
int LocateVex(AMGraph* G, char v) {
int i;
for (i = 0; i < G->vexnum; i++) {
if (G->vexs[i] == v) {
return i;
}
}
return -1;
}
//创建无向网G
AMGraph* CreateUDN() {
int i, j, k, w;
char v1, v2;
AMGraph* G = malloc(sizeof(AMGraph));
printf("输入总顶点数,边数\n");
scanf("%d%d", &G->vexnum, &G->arcnum);
getchar();//吸收换行符
printf("依次输入点的信息\n");
for (i = 0; i < G->vexnum; i++) {
scanf("%c", &G->vexs[i]);
}
getchar();//吸收换行符
for (i = 0; i < G->vexnum; i++)
for (j = 0; j < G->vexnum; j++) {
if (i == j) {
G->arcs[i][j] = 0;
}
else {
G->arcs[i][j] = MaxInt;
}
}
for (k = 0; k < G->arcnum; k++) {
printf("输入一条边依附的顶点及权值\n");
scanf("%c%c", &v1, &v2);
scanf("%d", &w);
getchar();//吸收换行符
i = LocateVex(G, v1), j = LocateVex(G, v2);//确定v1、v2在顶点数组的下标
G->arcs[i][j] = w;//边<v1,v2>权值置为w
G->arcs[j][i] = w;//无向网对称边<v2,v2>权值也置为w
}
return G;
}
再写个输出函数
void print(AMGraph* G) {
int i, j;
printf(" ");
for (i = 0; i < G->vexnum; i++) {
printf("%c ", G->vexs[i]);
}
printf("\n");
for (i = 0; i < G->vexnum; i++) {
printf("%c ", G->vexs[i]);
for (j = 0; j < G->vexnum; j++) {
if (G->arcs[i][j] == MaxInt)
printf("∞ ");
else
printf("%d ", G->arcs[i][j]);
}
printf("\n");
}
}
如果要创建无向图,只需改动两处:一是初始化时将边的权值都初始化为0;二是构造邻接矩阵时将权值w改为1。同样,稍做修改即可建立有向图或有线网(如果你前面知识学懂了,这里肯定没问题)。
二、邻接表
1.邻接表表示法
邻接表(Adjacency List)是一种表示无向图或有向图的数据结构。它使用一个数组来存储所有顶点,每个顶点对应一个链表。链表中存储了与该顶点直接相邻的所有顶点。对于有向图,邻接表中的链表只存储指向的顶点(个数为出度)。有时,为了便于确定顶点的入度,可以建立有向图的逆邻接表。
邻接表储存结构如下:
#define MVNum 100 //最大顶点数
typedef struct ArcNode { //边表结点
int adjvex;//邻接点在顶点数组中的下标
struct ArcNode* next;//指向下一条边的指针
}ArcNode;
typedef struct VNode { //表头顶点信息结构体
char data;
ArcNode* first;//指向第一条依附于该顶点的边的指针
}VNode, AdjList[MVNum];
typedef struct { //图结构体
AdjList vertices;//邻接表
int vexnum, arcnum;//顶点数和边数
}ALGraph;
2.采用邻接表表示法创建无向图
- 首先输入顶点数和边数
- 对于每条边,都会关联两个顶点,所以接下里输入被关联的两个顶点
- 通过输入的顶点调用LocateVex函数来找到这两个顶点在顶点数组中的下标
- 创建新结点,采用头插法插入到关联顶点的表头结点指向的单链表中
//查找
int LocateVex(ALGraph* G, char v) {
int i;
for (i = 0; i < G->vexnum; i++) {
if (G->vertices[i].data == v) {
return i;
}
}
return -1;
}
//无向图的创建
ALGraph* CreateALGraph() {
int i, j, k;
char v1, v2;
ALGraph* G = malloc(sizeof(ALGraph));
printf("输入顶点数和边数:\n");
scanf("%d%d", &G->vexnum, &G->arcnum);
getchar();//吸收换行符
printf("依次输入顶点信息:\n");
for (i = 0; i < G->vexnum; i++) {
scanf("%c", &G->vertices[i].data);
G->vertices[i].first = NULL;
}
getchar();//吸收换行符
//构造边表
for (k = 0; k < G->arcnum; k++) {
printf("输入一条边依附的两个顶点:\n");
scanf("%c%c", &v1, &v2);
getchar();//吸收换行符
i = LocateVex(G, v1), j = LocateVex(G, v2);//确定v1、v2在邻接表数组中的下标
ArcNode* p1 = malloc(sizeof(ArcNode));//生成新的边结点*p1
p1->adjvex = i;//邻接点序号为i
p1->next = G->vertices[j].first;//头插法插到顶点vj的边表头部
G->vertices[j].first = p1;
//因为是无向图,所以生成对称的边结点*p2
ArcNode* p2 = malloc(sizeof(ArcNode));
p2->adjvex = j;
p2->next = G->vertices[i].first;
G->vertices[i].first = p2;
}
return G;
}
还可以写个输出邻接表的函数
void print(ALGraph* G) {
int i;
for (i = 0; i < G->vexnum; i++) {
printf("顶点%c的邻结点有:", G->vertices[i].data);
ArcNode* p = G->vertices[i].first;
while (p != NULL) {
printf(" %c", G->vertices[p->adjvex].data);
p = p->next;
}
printf("\n");
}
}
运行 并构建如下图所示的邻接表:
运行结果如下:
文章来源:https://www.toymoban.com/news/detail-768490.html
总结
文章来源地址https://www.toymoban.com/news/detail-768490.html
到了这里,关于C语言 图的建立(邻接矩阵与邻接表)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!