第7章 图.ppt

第7章图
数据结构(C++描述)
目录

图的基本概念
图的存贮结构
图的遍历
生成树和最小生成树

退出
图的基本概念
图的定义
图是由顶点集V和顶点间的关系集合E(边的集合)组成的一种数据结构,可以用二元组定义为:G=(V,E)。
例如,对于图7-1所示的无向图G1和有向图G2,它们的数据结构可以描述为:G1=(V1,E1), 其中 V1={a,b,c,d},E1={(a,b),(a,c),(a,d),(b,d),(c,d)},而G2=(V2,E2),其中V2={1,2,3}, E2={<1,2>,<1,3>,<2,3>,<3,1>}。
图的基本术语
1. 有向图和无向图
在图中,若用箭头标明了边是有方向性的,则称这样的图为有向图,否则称为无向图。如图7-1中,G1为无向图,G2为有向图。
在无向图中,一条边(x,y)与(y,x)表示的结果相同,用圆括号表示,在有向图中,一条边<x,y>与<y,x>表示的结果不相同,故用尖括号表示。〈x,y>表示从顶点x发向顶点y的边,x为始点,y为终点。有向边也称为弧,x为弧尾,y为弧头,则〈x,y>表示为一条弧,而〈y,x>表示y为弧尾,x为弧头的另一条弧。
2. 完全图、稠密图、稀疏图
具有n个顶点,n(n-1)/2条边的图,称为完全无向图,具有n个顶点,n(n-1) 条弧的有向图,称为完全有向图。完全无向图和完全有向图都称为完全图。
对于一般无向图,顶点数为n,边数为e,则 0≤e ≤n(n-1)/2。
对于一般有向图,顶点数为n,弧数为e, 则 0≤e≤n(n-1) 。
当一个图接近完全图时,则称它为稠密图,相反地,当一个图中含有较少的边或弧时,则称它为稀疏图。
3. 度、入度、出度
在图中,一个顶点依附的边或弧的数目,称为该顶点的度。在有向图中,一个顶点依附的弧头数目,称为该顶点的入度。一个顶点依附的弧尾数目,称为该顶点的出度,某个顶点的入度和出度之和称为该顶点的度。
另外,若图中有n个顶点,e条边或弧,第i个顶点的度为di,则有e=
4. 子图
若有两个图G1和G2, G1=(V1,E1), G2=(V2,E2), 满足如下条件: V2V1 ,E2 E1,即V2为V1的子集,E2为E1的子集,称图G2为图G1的子图。
图和子图的示例具体见图7-2。
5. 权
在图的边或弧中给出相关的数,称为权。权可以代表一个顶点到另一个顶点的距离,耗费等,带权图一般称为网。
带权图的示例具体见图7-3。
6. 连通图和强连通图
在无向图中,若从顶点i到顶点j有路径,则称顶点i和顶点j是连通的。若任意两个顶点都是连通的,则称此无向图为连通图,否则称为非连通图。
连通图和非连通图示例见图7-4。
在有向图中,若从顶点i到顶点j有路径,则称从顶点i和顶点j是连通的,若图中任意两个顶点都是连通的,则称此有向图为强连通图,否则称为非强连通图。
强连通图和非强连通图示例见图7-5。
7. 连通分量和强连通分量
无向图中,极大的连通子图为该图的连通分量。显然,任何连通图的连通分量只有一个,即它本身,而非连通图有多个连通分量。
对于图7-4 中的非连通图,它的连通分量见图7-6。