[电脑基础知识]数据结构图.ppt

文档介绍：第7章图
图是一种非线性结构,结构较复杂,数据元素之间的关系是任意的。它可应用到电子线路分析、系统工程、人工智能等。
图的定义和术语
图的抽象数据类型:P156~157
图的定义
图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)
其中:V(G)是顶点的非空有限集
E(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)
例
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)}
图的基本术语
完全图:n个顶点的图中,每个顶点与其它n-1个顶点都有边
有向完全图——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)
路径长度——沿路径边的数目或沿路径各边权值之和
回路——第一个顶点和最后一个顶点相同的路径叫~
简单路径——序列中顶点不重复出现的路径叫~
简单回路——除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路叫~
连通——从顶点V到顶点W有一条路径,则说V和W是连通的
连通图——图中任意两个顶点都是连通的叫~
连通分量——非连通图的每一个连通部分叫~
(P159 )
强连通图——有向图中,如果对每一对Vi,VjV, ViVj,从Vi到Vj 和从Vj到 Vi都存在路径,则称G是~

例
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
例
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
连通图
例
2
4
5
1
3
6
强连通图
3
5
6
例
非连通图
连通分量
例
2
4
5
1
3
6
有向树:一个有向图若只有一个顶点的入度为0,
其余顶点的入度都为1,则该图称为一棵有向树.
生成森林:由若干棵有向树组成,含图中全部顶点,这些顶点构成若干棵互不相交的有向树的弧.

图的存储结构
多重链表(P160)
例
G1
2
4
1
3
例
1
5
3
2
4
G2
V1
V2 ^ ^
V4 ^
V3 ^
^ V1
V2
V4 ^
V5 ^
V3
数组表示法——表示顶点间相联关系的邻接矩阵
定义:设G=(V,E)是有n1个顶点的图,G的邻接矩阵A是具有以下性质的n阶方阵
例
G1
2
4
1
3
例
1
5
3
2
4
G2












