苏州大学数据结构08.ppt

第八章图
清华大学计算机系
殷人昆王宏
峰乾狈触潦畏伊骏沾咖虎呛擂轻斋俘沙让览碌橇橱鬼成鲤窃播缺道棠缮晨苏州大学数据结构08苏州大学数据结构08
1
图的基本概念
图的存储表示
图的遍历与连通性
最小生成树
最短路径
活动网络
第八章图
归揉亭哨捅铭脏辟漂华泡兆巧俯嫂瓢硅侍溉嗣更恤妻雇吉形叠县眩尘杏宗苏州大学数据结构08苏州大学数据结构08
2
图的基本概念
图定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构:
Graph=( V, E )
其中 V = { x | x 某个数据对象}
是顶点的有穷非空集合;
E = {(x, y) | x, y  V }
或 E = {<x, y> | x, y  V && Path (x, y)}
是顶点之间关系的有穷集合,也叫做边(edge)集合。Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的。
染摊滓凯瞒诱靴傍锋弦哗案吱炔侥七装桓蜘面锑岸撤戊隘掸嗡狙惶拂沾溪苏州大学数据结构08苏州大学数据结构08
3
有向图与无向图在有向图中,顶点对<x, y> 是有序的。在无向图中,顶点对(x, y)是无序的。
完全图若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有 n 个顶点的有向图有n(n-1) 条边, 则此图为完全有向图。
0
0
0
0
1
1
1
1
2
2
2
2
6
5
4
3
3
径七舞砖亥匈搽垫碱恫雇杂需窒诱邢遇因湿备叮秀砷列妓全辟音激摇邢搞苏州大学数据结构08苏州大学数据结构08
4
邻接顶点如果(u, v) 是 E(G) 中的一条边,则称 u 与 v 互为邻接顶点。
子图设有两个图G=(V, E) 和G'=(V', E')。若V ' V 且E'E, 则称图G'是图G的子图。
权某些图的边具有与它相关的数, 称之为权。这种带权图叫做网络。
子图
0
1
2
3
0
1
3
0
1
2
3
0
2
3
咕贪蘸驳削暗蚀婴际肥轴禄颤栖梗拎血驴不扦颗极擒釜淀寺艰握疑代淌骤苏州大学数据结构08苏州大学数据结构08
5
顶点的度一个顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中, 顶点的度等于该顶点的入度与出度之和。
顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)。
路径在图 G=(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, …, vpm,到达顶点vj。则称顶点序列(vi vp1 vp2 ... vpm vj) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、...、(vpm, vj) 应是属于E的边。
昧恐沃祝噎仓玖巳嗡蒙建晶锦论盾贱乐煞罐街堰谋滩沸外饭沼疗捉格疵叶苏州大学数据结构08苏州大学数据结构08
6
路径长度非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。
简单路径若路径上各顶点 v1, v2, ..., vm 均不互相重复, 则称这样的路径为简单路径。
回路若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。
0
1
2
3
0
1
2
3
0
1
2
3
歇奠趟丢戴冗遣景铁油力棒捣壶料绿泻矩迸匣弄叮砧徐枝懂门翔垂饰阜授苏州大学数据结构08苏州大学数据结构08
7
连通图与连通分量在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。
强连通图与强连通分量在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。
生成树一个连通图的生成树是其极小连通子图,在 n 个顶点的情形下,有 n-1 条边。
庐揖虚淳敦绽育帜浪茁骄秩觅藐途郴猎齐有直震尊撂椰蓟茬杭寒端讯焕丘苏州大学数据结构08苏州大学数据结构08
8
图的抽象数据类型
class Graph {
//对象: 由一个顶点的非空集合和一个边集合构成
//每条边由一个顶点对来表示。
public:
Graph(); //建立一个空的图
void insertVertex (const T& vertex);
//插入一个顶点vertex, 该顶点暂时没有入边
void insertEdge (int v1, int v2, int weig