201447 §7.1概念 s7.1概念 路径 有根田： 若存在一顶点序列y,a,a…v,使 在有向图G中，若存在v∈V,从y到其他顶点均有 (w,ahaa…,(y.y,)eE(G 路径可达，则称为根，G为有根图。 则称从到，存在一条路径。”，0 连通、连通图、联通分量 所经过的边数称为路径长度。 设G为无向图 有向路径类似定义。 ①G中，若y和y有路径，则称y和连通。 若y,yeV(Gy,和V,均连通，则G为连通图. 简单路径： 无向图中极大连通子图称为连通分量。 除起点和终点外，其余顶点均不相同的路径， 连通图只有一个连通分量，即自身。 葡单回路（环）： 起点和终点相同的筒单路径。 S7.1概念 §7.2图的存储结构 强连通图 没有前驱和后继的关系，任两结点均可能有“邻 终盟⊙，苦到及y到有 接”关系 个顶点的强连通图至少有几条边？ 无向图中，邻接点互为对称，分不清淮是前驱和 有向完全图是强连通图？ 后继。 强连通分量： 有向图中，边的起点为前驱，终点为后继，但有 有向图的极大强连通子图，称为强连通分量。 向环又如何表达？ 强连通图只有一个强连通分量。 设G中，V(G=o,…,} 例：G不是强连通图，它有两个强连通分量。 多种袁示法，重点介绍常用的两种。 加权图： 顶点、边上带权。 87.2.1邻接矩阵表示法 87.2.1邻接矩阵表示法 邻接矩阵：表示项点（数据元素）相邻关系的矩库。 类型说明 若项点值意无关赛要，则用二维数组人，表示，n=Y(G #define MaxVertex Num1oo象大顶点数 44刀-.h或<光O 否则 typedef int EdgeType;边类里 对于加权图： typedef char VertexType;项点类型 n-.以减oao typedef struct 123 Vertex Type vexsMaxVertexNum:/顶点w n10 无向图的邻接矩阵是对称的 EdgeType edges Max VertexNumMaxVertexNuml; 邻接矩阵表示法： 边表，矩阵 若顶点信惠量要，则应将其组织成一个顺序表： int血，c:顶点数，边数 边表（邻接矩阵） →邻接矩阵表示法 )MGraphi 顶点表 22014/4/7 2 §7.1 概念  路径 若存在一顶点序列 使 则称从 到 存在一条路径。 7 所经过的边数称为路径长度。 有向路径类似定义。  简单路径： 除起点和终点外，其余顶点均不相同的路径.  简单回路（环）： 起点和终点相同的简单路径。 §7.1 概念  有根图： 在有向图G中，若存在 ，从 到其他顶点均有 路径可达，则 称为根，G为有根图。  连通、连通图、联通分量 设G为无向图 8 ① G中，若 和 有路径，则称 和 连通。 ② 若 ， 和 均连通，则G为连通图。 ③ 无向图中极大连通子图称为连通分量。 连通图只有一个连通分量，即自身。 §7.1 概念  强连通图 设G是有向图， ，若 到 及 到 都有 路径，则是强连通图 n个顶点的强连通图至少有几条边？ 有向完全图是强连通图？ 强连通分量 9  ： 有向图的极大强连通子图，称为强连通分量。 强连通图只有一个强连通分量。 例：G1不是强连通图，它有两个强连通分量。  加权图： 顶点、边上带权。 §7.2 图的存储结构 没有前驱和后继的关系，任两结点均可能有“邻 接”关系  无向图中，邻接点互为对称，分不清谁是前驱和 后继。  有向图中 边的起点为前驱 终点为后继 但有 10  有向图中，边的起点为前驱，终点为后继，但有 向环又如何表达？ 设G中， 多种表示法，重点介绍常用的两种。 §7.2.1 邻接矩阵表示法  邻接矩阵：表示顶点（数据元素）相邻关系的矩阵。 若顶点信息无关紧要，则用二维数组 表示， 对于加权图： 11 无向图的邻接矩阵是对称的  邻接矩阵表示法： 若顶点信息重要，则应将其组织成一个顺序表： 边表（邻接矩阵） 顶点表 §7.2.1 邻接矩阵表示法  类型说明 #define MaxVertexNum 100 //最大顶点数 typedef int EdgeType; //边类型 typedef char VertexType; //顶点类型 t d f t t{ 12 typedef struct{ VertexType vexs[MaxVertexNum]; //顶点表 EdgeType edges[MaxVertexNum][MaxVertexNum]; //边表，邻接矩阵 int n, e; //顶点数，边数 }MGraph；