3 图6a生通图 图6-30生通图 33 图63C图的公量 图63无向图的连通性示意 武汉理工人字华夏字阮-信息工程 系
武汉理工大学华夏学院-信息工程 系 2 1 4 1 3 6 2 5 2 5 1 3 4 图6－３（ａ）连通图 图6－３（ｂ）非连通图 图6－３（ｃ）非连通图的连通分量 图6－３无向图的连通性示意 3 4 6
10.有根图在有向图中,若存在一个顶点G, 从该顶点出发,可以沿着有向路径到达图中其余 的所有顶点,则称该图为有根图,顶点G为有根 图的根。例如:图6-4为一个有根图。 1.与网络当图中的每一亲边都对应着一个 ≥数值,这个数值称为该边的权,在实际应用中可 以用权来表示距离、造价等;对这种每条边上都 带有权值的图称为网络。 例如:图6-5表示了一个网络图。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 10. 有根图 在有向图中，若存在一个顶点G， 从该顶点出发，可以沿着有向路径到达图中其余 的所有顶点，则称该图为有根图，顶点G为有根 图的根。例如：图6-4为一个有根图。 11.权与网络 当图中的每一条边都对应着一个 数值，这个数值称为该边的权，在实际应用中可 以用权来表示距离、造价等；对这种每条边上都 带有权值的图称为网络。 例如：图6-5表示了一个网络图
私根 图6-4有根图 D B 二图6-5网络图 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 A D B C 树根 图6－４有根图 A D B 2 C 7 4 8 9 图6－5网络图
62图的存储表示 图的存储表示方法有很多,例如用存储树的 方法可以存储图,这里只介绍两种常用方法。 6.2.1邻接矩阵 邻接矩阵是用来表示图中顶点之间的邻接关 系的矩阵 定义:对于有N个顶点的图的邻接矩阵是一 个N×N的方阵C,其中C[(0<IJ<=N)的值 是这样确定的: 当顶点对顶点边相连时C[]的值为1,当 顶点对顶点无边相连时c[IJ的值为0。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 6.2 图的存储表示 图的存储表示方法有很多，例如用存储树的 方法可以存储图，这里只介绍两种常用方法。 6.２.１ 邻接矩阵 邻接矩阵是用来表示图中顶点之间的邻接关 系的矩阵。 一、定义：对于有N个顶点的图的邻接矩阵是一 个N×N的方阵C，其中C[I,J]（0<I,J<=N)的值 是这样确定的： 当顶点I对顶点J有边相连时C[I,J]的值为１，当 顶点I对顶点J无边相连时C[I,J]的值为０
例如:图6-1(a)所示的有向图的邻接矩阵为 A B 上图的邻接矩阵为 A B C 出度 A011 BcD 0 000 0 D1000 3201 3 入度 武汉理工大学华夏学院信息工程<心心 系
武汉理工大学华夏学院-信息工程 系 上图的邻接矩阵为 A B C D 出度 A 0 1 1 1 ３ B 1 0 1 0 ２ C 0 0 0 0 ０ D 0 0 1 0 １ １ １ ３ １ 入度 A D C B 例如：图6-1（ａ）所示的有向图的邻接矩阵为：