V2 Q V3 V6 Ve V3 若将图的每条边都赋上一个权,则称这种带权图为网 络( Network)。通常权是具有某种意义的数
若将图的每条边都赋上一个权，则称这种带权图为网 络(Network)。通常权是具有某种意义的数
它们可以表示两个顶点∩ 之间的距离,耗费等
它们可以表示两个顶点 之间的距离，耗费等
图的存储结构 邻接矩阵( Adjacency Maix)是表示顶点之 间相邻关系的矩阵。 设G=(V,E)是具有n 个顶点的图,则G的 A[j={若(n,y)或<,>是E(G)中的边 0:若(v,)或<,”>不是E(G)中的边 邻接矩阵是具有如下 性质的n阶方阵:
图的存储结构 • 邻接矩阵(Adjacency Matrix)是表示顶点之 间相邻关系的矩阵。 设G＝(V，E)是具有n 个顶点的图，则G的 邻接矩阵是具有如下 性质的n阶方阵： = ：若（ ）或 不是 （ ）中的边 ：若（ ）或 是 （ ）中的边 v v v v E G v v v v E G i j i j i j i j 0 , , 1 , , A i, j
用邻接矩阵表示法表示图,除了存储用于表示顶点间 相邻关系的邻接矩阵外,通常还需要用一个顺序表来 存储顶点信息。其形式说明如下 t define n 6 /*图的顶点数*/ f define e 8 /*图的边(弧)数* typedef char vextype;/*顶点的数据类型*/ typedef float adjtype;/*权值类型*/ typedef struct i vextype vex[n] adjtype arcs]: igraph
• 用邻接矩阵表示法表示图，除了存储用于表示顶点间 相邻关系的邻接矩阵外，通常还需要用一个顺序表来 存储顶点信息。其形式说明如下： • # define n 6 / * 图的顶点数 * / • # define e 8 / * 图的边（弧）数 */ • typedef char vextype； / * 顶点的数据类型 * / • typedef float adjtype； / * 权值类型 * / • typedef struct • {vextype vexs[n]； • adjtype arcs[n][n]； • }graph；
若图中顶点信息是0至n-1的编号,则仅需令权值为1,存储一个邻接矩阵就可以表 示图。若是网络,则 ditype为权的类型。由于无向图或无向网络的邻接矩阵是对 称的,故可采用压缩存储的方法,仅存储下三角阵(不包括对角线上的元素)中的 元素即可。显然,邻接矩阵表示法的空间复杂度S(n)=O(n2)。 CREATGRAPH(ga)/*建立无向网络* Graph* ga int 1, j, k: float w for(i=0: i<n: i++) ga->vexs[i]= getchar;/*读入顶点信息,建立顶点表*/ for(i=0: i<n; i++) for(j=0; j<n; j++) >arcs[i[]=0;/*邻接矩阵初始化*/ for(k=0:k<e;k++)/*读入e条边* ( scanf(%d%d%6f,&L8j,&w);/*读入边(v,y)上的权w*/ ga->arcs[]=W; ga->arcs=W; 1/*CREATGRAPH * 该算法的执行时间是O(n+n2+e),其中O(n2)的时问耗费在邻接矩阵的初始化操作上。 因为e<n2,所以,算法的时间复杂度是O(n2)
• 若图中顶点信息是0至n-1的编号，则仅需令权值为1，存储一个邻接矩阵就可以表 示图。若是网络，则adjtype为权的类型。由于无向图或无向网络的邻接矩阵是对 称的，故可采用压缩存储的方法，仅存储下三角阵(不包括对角线上的元素)中的 元素即可。显然，邻接矩阵表示法的空间复杂度S(n)＝O(n2 )。 • CREATGRAPH(ga) ／* 建立无向网络 * ／ • Graph * ga； • { • int i，j，k； • float w； • for(i＝0；i＜n；i++) • ga ->vexs[i]＝getchar()；／* 读入顶点信息，建立顶点表 *／ • for(i＝0；i＜n；i++) • for(j＝0；j＜n；j++) • ga ->arcs[i][j]＝0； ／* 邻接矩阵初始化*／ • for(k＝0；k＜e；k++) ／* 读入e条边 *／ • (scanf(”％d％d％f”，&I,&j，&w)；／*读入边(vi，vj )上的权w *／ • ga ->arcs[i][j]＝w； • ga - >arcs[j][i]＝w； • } • }／*CREATGRAPH *／ • 该算法的执行时间是O(n+n2+e)，其中O(n2 )的时问耗费在邻接矩阵的初始化操作上。 因为e＜n 2，所以，算法的时间复杂度是O(n2 )