第06章 图.ppt

引入
《数据结构(C#语言描述)》配套PPT
线性表中的元素是“一对一”的关系,树中的元素是“一对多”的关系,本章所讲述的图形结构中的元素则是“多对多”的关系。图(Graph)是一种复杂的非线性数据结构,在图形结构中,每个元素可以有零个或多个前驱,也可以有零个或多个后继,也就是说,元素之间的关系是任意的。
基本概念和术语
《数据结构(C#语言描述)》配套PPT
一个图(Graph)是由顶点(Vertex)集V和边(Edge,又称为弧)集E组成的。,在括号中使用逗号分隔的两个顶点来表示一个边,如(V1,V2 )。
顶点集V(G) = {V1,V2,V3,V4}
边集 E(G) = { (V1,V2 ),(V1,V3 ),(V1,V4 ),(V2,V4 ) }
V1
V3
V2
V4
基本概念和术语
《数据结构(C#语言描述)》配套PPT
V1
V3
V2
V4
V1
V3
V2
无向图:若图中所有边的两个顶点没有次序关系和方向性,即(V1,V2)和(V2,V1)代表的是同一条边,则称为无向图。
有向图:若图中两个顶点存在次序关系和方向性,即<V1,V2>和<V2,V1>代表的是两条不同的边,则称为有向图。
基本概念和术语
《数据结构(C#语言描述)》配套PPT
完全图:在一个无向图中,如果任意两顶点都有一条边直接连接,则称该图为完全无向图。在一个有向图中,如果任意两顶点都存在着方向相反的两条边,则称此图为完全有向图。
当一个图接近完全图时,则称它为稠密图(Dense Graph),当一个图含有较少的边数时,则称为稀疏图(Sparse Graphs)。
V1
V3
V2
V4
V1
V3
V2
基本概念和术语
《数据结构(C#语言描述)》配套PPT
顶点的度(Degree):顶点Vi的度是指在图中与Vi相关联的边的条数。对于有向图来说,有入度(In-degree)和出度(Out-degree)之分,有向图顶点的度等于该顶点的入度和出度之和。
邻接(Adjacent):若无向图中的两个顶点V1和V2存在一条边(V1,V2 ),则称顶点V1和V2相邻。在有向图中存在一条边< V3,V2>,则称顶点V3与顶点V2邻接,且是V3邻接到(to) V2或V2邻接自(from) V3。
V1
V3
V2
V4
V1
V3
V2
基本概念和术语
《数据结构(C#语言描述)》配套PPT
子图(Subgraph):设有两个图G = (V,E)和G’= (V’,E’),若V’是V的子集,且E’是E的子集,则称G’是G的子图。
(a)
A
B
C
D
(b)
A
B
D
(c)
B
C
D
基本概念和术语
《数据结构(C#语言描述)》配套PPT
路径(Path):在无向图中,若从顶点Vi出发有一组边可到达顶点Vj,则称顶点Vi到顶点Vj的顶点序列为从顶点Vi到顶点Vj的路径。
A
B
C
D
E
A
B
C
D
E
基本概念和术语
《数据结构(C#语言描述)》配套PPT
连通(Connected):若从Vi到Vj有路径可通,则称顶点Vi和顶点Vj是连通的。
连通图(Connected Graph):在无向图中任意两个结点都有路径相通的,称为连通图。只要有两个结点无路径相通,则称为非连通图。图中的极大连通子图称为连通分量。
(a)
A
B
C
D
E
F
(b)
A
B
C
D
E
F
基本概念和术语
《数据结构(C#语言描述)》配套PPT
强连通图(Strongly Connected Graph):在有向图中,若任意一对不同的顶点Vi和Vj都存在从Vi到Vj及Vj到Vi的路径,则称为强连通图。有向图中极大的强连通子图称为它的强连通分量。
B
C
D
(a)
A
C
(b)
A
B
D
(c)
基本概念和术语
《数据结构(C#语言描述)》配套PPT
权(Weight):图的边有时会包含具有某种特定含义的数据信息,这些附带的数据信息称为权。权可以表示实际问题中从一个顶点到另一个顶点的距离、花费代价、所需时间等。带权的图也称作网络或网。
809
1810
1371
1325
1205
北京
上海
南宁
广州
武汉