文档介绍：该【数据结构图1公开课获奖课件赛课一等奖课件 】是由【非学无以广才】上传分享，文档一共【122】页，该文档可以免费在线阅读，需要了解更多关于【数据结构图1公开课获奖课件赛课一等奖课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第七章 图
图形构造是一种比树形构造更复杂的非线性构造。在图形构造中，任意两个结点之间都也许有关，即结点之间的邻接关系可以是任意的。就是说，图是一种多对多的构造关系，每个元素可以有零个或多种直接前趋；零个或多种直接后继。因此图形构造被用于描述多种复杂的数据对象。应用领域非常广泛。
1
[内容提要]
图的概念
图的存储构造
图的遍历措施
求生成树
找最短途径
关键途径
拓扑排序
2
图（graph）
图是一种数据构造，它的形式化定义为G=(V，E)，其中：
V是一种非空有限集合，它的元素称为顶点(vertex)。
顶点的偶对(x，y) (x∈V，y∈V)叫做边(edge)，E是边的集合。
3
图基本术语
有向图（ digraph ）：
若图中代表一条边的顶点偶对是有序的，记作<x，y>，称x为弧尾(tail)或初始点(initial node)，称y为弧头(head)或终端点(terminal node)，<x，y>表达从x到y的一条弧(arc)，此时的图称为有向图。
无向图(undigraph) ：
图中代表一条边的顶点偶对(x，y)是无序的，则称其为无向图。这时(x，y)，(y，x)是同一条边。
4
G1=(V1，E1) 其中：
V1={v1，v2，v3，v4}
E1={<v1，v2>，< v3 ,v1>，< v4 ， v3>，< v1 v4>}
G2=(V2，E2) 其中：
V2={v1，v2，v3，v4，v5}
E2={(v1，v2)，(v1，v4)，(v2，v3)，(v2，v5)，(v3，v4)，(v3，v5)}
有向图G1 (b)无向图G2
图 图的示例
图基本术语(续)
无序对(vi,vj)：
用连接顶点vi、vj的线段
表达，称为无向边。
有序对<vi,vj> ：
以vi为起点、vj为终点的
有向线段表达，称为有向
边或弧。
5
图基本术语(续)
完全图(completed graph) ：
对于无向图，e的取值范围是0到n(n-1)/2，有n(n-1)/2条边的无向图称为完全图。
对于有向图，e的取值范围是0到n(n-1)。具有n(n-1)条弧的有向图称为有向完全图。
邻接点(adjacent)：对于无向图G=(V，E)，假如边(v，v’)∈E，则称顶点v和v’互为邻接点，即v和v'相邻接。边(v，v')依附(incident)于顶点v和v'，或者说边(v，v')和顶点v，v'有关联。
例
2
1
3
2
1
3
有向完备图
无向完备图
6
度：顶点v的度是和v有关联的边的数目。记作TD(V)。例如G2中顶点v3的度是3。
入度：有向图中，以顶点v为头的弧的数目称为v的入度，记为ID(V)；
出度：有向图中，以顶点v为尾的弧的数目称为v的出度，记为OD(v)；
顶点v的度为： TD(v)=ID(v)+OD(v)
图基本术语(续)
例
1
5
7
3
2
4
G2
6
顶点5的度：3
顶点2的度：4
例
2
4
5
1
3
6
G1
顶点2入度：1 出度：3
顶点4入度：1 出度：0
7
图基本术语(续)
子图(subgraph)： 假设有两个图G=(V，E)，G'=(V'，E')。假如V'包含于V，E'包含于E，则称G'是G的子图。
(a)G1的子图 (b)G2的子图
子图示例
3
5
6
例
2
4
5
1
3
6
图与子图
8
途径：无向图G=(V，E)中从顶点v到顶点v‘的途径是一种顶点序列(v=vi0，vi1，vi2，...，vin=v’)，其中(vi，j-1，vij)∈E，1≤j≤n。假如G是有向图，则途径也是有向的，顶点序列应满足<vi，j-1，vij>∈E，1≤j≤n。
途径的长度：是指途径上的边的或弧的数目。
图基本术语(续)
9
回路：第一种顶点和最终一种顶点相似的途径称为回路或环。
简单途径：序列中顶点不反复出现的途径称为简单途径。
简单回路：除了第一顶点和最终一种顶点之外，其他顶点不反复出现的回路，称为简单回路或简单环。
图基本术语(续)
10