数据结构培训PPT学习教案.pptx

文档介绍：会计学
1
数据结构培训
例
2
4
5
1
3
6
G1
图G1中：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(G2)={1,2,3,4,5,6,7}
E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)}
第1页/共54页
有向完全图——n个顶点的有向图边数是n(n-1)
无向完全图——n个顶点的无向图边数是n(n-1)/2
权——与图的边或弧相关的数叫~
网——带权的图叫~
子图——如果图G(V,E)和图G‘(V’,E‘),满足：
V’V
E’E
则称G‘为G的子图
顶点的度
无向图中，顶点的度为与每个顶点相连的边数
有向图中，顶点的度分成入度与出度
入度：以该顶点为头的弧的数目
出度：以该顶点为尾的弧的数目
路径——路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)E 或 <Vij-1,Vij>E,(1<jn)
第2页/共54页
路径长度——沿路径边的数目或沿路径各边权值之和
回路——第一个顶点和最后一个顶点相同的路径叫~
简单路径——序列中顶点不重复出现的路径叫~
简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫~
连通——无向图中,从顶点V到顶点W有一条路径，则说V和W是连通的
连通图——无向图中,图中任意两个顶点都是连通的叫~
连通分量——无向图中,非连通图的每一个连通部分叫~
强连通图——有向图中，如果对每一对Vi,VjV, ViVj,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是~
第3页/共54页
例
2
1
3
2
1
3
有向完全图
无向完全图
3
5
6
例
2
4
5
1
3
6
图与子图
例
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
第4页/共54页
例
1
5
7
3
2
4
G2
6
例
2
4
5
1
3
6
G1
路径：1，2，3，5，6，3
路径长度：5
简单路径：1，2，3，5
回路：1，2，3，5，6，3，1
简单回路：3，5，6，3
路径：1，2，5，7，6，5，2，3
路径长度：7
简单路径：1，2，5，7，6
回路：1，2，5，7，6，5，2，1
简单回路：1，2，3，1
第5页/共54页
连通图
例
2
4
5
1
3
6
强连通图
3
5
6
例
非连通图
连通分量
例
2
4
5
1
3
6
第6页/共54页
图的存储结构
多重链表
例
G1
2
4
1
3
例
1
5
3
2
4
G2
V1
V2 ^ ^
V4 ^
V3 ^
^ V1
V2
V4 ^
V5 ^
V3
按度数最大的顶点设计顶点结构
第7页/共54页
邻接矩阵——表示顶点间相联关系的矩阵
定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵
例
G1
2
4
1
3
例
1
5
3
2
4
G2


















第8页/共54页
特点：
无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2
有向图邻接矩阵不一