路径在图G=(V,E)中,若从顶点v出发,沿一些边 经过一些顶点v,V23…,vm,到达顶点v则称顶点 序列(V1v2…Vmv)为从顶点v到顶点y的路径。 它经过的边(vv1(V)…、(vmv应是属于E 的边。 路径长度 非带权图的路径长度是指此路径上边/弧的条数。 带权图的路径长度是指路径上各边/弧的权之和
路径 在图 G=(V, E) 中, 若从顶点 vi 出发, 沿一些边 经过一些顶点 vp1 , vp2 , …, vpm,到达顶点vj。则称顶点 序列 ( vi vp1 vp2 ... vpm vj ) 为从顶点vi 到顶点 vj 的路径。 它经过的边(vi , vp1 )、(vp1 , vp2 )、...、(vpm, vj )应是属于E 的边。 路径长度 非带权图的路径长度是指此路径上边/弧的条数。 带权图的路径长度是指路径上各边/弧的权之和
简单路径若路径上各顶点v,2…,n均不互相 重复,则称这样的路径为简单路径。 回路着路径上第一个顶点v1与最后一个顶点 vn重合,则称这样的路径为回路或环。 (a)简单路径 (b)非简单路径 (C)回路 连通图与连通分量在无向图中若从顶点v到 顶点v有路径,则称顶点v与v2是连通的。如果 图中任意一对顶点都是连通的,则称此图是连通 图。非连通图的极大连通子图叫做连通分量
简单路径 若路径上各顶点 v1 ,v2 ,...,vm 均不互相 重复, 则称这样的路径为简单路径。 回路 若路径上第一个顶点 v1 与最后一个顶点 vm 重合, 则称这样的路径为回路或环。 连通图与连通分量 在无向图中, 若从顶点v1到 顶点v2有路径, 则称顶点v1与v2是连通的。如果 图中任意一对顶点都是连通的, 则称此图是连通 图。非连通图的极大连通子图叫做连通分量
强连通图与强连通分量在有向图中,若对于每一对顶 点v和v都存在一条从w到v和从v到v的路径,则称此 是强连通图。非强连通图的极大强连通子图叫做强 连通分量。 生成树一个连通图的生成树是它的极小连通子图, 在n个顶点的情那下,有n-1条边 令生成树是对指连通图来而言的 令是连同图的极小连同子图 令包含图中的所有顶点 令有且仅有n-条边 本章不予 讨论的图 d a)带自身环的图 b)多重图
强连通图与强连通分量 在有向图中, 若对于每一对顶 点vi和vj , 都存在一条从vi到vj和从vj到vi的路径, 则称此 图是强连通图。非强连通图的极大强连通子图叫做强 连通分量。 生成树 一个连通图的生成树是它的极小连通子图, 在n个顶点的情形下,有n-1条边。 ❖ 生成树是对指连通图来而言的 ❖ 是连同图的极小连同子图 ❖ 包含图中的所有顶点 ❖ 有且仅有n-1条边 本章不予 讨论的图
72图的存储表示 1.邻接矩阵( Adjacency Matrix)表示法 (数组表示法) 顶点表:一个记录各个顶点信息的一维数组, 0邻接矩阵:一个表示各个顶点之间的关系(边 或弧)的二维数组。 设图G=(V,E是一个有n个顶点的图,则图的 邻接矩阵 G arcsIn四定义为 Garculli|1若V,vj>或(Ⅴ)∈E 0反之
7.2 图的存储表示 顶点表: 一个记录各个顶点信息的一维数组, 邻接矩阵:一个表示各个顶点之间的关系(边 或弧)的二维数组。 设图 G = (V, E)是一个有 n 个顶点的图,则图的 邻接矩阵G.arcs[n][n] 定义为: G.arcs[i][j]= 1 若<Vi,Vj> 或(Vi,Vj)∈E 0 反之 1. 邻接矩阵 (Adjacency Matrix)表示法 (数组表示法)
1)类型定义 # define maX VErTEX num20/最大顶点数 typedef int AdjMatrix MAX VERTEX NUMIIMAX VERTEX NUMB ∥接矩阵类型 typedef struct i Vertex Type vexs MAX VERTEX NUM];/顶点表 AdjMatrix arcs ∥接矩阵 int vexnum arcum /图的顶点数和弧数 } MGraph;(有四个域)
1)类型定义 #define MAX_VERTEX_NUM 20 //最大顶点数 typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵类型 typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //顶点表 AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的顶点数和弧数 } MGraph;(有四个域)