10.权和网 图中每一条边都可以附有一个对应的数值这种与 边相关的数值称为权。权可以表示从一个顶点到另一个 顶点的距离或花费的代价。边上带有权的图称为带权图, 也称作网
10. 权和网 图中每一条边都可以附有一个对应的数值,这种与 边相关的数值称为权。权可以表示从一个顶点到另一个 顶点的距离或花费的代价。边上带有权的图称为带权图, 也称作网
例91有n个顶点的有向强连通图最多需要多少条边? 最少需要多少条边? 答:有n个顶点的有向强连通图最多有n(n-1)条边 (构成一个有向完全图的情况);最少有n条边(n个顶点 依次首尾相接构成一个环的情况)
例9.1 有n个顶点的有向强连通图最多需要多少条边？ 最少需要多 少条边？ 答：有n个顶点的有向强连通图最多有n(n-1)条边 (构成一个有向完全图的情况)；最少有n条边(n个顶点 依次首尾相接构成一个环的情况)
9.2图的存储结构 9.2.1邻接矩阵存储方法 邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是 具有n(n>0)个顶点的图顶点的顺序依次为vy1…,ym.则G的 邻接矩阵4是m阶方阵其定义如下: (1)如果G是无向图则: A[il[i=1:若(v,v)∈E(G)0:其他 (2)如果G是有向图则: Ail=1:若wpy>∈E(G)0其他
9.2 图的存储结构 9.2.1 邻接矩阵存储方法 邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是 具有n(n＞0)个顶点的图,顶点的顺序依次为(v0 ,v1 ,…,vn-1 ),则G的 邻接矩阵A是n阶方阵,其定义如下： (1)如果G是无向图,则： A[i][j]= 1:若(vi ,vj )∈E(G) 0:其他 (2)如果G是有向图,则： A[i][j]= 1:若<vi ,vj>∈E(G) 0:其他
(3)如果G是带权无向图,则: Aiil=wn:若v内v且vyy)∈E(G)∞其他 (4)如果G是带权有向图则 Ail=wn:若v内且wy∈E(G)∞:其他
(3)如果G是带权无向图,则： A[i][j]= wij :若vi ≠vj且(vi ,vj )∈E(G) ∞:其他 (4)如果G是带权有向图,则： A[i][j]= wij :若vi ≠vj且<vi ,vj>∈E(G) ∞:其他
01011 3 0 A1=01011 1110 0110 (a) 「010101 00110 A2=0001 00000 10010
= 1 0 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 1 A1 1 2 3 0 4 1 2 3 0 4 (a) (b) = 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 A2