1、数据结构与算法分析第六章 图（ 1）6.1. 图的基本概念 图的定义：图是由顶点集合 (vertex)及顶点间的关系集合组成的一种数据结构： Graph ( V, E )其中，V = x | x 某个数据对象 是顶点的有穷非空集合；E = (x, y) | x, y V 或E = | x, y V是顶点之间关系的有穷集合，也叫做边 (edge)集合。n 若图 G的每条边都是没有方向的，则称 G为无向图（UnDigraph) ，图中两个顶点间最多只存在一条边。无向边用两个顶点的无序对表示，记为 (顶点 x,顶点 y）下图为例子：n V(G1) =0,1,2,3,4n E(G1) =(0,1),(
2、0,2),(0,3), (0,4), (1,2), (1,3), (2,4)01 23 4无向图 G1无向图有向图n 若图 G的每条边都有方向，则称 G为有向图（ Digraph)。n 有向边（即弧）由两个顶点组成的有序对来表示，记为 （也可称 ）。举例：n V(G2)=0,1,2,3,4n E(G2)=,10 23 4有向图 G2 网络n 若将图中的每条边都有一个数与之关联，则称该数为边或弧的权，并称这种带权的图为网络 (Network)。n 通常权是一个具有某种意义的数（如表示两顶点间的距离、耗费等）。n V(G2)=0,1,2,3n E(G2)=,01 325 281 3网络边和顶点之间
3、的关系1. 无向图：顶点数 n和边数 e满足 : 0 e n(n-1)/2。如果e=n(n-1)/2,则该有向图为完全无向图2. 有向图：顶点数 n和边数 e满足 0 e n(n-1)。如果 e=n(n-1)，则该图为完全有向图3. 如果 e是一条有向边，则称 vi 邻接到 vj ，或称 vj 邻接于 vi；并称边 关联于顶点 vi 和 vj ，或称边 与 vi 和 vj 相关联。 图 G2中， 边 G2，称 顶 点 4邻 接到 2， 边 与 顶 点 4和 2关 联邻 接与关 联01 23 4无向图 G110 23 4有向图 G2 度1. 无向图中顶点 v 的度（ Degree）是关联于该顶点
4、的边的数目，或与该顶点相邻的顶点数目，记为 D（ v）。2. 若 G 是有向图，则把邻接到顶点 v 的顶点数目或边数目称为顶点 v 的入度（ Indegree），记为 ID（ v）；把邻接于顶点 v 的顶点数目或边数目称为顶点 v 的出度（ Outdegree），记为 OD（ v）；顶点 v 的度则定义为该顶点的入度和出度之和，即 D（ v） = ID（ v） + OD（ v）3. 无论是有向图还是无向图，顶点数 n 、边数 e 和度数之间的关系为：e = ni=0D( v i )/2路径1. 在无向图 G 中，若存在一个顶点序列 vp ,vi1 , vi2 , vim ,vq ，使得 （ v
5、p ,vi1） ,（ vi1 ,vi2） , , （ vim ,vq ） E(G)，则称顶点序列（ vp ,vi1） ,（ vi1 ,vi2） , , （ vim ,vq ） E(G) 为从 vp到 vq的一条（ Path）。2. 在有向图 G 中，若存在一个顶点序列 vp ,vi1 , vi2 , vim ,vq ，使得有向边 , , , E(G)，则称顶点 vp路到 vq有一条有向路径（ Path）。3. 无权图的路径长度是指此路径上边的条数。4. 有权图的路径长度是指路径上各边的权之和。5. 简单路径：若路径上各顶点 vp ,vi1 , vi2 , vim ,vq 均不互相同 , 则称这样的路径为简单路径。6. 环：若简单路径长度大于 2，且第一个顶点 v1 与最后一个顶点 vm 重合 , 则称这样的简单路径为回路或环。
