用邻接矩阵表示图,很容易判定任意两个顶点 之间是否有边相连,并求得各个顶点的度数。对于 无向图,顶点v的度数是邻接矩阵中第行或第冽值 为1的元素个数,即: D(v)=∑4,=∑4,]…(82) 对于有向图,邻接矩阵中第值为1的元素个 数为顶点v的出度,第列值为1的元素的个数为顶 点v的入度,即: OD(v)=∑4n;|D(v)=∑41(8-3)
用邻接矩阵表示图，很容易判定任意两个顶点 之间是否有边相连，并求得各个顶点的度数。对于 无向图，顶点vi的度数是邻接矩阵中第i行或第i列值 为1的元素个数，即： D（vi）= = …（8-2） − = 1 0 [ , ] n j A i j − = 1 0 [ , ] n j A j i 对于有向图，邻接矩阵中第i行值为1的元素个 数为顶点vi的出度，第i列值为1的元素的个数为顶 点vi的入度，即： OD（vi）= ; ID（v i） = … （8-3） − = 1 0 [ , ] n j A i j − = 1 0 [ , ] n j A j i
网络的邻接矩阵 当G=(∨,E)是一个网络时,G的邻接矩阵是具 有如下性质的η阶方阵 W当(v,y)或<v,>∈E(G) A[,j{0当(w,y)或M,E(G)且问 ∞当(M,y)或M,y>E(G)且 其中W表示边上的权值;∞表示一个计算机允 许的、大于所有边上权值的数
二、网络的邻接矩阵 当G=（V，E）是一个网络时，G的邻接矩阵是具 有如下性质的n阶方阵： Wij 当（vi，vj）或< vi，vj >E（G） 0 当（vi，vj）或< vi，vj >E（G）且i=j ∞ 当（vi，vj）或< vi，vj > E（G）且i≠j A[i，j]= 其中Wij表示边上的权值；∞表示一个计算机允 许的、大于所有边上权值的数
网络的邻接矩阵示例 56 78 6450 0563478 50 560∞∞ 3 0∞45 34∞025 6400 78∞250 (a)G的邻接矩阵 (b)G的邻接矩阵 图8.8网络邻接矩阵示例
V0 V1 V3 V2 34 56 78 25 V0 V1 V2 45 64 50 网络的邻接矩阵示例 0 56 34 78 56 0 ∞ ∞ 34 ∞ 0 25 78 ∞ 25 0 0 ∞ 50 0 ∞ 45 64 ∞ 0 A3= A4= （a）G7的邻接矩阵 （b）G8的邻接矩阵 图8.8 网络邻接矩阵示例
邻接矩阵存储结构 文件名 mgraph. h # define fIniTy5000/此处用5000代表无穷大* define m 20 /最大顶点数* typedef char vertextype;/顶点值类型* typedef int edgetype;/权值类型 typedef structi vertextype veX[m];/顶点信息域 edgetype edges[m[m];/*邻接矩阵* ntn,e;/图中顶点总数与边数* } mgraph;/*邻接矩阵表示的图类型*
邻接矩阵存储结构 #define FINITY 5000 /*此处用5000代表无穷大*/ #define m 20 /*最大顶点数*/ typedef char vertextype; /*顶点值类型*/ typedef int edgetype; /*权值类型*/ typedef struct{ vertextype vexs[m]; /*顶点信息域*/ edgetype edges[m][m]; /*邻接矩阵*/ int n,e; /*图中顶点总数与边数*/ } mgraph; /*邻接矩阵表示的图类型*/ 文件名:mgraph.h
/★*★为★实★★大火为为★★实实★★实★为为★★大*实★★为实实兴为实★火*实★★★★ 图的邻接矩阵创建算法 /*文件名:c_zc函数名: creatmgraph10* 大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大 #include <stdio. h> #include "mgraph. h void creatmgraph 1 (mgraph *g) int i,j, k,w;/建立有向网络的邻接矩阵存储结构*/ printf("please input n and e: In") scanf(%d%d",&g->n,.&g->e);/输入图的顶点数与边数* getchar 取消输入的换行符 printf("please input veXs: n)
/*********************************************************/ /* 图的邻接矩阵创建算法 */ /* 文件名：c_ljjz.c 函数名：creatmgraph1() */ /*********************************************************/ #include <stdio.h> #include "mgraph.h" void creatmgraph1(mgraph *g) {int i,j,k,w; /*建立有向网络的邻接矩阵存储结构*/ printf("please input n and e:\n"); scanf("%d%d",&g->n,&g->e); /*输入图的顶点数与边数*/ getchar(); /*取消输入的换行符*/ printf("please input vexs:\n");