数据结构 图的基本知识点.pptx

第8章图
图的基本概念
图的基本存储结构
邻接距阵及其实现
邻接表及其实现
图的遍历
深度优先搜索遍历
广度优先搜索遍历
图的应用
连通图的最小生成树
拓扑排序
一、现实中的图
图的基本概念
图最常见的应用是在交通运输和通信网络中找出造价最低的方案。通信网络示例如下图所示:
图G是由一个顶点集V和一个边集E构成的数据结构。记为二元组形式: G= (V, E)
其中:
V是由顶点构成的非空有限集合,记为:V={V0, V1, V2, …Vn-1}
E是由V中顶点的对偶构成的有限集合,记为:E={(V0, V2), (V3, V4), …},若E为空,则图中只有顶点而没有边。
其中对偶可以表示成:
(Vi, Vj)—无序的对偶称为边,即(Vi, Vj)=(Vj, Vi) ,其图称为无向图
<Vi, Vj>—有序的对偶称为弧,即<Vi, Vj> ≠<Vj, Vi>,则称Vi为弧尾,称Vj为弧头,该图称为有向图
二、图的定义
有向图和无向图示例:
无向图G1的二元组表示:
V(G1)={V1, V2, V3, V4}
E(G1)={(V1, V2),(V1, V3),(V1, V4),(V2, V3),(V2, V4),(V3, V4)}
有向图G3的二元组表示:
V(G3)={V1, V2, V3}
E(G3)={<V1, V2>,<V1, V3>,<V2, V3>,<V3, V2>}
在无向图中,若存在一条边(Vi, Vj),则称Vi和Vj互为邻接点(Adjacent)
在有向图中,若存在一条弧<Vi, Vj >,则称Vi为此弧的起点,称Vj为此弧的终点,称Vi邻接到Vj,Vj邻接自Vi,Vi和Vj互为邻接点。

、入度和出度
在无向图中,与顶点v相邻接的边数称为该顶点的度,记为D(v)。
在有向图中,顶点v的度又分为入度和出度两种:
以顶点v为终点(弧头)的弧的数目称为顶点v的入度,记为ID(v);
以顶点v为起点(弧尾)的弧的数目称为顶点v的出度,记为OD(v);
有向图顶点v的度为该顶点的入度和出度之和,即
D(v)=ID(v)+OD(v)
无论是有向图还是无向图,一个图的顶点数n、边(弧)数e和每个顶点的度di之间满足以下的关系式:
即在有向图或无向图中:
所有顶点度数之和:边数= 2 :1
、稠密图和稀疏图
在图G中:
若G为无向图,任意两个顶点之间都有一条边,称G为无向完全图。顶点数为n,无向完全图的边数:
2 =n(n1)/2
若G为有向图,任意两个顶点Vi, Vj之间都有弧<Vi,Vj> 、<Vj,Vi> ,称G为有向完全图。如顶点数为n,有向完全图的弧数:
e=Pn2 =n(n1)
例如,无向图G1就是4个顶点无向完全图。
若一个图接近完全图,则称其为稠密图;反之,若一个图含有很少条边或弧(即e<<n2),则称其为稀疏图。

若有图G=(V, E)和G′=(V′, E′)
且V′是V的子集,即V′ V , E′是E的子集,即 E′ E
则称图G′为图G的子图。
、回路和路径长度
在无向图G中,若存在一个顶点序列(Vp , Vi1 , Vi2 , …, Vin , Vq),使(Vp, Vi1),(Vi1, Vi2),…,(Vin, Vq)均为图G的边,则该称顶点的序列为顶点Vp到顶点Vq的路径。若G是有向图,则路径是有向的。
路径长度定义为路径上的边数或者弧的数目。
若一条路径中不出现重复顶点,则称此路径为简单路径。
若一条路径的起点和终点相同(Vp=Vq)称为回路或环。
除了起点和终点相同外,其余顶点不相同的回路,称为简单回路或简单环。