数据结构第9章图学习教案.pptx

文档介绍：会计学
1
数据结构(shù jù jié ɡòu)第9章图
第一页，共58页。
图的基本概念
图(Graph) 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构(shù jù jié ɡòu)：
Graph＝( V, E )
其中:V = { x | x  某个数据对象}是顶点的有穷非空集合；
E = {(x, y) | x, y  V }
或 E = {<x, y> | x, y  V}是顶点之间关系的有穷集合。
1
2
5
6
3
4
a
b
c
d
无向(wú xiànɡ)图
有向图
V={1, 2, 3, 4, 5, 6}
E={(1, 2), (1, 5), (1,6),
(2, 3), (2, 4), (3, 4),
(4, 5), (4, 6)}（边）
V={ a, b, c, d}
E={ <a,b>, <a,d>,<b,d>,
<c,a>,<d,a>,<d,b>,
<d,c> }
（弧）<弧尾顶点(dǐngdiǎn)，弧头顶点(dǐngdiǎn)>
第1页/共58页
第二页，共58页。
ADT Graph
{ 数据对象:
D={ai|1i  n, n  0, ai属Elemtype类型
数据关系:
R1={< ai ,aj >| ai ,aj D, 1i  n, 1j  n,
每个元素可以有多个直接前驱和可以有多个直接后继}
基本(jīběn)运算:
InitGraph(t);
ClearGraph(t);
DSF(t);
BSF(t);

}
抽象数据类型数的定义(dìngyì)
第2页/共58页
第三页，共58页。
完全(wánquán)图 若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全(wánquán)无向图。有 n 个顶点的有向图有n(n-1) 条边, 则此图为完全(wánquán)有向图。
a
b
c
1
2
3
4
邻接顶点 如果 (u, v) 是 E(G) 中的一条(yī tiáo)边，则称 u 与 v 互为邻接顶点。
例：存在(1, 2)，则顶点1与2互为邻接点。
存在<a, b>, 则顶点a与b互为邻接点。
第3页/共58页
第四页，共58页。
1
2
5
6
3
4
a
b
c
d
顶点的度 一个(yī ɡè)顶点v的度是与它相关联的边的条数。记作TD(v)。
在有向图中,顶点的度=入度+出度。
顶点 v 的入度 是以 v 为终点(zhōngdiǎn)的有向边的条数, 记作 ID(v); 顶点 v 的出度 是以 v 为始点的有向边的条数, 记作 OD(v)。 TD(v)=ID(v)+OD(v)
例：TD(1)=3 TD(4)=4 TD(5)=2
例：TD(b)=ID(b)+OD(b) TD(d)=ID(d)+OD(d)
=2+1=3
=2+3=5
第4页/共58页
第五页，共58页。
子图 设有两个(liǎnɡ ɡè)图 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
权 某些图的边具有与它相关的数, 称为(chēnɡ wéi)权。这种带权图叫做网络。
任意图(yìtú)都是其自身子图
a
b
c
d
8

1 9
3 4 11
23
第5页/共58页
第六页，共58页。
路径(lùjìng) 在图