图的基本概念 路径长度 口非带权图的路径长度是指此路径上边的条数 口带权图的路径长度是指路径上各边的权之和 简单路径 口路径上各顶点v1V2,…,Vm均不互相重复 回路 口路径上第一个顶点v1与最后一个顶点vm重合
图的基本概念 ◼ 路径长度 非带权图的路径长度是指此路径上边的条数 带权图的路径长度是指路径上各边的权之和 ◼ 简单路径 路径上各顶点 v1 ,v2 ,...,vm均不互相重复 ◼ 回路 路径上第一个顶点 v1 与最后一个顶点vm重合 7
图的基本概念 连通图与连通分量 口无向图中,从顶点v倒到顶点v2有路径,则称顶点v1与 2是连通的。 口若图中任意一对顶点都是连通的则此图是连通图 a非连通图的极大连通子图叫连通分量 5 3 3 连通图 非连通图(有2个连通分量
图的基本概念 ◼ 连通图与连通分量 无向图中, 从顶点v1到顶点v2有路径, 则称顶点v1与 v2是连通的。 若图中任意一对顶点都是连通的, 则此图是连通图 非连通图的极大连通子图叫连通分量 8 1 2 3 0 4 连通图 5 1 2 3 0 4 非连通图(有2个连通分量) 5
图的基本概念 强连通图与强连通分量 口在有向图中若对于每一对顶点v和v都存在一条 从v到y和从到v的路径则称此图是强连通图 口非强连通图的极大强连通子图叫做强连通分量 n生成树 个连通图的生成树是其极小连通子图,在n个 顶点的情形下,有n-1条边
图的基本概念 ◼ 强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj , 都存在一条 从vi到vj和从vj到vi的路径, 则称此图是强连通图 非强连通图的极大强连通子图叫做强连通分量 ◼ 生成树 一个连通图的生成树是其极小连通子图，在 n 个 顶点的情形下，有n-1条边。 9
图的存储衰示 ■邻接矩阵 口一个有n个顶点的图G=(V,E),图的邻接矩阵 是一个二维数组 A edgell 1,若(i,j)∈E edge[il10.否则 0 010 010 Edge 010 Edge=101 2 无向图的邻接矩阵是对称的 有向图的邻接矩阵可能不对称 10
图的存储表示 ◼ 邻接矩阵 一个有 n 个顶点的图G = ( V, E )， 图的邻接矩阵 是一个二维数组A.edge[n][n] 10 1 2 0 有向图的邻接矩阵可能不对称 1 2 3 0 = 否 则 若 , , 0 1 ( , ) Edge[ ][ ] i j E i j = 0 0 0 1 0 1 0 1 0 Edge = 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 Edge 无向图的邻接矩阵是对称的
图的存储表示 ■邻接矩阵 口网络(带权图)的邻接矩阵 W(G,j),若i≠沮或,j)∈E Edge[门 若i≠沮或i)E 若i==j 6 Edge ∞092 5 3508 11
图的存储表示 ◼ 邻接矩阵 网络(带权图)的邻接矩阵 11 = = = i j i j i , j W i j i j i , j i j 若 若 且 或 若 且 或 , , ( ) ( , ), ( ) [ ][ ] 0 E E Edge = 6 0 3 5 0 8 0 9 2 0 1 4 Edge 2 3 0 1 8 6 3 9 5 2 1 4