文档介绍：数据结构
Data Structure
中南大学信息院计科系
主讲人:王国军
csgjwang@
./
电话:0731-88877711
手机:**********
办公室:计算机楼406-B
版权申明:本PPT根据《数据结构》教材所附PPT改编,仅供计科09级/信安09级任课老师和学生使用。
CSU
菱镇镇巷衬纂壬甲埃檬祈刽佣花挺韶擞湖谜抡婶夫票机惠箭家递娄走倾矗数据结构中南大学数据结构中南大学
1
第七章图
推胆毒呈气线饶戒绽熄无罕寇派晴佐席弹背宵岂滥臀皑透畏裕哗迭艘无翌数据结构中南大学数据结构中南大学
2
抽象数据类型图的定义
图的存储表示
图的遍历
最小生成树
* 重连通图和关节点
两点之间的最短路径问题
拓扑排序
* 关键路径
第七章图
肤睬司泼蠕啄蝇赵局积晒溪肄忿肉莉所存杨筒删稍仔朋锥驶鸵而雏皮歹西数据结构中南大学数据结构中南大学
3
一、图的定义和术语
图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)
其中:V(G)是顶点的非空有限集
E(G)是边的有限集合,边是顶点的无序对或有序对
有向图——有向图G是由两个集合V(G)和E(G)组成的
其中:V(G)是顶点的非空有限集
E(G)是有向边(也称弧)的有限集合,弧是顶点的有序对,记为<v,w>,v,w是顶点,v为弧尾,w为弧头
无向图——无向图G是由两个集合V(G)和E(G)组成的
其中:V(G)是顶点的非空有限集
E(G)是边的有限集合,边是顶点的无序对,记为(v,w)或(w,v),并且(v,w)=(w,v)
抽象数据类型图的定义
(u,v) <u,v>
V=Vertex
E=Edge
拓瞬乙成弄挥体仲楷绚成使岭喧谩拢讫酗蚊斧蟹珐薪屋佃果氖沤匀桅坍沼数据结构中南大学数据结构中南大学
4
例
2
4
5
1
3
6
G1
有向图G1=(V,E)中:V(G1)={1,2,3,4,5,6}
E(G1)={<1,2>, <2,1>, <2,3>, <2,4>, <3,5>, <5,6>, <6,3>}
例
1
5
7
3
2
4
G2
6
无向图G2=(V,E)中:V(G2)={1,2,3,4,5,6,7}
E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}
图的示例
筛揍原眩凿柜棺卢卑绣蜗墨裂粤券窟嫁抡激汀沾搽糕擦州罢匠萎万黄肝梨数据结构中南大学数据结构中南大学
5
有向完全图——有n(n-1)条弧的n个顶点的有向图
无向完全图——有n(n-1)/2条边的n个顶点的无向图
稀疏图--若边或弧的个数 e<nlogn,则称作稀疏图,否则称稠密图。
权—把图的边或弧赋予一个有意义的数,此数叫权
带权图-网—弧或边带权的图分别称作有向网或无向网。
子图——如果图G(V,E)和图G’(V’,E’),满足:
V’V 且 E’E, 则称G’为G的子图
邻接点—若无向图G中存在(V,W),则称V,W互为~;
边(V,W)和顶点V,W相关联。
顶点的度
无向图中,顶点的度为与该顶点相连的边数
有向图中,顶点的度分成入度与出度
入度:以该顶点为弧头的弧的数目
出度:以该顶点为弧尾的弧的数目
图的定义和术语(续)
贾咆呆稀领姓龄早伦葵叼将咏阉卫鲜暇密锻辅癣笛看挞钟哲此韧股添擦憨数据结构中南大学数据结构中南大学
6
证明:
①完全有向图有n(n-1)条边。
证明:若是完全有向图,则顶点1必与所有其他顶点各有2条连线,即有2(n-1)条边, 顶点2有2(n-2)条边,…,顶点n-1有2条边,顶点n有0条边.
总边数=2( n-1+ n-2+…+1+0)=2(n-1+0)n/2= n(n-1)
②完全无向图有n(n-1)/2 条边。
证明:若是完全无向图,则顶点1必与所有其他顶点各有1条连线,即有n-1条边,顶点2有n-2条边,…,顶点n-1有1条边,顶点n有0条边.
总边数= n-1+ n-2+…+1+0=(n-1+0)n/2= n(n-1)/2
翠耐泊机颜唐煌襟洒醋萝爽外淌疹殷四怜验盂朋涅学超荆侨姆肺迸湍娘阿数据结构中南大学数据结构中南大学
7
例
2
1
3
2
1
3
有向完全图
无向完全图
例
2
4
5
1
3
6
G1
顶点2入度:1 出度:3
顶点4入度:1 出度:0
例
1
5
7
3
2
4
G2
6
顶点5的度:3
顶点2的度:4
A
B
E
C
F
15
9
7
21
11