路径长度非带权图的路径长度是指此路径 上边的条数。带权图的路径长度是指略径 上各边的权之和。 简单路径着路径上各顶点η,V2y…,Vm均不 互相重复,则称这样的路径为简单路径。 回路若路径上第一个顶点v与最后一个 顶点vn重合,则称这样的路径为回路或环。 0 (0 2 3 3
◼ 路径长度 非带权图的路径长度是指此路径 上边的条数。带权图的路径长度是指路径 上各边的权之和。 ◼ 简单路径 若路径上各顶点 v1 ,v2 ,...,vm 均不 互相重复, 则称这样的路径为简单路径。 ◼ 回路 若路径上第一个顶点 v1 与最后一个 顶点vm 重合, 则称这样的路径为回路或环。 0 1 2 3 0 1 2 3 0 1 2 3
连通图与连通分量在无向图中,若从顶点 v到顶点v有路径,则称顶点v与v2是连通 的。如果图中任意一对顶点都是连通的,则 称此图是连通图。非连通图的极大连通子 图叫做连通分量。 强连通图与强连通分量在有向图中,若对 于每一对顶点w和v都存在一条从v到v和 从v到v的路径,则称些图是强连通图。非 强连通图的极大强连通子图叫做强连通分 量 生成树一个连通图的生成树是其极小连 通子图,在n个顶点的情形下,有n-1条边
◼ 连通图与连通分量 在无向图中, 若从顶点 v1到顶点v2有路径, 则称顶点v1与v2是连通 的。如果图中任意一对顶点都是连通的, 则 称此图是连通图。非连通图的极大连通子 图叫做连通分量。 ◼ 强连通图与强连通分量 在有向图中, 若对 于每一对顶点vi和vj , 都存在一条从vi到vj和 从vj到vi的路径, 则称此图是强连通图。非 强连通图的极大强连通子图叫做强连通分 量。 ◼ 生成树 一个连通图的生成树是其极小连 通子图，在n个顶点的情形下，有n-1条边
图的存储表示 邻接矩阵( Adjacency Matrix) 在图的邻接矩阵表示中,有一个记录各个 顶点信息的顶点表,还有一个表示各个顶 点之间关系的邻矩阵。 设图A=(V,E)是一个有n个顶点的图,图 的邻接矩阵是一个二维数组 A eugeniin 定义: AEg[/={0 若<ij>∈E或(ij∈E 10,否则
图的存储表示 ◼ 在图的邻接矩阵表示中，有一个记录各个 顶点信息的顶点表，还有一个表示各个顶 点之间关系的邻接矩阵。 ◼ 设图 A = (V, E)是一个有 n 个顶点的图, 图 的邻接矩阵是一个二维数组A.edge[n][n]， 定义： 邻接矩阵 (Adjacency Matrix) = , , , ( , ) . [ ][ ] 否 则 若 或 0 1 < > A i j E i j E Edge i j
④0 ①OA.edge 0101 ③3 1010 「010 Aedge=1 0 1 1000 无向图的邻接矩阵是对称的; 有向图的邻接矩阵可能是不对称的
◼ 无向图的邻接矩阵是对称的; ◼ 有向图的邻接矩阵可能是不对称的。 0 1 2 3 = 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 A.edge 0 1 2 = 0 0 0 1 0 1 0 1 0 A.edge
在有向图中,统计第i行1的个数可得顶点 i的出度,统计第j列1的个数可得顶点j 的入度。 在无向图中,统计第i行(列1的个数可得 顶点的度。 网络的邻接矩阵 W(,j若i≠诅且<,j>∈E或(i,j)∈E Adge证门={∞ 若法≠<;j>E或ij∈E 若i==j
◼ 在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 列 1 的个数可得顶点 j 的入度。 ◼ 在无向图中, 统计第 i 行 (列) 1 的个数可得 顶点i 的度。 网络的邻接矩阵 = = = i j i j i , j i , j i j i j i , j i , j i j 若 若 且 或 若 且 或 , , ( ) ( , ), ( ) [ ][ ] 0 E E W E E A.edge