求无向图的邻接矩阵例题,图的邻接矩阵怎么求
加权无向图的邻接矩阵表示法(c语言安装)文章目录加权无向图的邻接矩阵表示法) c语言安装)一、邻接矩阵表示法二、本次程序实现的功能三、加权无向图的构造体定义四、无向图和邻接矩阵五的制作、邻接矩阵六的输出、顶点
一.邻接矩阵表示法
定义：所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。
关于http://www.Sina.com/，如果顶点Vi和Vj之间有边相连，则邻接矩阵中的对应项中存储有与该边对应的3358 www.Sina.com /，如果顶点Vi和Vj不相连，则
例如，对于下图：
我们可以得到那个邻接矩阵：
带权图
为了便于发现，加权邻接矩阵包括：关于主对角线元素对称； 非0对应位置的值为边权。
如果没有权限，则有边的对应位置为1，无边的位置为0，且关于主对角线元素对称。
二、本次程序实现的功能是建立有向图的邻接矩阵
输出与有向图对应的邻接矩阵
输出顶点集合
判断两个顶点是否相邻，即是否有直接相连的边
三.赋权有向图的结构体定义typedef char VertexType； //顶点的数据类型typedef int EdgeType； //权重图中具有边权重的数据类型typedef struct { vertextypevex [ maxvertexnum ]； //顶点表MaxVertexNum是最大顶点数，下同edgetypeedge [ maxvertexnum ] [ maxvertexnum ]； //邻接矩阵，边表int vexnum，arcnum； //图的当前顶点数和边数}MGraph； //基于邻接矩阵法的加权无向图四、无向图的制作，以及邻接矩阵比较简单，所以不多赘述。 值得注意的是，为了有效利用有向图的邻接矩阵的主对角线对称的特性，在输入边权值时只需输入上三角或下三角即可。
voidcreatemgraph(mgraph*g ) {int i，j，k，w； //请输入预先决定顶点数和边数printf () )的顶点数和边数用空格分开的：(n ) )； scanf('%d%d )、G-vexnum和G-arcnum )； flush(stdin； //如果清空输入缓冲区，则输入//逐次输入顶点值printf (可能无法正常读取() )请逐次输入顶点值：(n ) )； for(intI=0； i G-vexnum； I ) ) {printf )，i 1 )输入第%d个顶点信息：(n )，i 1 )； scanf('%c '，G-Vex[i] )； //接收值在顶点表中放入fflush(stdin )； //如果清空输入缓冲区，则可能无法正常读取输入。 //初始化邻接矩阵for (I=0； i G-vexnum； I ) for ) j=0； j G-vexnum； j ) G-Edge[i][j]=0； //开始时全部初始化为0，但用 //表示邻接矩阵for(k=0； k G-arcnum； k ) ({printf (输入边vi，vj的下标I，下标j和权重w:(n ) )； scanf(%d%d%d )、I、j、w )； //输入边vi，vj上的权重wG-Edge[i][j]=w； G-Edge[j][i]=G-Edge[i][j]； //有向图矩阵是对称的)五、输出邻接矩阵的本质是遍历二维阵列。
//邻接矩阵voidprintmatrix(mgraphg ) {int i，j； printf (邻接矩阵表示以下：(n )； for(I=0； i G.vexnum； I ) for(j=0； j G.vexnum； j ) printf('%-10d '，G.Edge[i][j]； //左对齐输出printf () (n )； (六)输出顶点集合的本质是遍历一维数组。
//输出顶点集合voidprintvex(mgraphg ) printf ) (n顶点集合为() )； for(intI=0； iG.vexnum； I ) printf('%c '，G.Vex[i]； 打印((n )； (判断七、两个顶点是否相邻接收的参数是两个顶点的值，需要在顶点表中找到其下标，判断对应位置的相邻矩阵的值是否大于0。 如果大于0，则表示相邻，否则表示不相邻。
注意：如果经常使用下标查找顶点，请考虑将其封装到另一个函数中。
//确定boolis_edge_exist(mgraphg )是否在两个顶点之间相邻，
VertexType d1, VertexType d2){int i,j,k;for(k=0;k<G.vexnum;k++){if(G.Vex[k]==d1)i = k;//找到顶点对应的下标 if(G.Vex[k]==d2)j = k;//找到顶点对应的下标}return G.Edge[i][j]>0?1:0;} 八、全部代码 #include<stdio.h>#define MaxVertexNum 10 //顶点数目的最大值#include<stdbool.h> //根据C99标准,C语言使用bool类型需要添加这个头文件typedef char VertexType; //顶点的数据类型typedef int EdgeType; //带权图中边上权值的数据类型typedef struct {VertexType Vex[MaxVertexNum]; //顶点表EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表int vexnum, arcnum; //图的当前顶点数和边数}MGraph;//基于邻接矩阵法的带权无向图 void CreateMGraph(MGraph *G){int i,j,k,w;//先确定顶点数和边数printf("请输入顶点数和边数,用空格隔开:\n");scanf("%d %d",&G->vexnum,&G->arcnum);fflush(stdin);//清空输入缓冲区,否则可能无法正常读取输入 //依次输入顶点的值printf("请依次输入顶点的值:\n");for(int i = 0;i < G->vexnum; i++){printf("输入第%d个顶点信息:\n",i+1);scanf("%c",&G->Vex[i]); //接收值放入顶点表中fflush(stdin);//清空输入缓冲区,否则可能无法正常读取输入}//初始化邻接矩阵for(i = 0;i < G->vexnum; i++)for(j = 0;j <G->vexnum; j++)G->Edge[i][j] = 0;//开始时全部初始化为0,也可以用∞ //建立邻接矩阵for (k = 0; k < G->arcnum; k++){printf("输入边<vi,vj>的下标i,下标j和权w:\n");scanf("%d%d%d", &i, &j, &w);//输入边<vi,vj>上的权值wG->Edge[i][j] = w;G->Edge[j][i] = G->Edge[i][j];//无向图矩阵是对称的}}//输出邻接矩阵 void PrintMatrix(MGraph G){int i,j;printf("邻接矩阵表示如下:\n");for (i = 0; i < G.vexnum; i++){for (j = 0; j < G.vexnum; j++)printf("%-10d", G.Edge[i][j]);//左对齐输出 printf("\n");}}//输出顶点集合void PrintVex(MGraph G) {printf("\n顶点集合为：");for(int i=0;i<G.vexnum;i++)printf("%c ",G.Vex[i]);printf("\n");}//判断两个顶点之间是否邻接 bool Is_Edge_Exist(MGraph G, VertexType d1, VertexType d2){int i,j,k;for(k=0;k<G.vexnum;k++){if(G.Vex[k]==d1)i = k;//找到顶点对应的下标 if(G.Vex[k]==d2)j = k;//找到顶点对应的下标}return G.Edge[i][j]>0?1:0;}int main(){MGraph G;//无向图 CreateMGraph(&G);//创建图 PrintMatrix(G);//输出邻接矩阵 PrintVex(G);//输出顶点 //判断两个顶点是否邻接 VertexType d1,d2;d1 = 'A';d2 = 'B';if(Is_Edge_Exist(G,d1,d2))printf("\n%c和%c邻接!\n",d1,d2);elseprintf("\n%c和%c不邻接!\n",d1,d2);d2 = 'C';if(Is_Edge_Exist(G,d1,d2))printf("\n%c和%c邻接!\n",d1,d2);elseprintf("\n%c和%c不邻接!\n",d1,d2);return 0;} 九、测试
输入示例：
输入时只需要输入上三角部分或下三角部分(不含主对角线上的)即可。