当前位置：首页 > news >正文

《数据结构（C语言版）第二版》第六章-图（6.4 图的存储结构——6.4.1 邻接矩阵）

news 来源：原创 2024/9/18 8:43:19

无向图UDG、有向图DG：
最大顶点个数为MVNum(100)，顶点数据类型为VerTexType(char)；边的权值的极大值∞为Maxint(32767)，边的权值类型为ArcType(int)
//邻接矩阵存储表示，结构
{一维数组顶点表vexs ，内存大小为最大顶点个数MVNum；二维数组邻接矩阵arcs，阶数为最大顶点个数MVNum，不存在的边权值为0（初始化值），存在的边权值全部为1；顶点个数为vexnum；边数为arcnum；
}AMGraph

无向网UDN、有向网DN：
最大顶点个数为MVNum(100)，顶点数据类型为VerTexType(char)；边的权值的极大值∞为Maxint(32767)，边的权值类型为ArcType(int)
//邻接矩阵存储表示，结构
{一维数组顶点表vexs，内存大小为最大顶点个数MVNum；二维数组邻接矩阵arcs，阶数为最大顶点个数MVNum，不存在的边权值为∞（初始化值），存在的边权值为Wi；顶点个数为vexnum；边数为arcnum；
}AMGraph

采用邻接矩阵表示法创建无向网

//算法6.1 采用邻接矩阵表示法创建无向网#include <stdio.h>
#include <stdlib.h>#define MaxInt 32767
#define MVNum 100typedef char VerTexType;
typedef int ArcType;typedef struct
{VerTexType vexs[MVNum];ArcType arcs[MVNum][MVNum];int vexnum;int arcnum;
}AMGraph;void CreateUDN(AMGraph& G);
int LocateVex(AMGraph& G, VerTexType v);
void printfAMGraph(AMGraph& G);int main()
{AMGraph G = {  {'\0'}, {0}, 0, 0};CreateUDN(G);printfAMGraph(G);return 0;
}void CreateUDN(AMGraph& G) 
{int i = 0;int j = 0;int k = 0;VerTexType v1 = '\0';VerTexType v2 = '\0';ArcType w = 0;printf("请输入无向网的总顶点数：");scanf_s(" %d", &G.vexnum);printf("请输入无向网的总边数：");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点储存的元素：", i + 1);scanf_s(" %c", &G.vexs[i],sizeof(VerTexType));}//初始化邻接矩阵，将边的权值均置为极大值MaxIntfor (i = 0; i < G.vexnum; ++i){for (j = 0; j < G.vexnum; ++j){G.arcs[i][j] = MaxInt;}}//构造邻接矩阵for (k = 0; k < G.arcnum; ++k){printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车） : ", k+1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType)); //scanf_s函数中在读取的内容前面，不能有除空格之外的其它内容printf("请输入第%d条边的权值 : ", k + 1);scanf_s(" %d", &w, sizeof(ArcType));i = LocateVex(G, v1);j = LocateVex(G, v2);G.arcs[i][j] = w;G.arcs[j][i] = G.arcs[i][j];}
}//在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
int LocateVex(AMGraph &G,VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.vexs[i] != v); ++i){;}return i;
}//打印邻接矩阵表示法中的顶点表vexs和邻接矩阵arcs
void printfAMGraph(AMGraph& G)
{int i = 0;int j = 0;printf("各顶点为：");for (i = 0; i < G.vexnum; i++){printf("%c ", G.vexs[i]);}printf("\n邻接矩阵为：\n");for (i = 0; i < G.vexnum; i++){for (j = 0; j < G.vexnum; j++){if (G.arcs[i][j] == 32767){printf("%d  ", G.arcs[i][j]);}else{printf("%d      ", G.arcs[i][j]);}}printf("\n");}
}

在这里插入图片描述

采用邻接矩阵表示法创建无向图

//采用邻接矩阵表示法创建无向图void CreateUDG(AMGraph& G) 
{int i = 0;int j = 0;int k = 0;VerTexType v1 = '\0';VerTexType v2 = '\0';ArcType w = 0;printf("请输入无向图的总顶点数：");scanf_s(" %d", &G.vexnum);printf("请输入无向图的总边数：");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点储存的元素：", i + 1);scanf_s(" %c", &G.vexs[i],sizeof(VerTexType));}//初始化邻接矩阵，将边的权值均置为0for (i = 0; i < G.vexnum; ++i){for (j = 0; j < G.vexnum; ++j){G.arcs[i][j] = 0;}}//构造邻接矩阵for (k = 0; k < G.arcnum; ++k){printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车） : ", k+1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);G.arcs[i][j] = 1;  //存在的边权值均为1G.arcs[j][i] = G.arcs[i][j];}
}

在这里插入图片描述

一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。

不改变图中每个顶点的命名方式，也不改变图的边（每条边的起终点），仅改变边的输入次序时，图的邻接矩阵不会发生变化。
因为图中的顶点没变，边也没变，构造邻接矩阵时，最终输入的边及其起点、终点都不会发生变化。即寻找并给邻接矩阵元素A[i][j]赋值时，行列下标及A[i][j]都不会发生变化，因此图的邻接矩阵也不会发生变化。
边输入次序的改变仅会引起构造邻接矩阵时，矩阵中元素的产生次序。

在这里插入图片描述

采用邻接矩阵表示法创建有向网

//采用邻接矩阵表示法创建有向网
void CreateDN(AMGraph& G) 
{int i = 0;int j = 0;int k = 0;VerTexType v1 = '\0';VerTexType v2 = '\0';ArcType w = 0;printf("请输入有向网的总顶点数：");scanf_s(" %d", &G.vexnum);printf("请输入有向网的总边数：");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点储存的元素：", i + 1);scanf_s(" %c", &G.vexs[i],sizeof(VerTexType));}//初始化邻接矩阵，将边的权值均置为极大值MaxIntfor (i = 0; i < G.vexnum; ++i){for (j = 0; j < G.vexnum; ++j){G.arcs[i][j] = MaxInt;}}//构造邻接矩阵for (k = 0; k < G.arcnum; ++k){printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车） : ", k+1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));printf("请输入第%d条边的权值 : ", k + 1);scanf_s(" %d", &w, sizeof(ArcType));i = LocateVex(G, v1);j = LocateVex(G, v2);G.arcs[i][j] = w;}
}

在这里插入图片描述

采用邻接矩阵表示法创建有向图

//采用邻接矩阵表示法创建有向图void CreateDG(AMGraph& G) 
{int i = 0;int j = 0;int k = 0;VerTexType v1 = '\0';VerTexType v2 = '\0';ArcType w = 0;printf("请输入有向图的总顶点数：");scanf_s(" %d", &G.vexnum);printf("请输入有向图的总边数：");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点储存的元素：", i + 1);scanf_s(" %c", &G.vexs[i],sizeof(VerTexType));}//初始化邻接矩阵，将边的权值均置为0for (i = 0; i < G.vexnum; ++i){for (j = 0; j < G.vexnum; ++j){G.arcs[i][j] = 0;}}//构造邻接矩阵for (k = 0; k < G.arcnum; ++k){printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车） : ", k+1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);G.arcs[i][j] = 1;}
}