6.1 图的逻辑结构
V1 V3
V4 V1
V3
V2 若顶点vi和vj之间的边没有方向，则 称这条边为无向边，表示为(vi,vj)。 如果图的任意两个顶点之间的边都
V5 是无向边，则称该图为无向图。
V2 若从顶点vi到vj的边有方向，则称这 条边为有向边，表示为<vi,vj>。 如果图的任意两个顶点之间的边都
第6章 图
本章的主要内容是:
图的逻辑结构 图的存储结构及实现 图的连通性 最小生成树 最短路径 AOV网与拓扑排序 AOE网与关键路径
2019/10/26
第6章 图
图是一种非常复杂的非线性结构，并且具有极强的表达能力， 现实世界中的许多问题都可以抽象为图结构。本章是本课程 的难点和重点。通过本章的学习，要求学生：
i =1
V1
V2
V3
V4
V5
在具有n个顶点、e条边的无向图G中，各顶点 的度之和与边数之和的关系？
6.1 图的逻辑结构
图的基本术语
V1
V2
n
n
ID(vi ) = OD(vi ) = e
i=1
i=1
V3
V4
在具有n个顶点、e条边的有向图G中，各顶点 的入度之和与各顶点的出度之和的关系？与边 数之和的关系？
A
B
C
D
E
F
线性结构
A
V1
V2
B
C
V3
D
EF
V4
V5
树结构
图结构
在线性结构中，元素之间的关系为前驱和后继； 在树结构中，结点之间的关系为双亲和孩子； 在图结构中，顶点之间的关系为邻接。
6.1 图的逻辑结构
图的基本术语
无向完全图：在无向图中，如果任意两个顶点之间 都存在边，则称该图为无向完全图。
有向完全图：在有向图中，如果任意两个顶点之间都 存在方向相反的两条弧，则称该图为有向完全图。
哥尼斯堡七桥问题
能否从某个地方出发，穿过所有的桥仅一次 后再回到出发点？
哥尼斯堡七桥问题
七拉回路的判定规则： 1.如果通奇数桥的地方多于 两个，则不存在欧拉回路； 2.如果只有两个地方通奇数 桥，可以从这两个地方之一 出发，找到欧拉回路； 3.如果没有一个地方是通奇 数桥的，则无论从哪里出发， 都能找到欧拉回路。
V1
V2
V1
V2
V3
V4
V3
6.1 图的逻辑结构
含有n个顶点的无向完全图有多少条边？ 含有n个顶点的有向完全图有多少条弧？
V1
V2
V1
V2
V3
V4
V3
含有n个顶点的无向完全图有n×(n-1)/2条边。 含有n个顶点的有向完全图有n×(n-1)条边。
6.1 图的逻辑结构
图的基本术语
稀疏图：称边数很少的图为稀疏图； 稠密图：称边数很多的图为稠密图。
无向图中，对于任意两个顶点vi和顶点vj，若存在边 (vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边 (vi，vj)依附于顶点vi和顶点vj。
V1的邻接点： V2 、V4 V2的邻接点： V1 、V3 、V5
V1
V2
V3
V4
V5
6.1 图的逻辑结构
图的基本术语
邻接、依附
有向图中，对于任意两个顶点vi和顶点vj，若存在弧 <vi，vj>，则称顶点vi邻接到顶点vj，顶点vj邻接自顶 点vi，同时称弧<vi，vj>依附于顶点vi和顶点vj 。
V4 是有向边，则称该图为有向图。
6.1 图的逻辑结构
图的基本术语
简单图：在图中，若不存在顶点到其自身的边，且同 一条边不重复出现。
V1
V2 V1
V2 V1
V2
V3
V3
V3
V4
V5 V4
V5 V4
V5
非简单图
非简单图
简单图
数据结构中讨论的都是简单图。
6.1 图的逻辑结构
图的基本术语
邻接、依附
V1
V2
V1的邻接点： V2 、V3
V3的邻接点： V4
V3
V4
不同结构中逻辑关系的对比
A
B
C
D
E
F
线性结构
A
V1
V2
B
C
V3
D
EF
V4
V5
树结构
图结构
在线性结构中，数据元素之间仅具有线性关系； 在树结构中，结点之间具有层次关系； 在图结构中，任意两个顶点之间都可能有关系。
不同结构中逻辑关系的对比
顶点的度：在无向图中，顶点v的度是指依附于该顶 点的边数，通常记为TD (v)。 顶点的入度：在有向图中，顶点v的入度是指以该顶 点为弧头的弧的数目，记为ID (v)； 顶点的出度：在有向图中，顶点v的出度是指以该顶 点为弧尾的弧的数目，记为OD (v)。
6.1 图的逻辑结构
图的基本术语
n
TD (vi ) = 2e
•掌握图的定义及其基本术语； •理解图的抽象数据类型定义； •掌握图的邻接矩阵和邻接表存储； •掌握图的遍历方法及其在邻接矩阵和邻接表存储结构上的实现； •理解图的十字链表、邻接多重表和边集数组存储方法； •理解无向图的连通性； •了解有向图的连通性； •掌握Prim算法和Kruskal算法的基本思想和求解过程； •理解Prim算法和Kruskal算法的C++描述； •掌握Dijkstra算法和Floyd算法的基本思想及求解过程； •理解Dijkstra算法和Floyd算法的C++描述； •掌握拓扑序列的定义及拓扑排序算法； •掌握关键路径的定义及求解过程； •理解求关键路径算法。
图论——欧拉
欧拉1707年出生在瑞士的巴塞尔城，19岁开始发 表论文，直到76岁。几乎每一个数学领域都可以 看到欧拉的名字，从初等几何的欧拉线，多面体 的欧拉定理，立体解析几何的欧拉变换公式，四 次方程的欧拉解法到数论中的欧拉函数，微分方 程的欧拉方程，级数论的欧拉常数，变分学的欧 拉方程，复变函数的欧拉公式等等。据统计他那 不倦的一生，共写下了886本书籍和论文，其中 分析、代数、数论占40%，几何占18%，物理和 力学占28%，天文学占11%，弹道学、航海学、 建筑学等占3%。 1733年，年仅26岁的欧拉担任 了彼得堡科学院数学教授。1741年到柏林担任科 学院物理数学所所长，直到1766年，重回彼得堡， 没有多久，完全失明。欧拉在数学上的建树很多， 对著名的哥尼斯堡七桥问题的解答开创了图论的 研究。
6.1 图的逻辑结构
图的定义
图是由顶点的有穷非空集合和顶点之间边的集合组 成，通常表示为：
G=(V，E) 其中：G表示一个图，V是图G中顶点的集合，E是 图G中顶点之间边的集合。 在线性表中，元素个数可以为零，称为空表； 在树中，结点个数可以为零，称为空树； 在图中，顶点个数不能为零，但可以没有边。