用邻接矩阵表示图,很容易判定任意两个顶点 之间是否有边相连,并求得各个顶点的度数。对于 无向图,顶点v的度数是邻接矩阵中第i行或第例值 为1的元素个数,即: D()=∑4门=∑41…(82) 对于有向图,邻接矩阵中第行值为1的元素个 数为顶点v的出度,第冽值为1的元素的个数为顶 点v的入度,即 OD(v)=∑4n;|()=∑41…(83)
用邻接矩阵表示图，很容易判定任意两个顶点 之间是否有边相连，并求得各个顶点的度数。对于 无向图，顶点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=(V,E)是一个网络时,G的邻接矩阵是具 有如下性质的η阶方阵: 当(W,y)或<M,>∈E(G) A[,j{0当(w,y)或<M,=E(G)且 当(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表示边上的权值；∞表示一个计算机允 许的、大于所有边上权值的数
网络的邻接矩阵示例 5678 6450 V45<V 0563478 0 50 560 0 45 34∞025 6400 780250 (a)G的邻接矩阵 (b)G。的邻接矩阵 图88网络邻接矩阵示例
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 /最大顶点数 pede char vertextype;/顶点值类型 typedef int edgetype;/权值类型 typedef struct vertextype vex[m];/顶点信息域 edgetype edges[]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");