数据结构(C++版)

1、数据结构（数据结构（C版）版）清华大学出版社清华大学出版社第六章第六章 图图本章的主要内容是本章的主要内容是:图的逻辑结构图的逻辑结构图的存储结构及实现图的存储结构及实现图的连通性图的连通性最小生成树最小生成树最短路径最短路径AOV网与拓扑排序网与拓扑排序AOE网与关键路径网与关键路径 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社欧拉欧拉17071707年出生在瑞士的巴塞尔城，年出生在瑞士的巴塞尔城，1919岁开始发岁开始发表论文，直到表论文，直到7676岁。几乎每一个数学领域都可以岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体看到欧拉的名字，从初等几何的

2、欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了不倦的一生，共写下了886886本书籍和论文，其中本书籍和论文，其中分析、代数、数论占分析、代数、数论占40%40%，几何占，几何占18%18%，物理和，物理和力学占力学占28%28%，天文学占，天文学占11%11%，弹道学、航海

3、学、，弹道学、航海学、建筑学等占建筑学等占3%3%。 1733 1733年，年仅年，年仅2626岁的欧拉担任岁的欧拉担任了彼得堡科学院数学教授。了彼得堡科学院数学教授。17411741年到柏林担任科年到柏林担任科学院物理数学所所长，直到学院物理数学所所长，直到17661766年，重回彼得堡，年，重回彼得堡，没有多久，完全失明。欧拉在数学上的建树很多，没有多久，完全失明。欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的对著名的哥尼斯堡七桥问题的解答开创了图论的研究。研究。图论图论欧拉欧拉数据结构（数据结构（C版）版）清华大学出版社清华大学出版社能否从某个地方出发，穿过所有的桥仅

4、一次能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？后再回到出发点？哥尼斯堡七桥问题哥尼斯堡七桥问题 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社CADB七桥问题的图模型七桥问题的图模型哥尼斯堡七桥问题哥尼斯堡七桥问题 欧拉回路的判定规则：欧拉回路的判定规则：1.如果通奇数桥的地方多于如果通奇数桥的地方多于两个，则不存在欧拉回路；两个，则不存在欧拉回路；2.如果只有两个地方通奇数如果只有两个地方通奇数桥，可以从这两个地方之一桥，可以从这两个地方之一出发，找到欧拉回路；出发，找到欧拉回路；3.如果没有一个地方是通奇如果没有一个地方是通奇数桥的，则无论从哪里出发，数桥的，则无论

5、从哪里出发，都能找到欧拉回路。都能找到欧拉回路。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社图的定义图的定义6.1 图的逻辑结构图的逻辑结构图是由图是由顶点顶点的的有穷非空有穷非空集合和顶点之间集合和顶点之间边边的集合组的集合组成，通常表示为：成，通常表示为： G=(V，E)其中：其中：G表示一个图，表示一个图，V是图是图G中顶点的集合，中顶点的集合，E是是图图G中顶点之间边的集合。中顶点之间边的集合。 在线性表中，元素个数可以为零，称为空表；在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，

6、但可以没有边。在图中，顶点个数不能为零，但可以没有边。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.1 图的逻辑结构图的逻辑结构如果图的任意两个顶点之间的边都如果图的任意两个顶点之间的边都是是无向边，则称该图为无向边，则称该图为无向图无向图。若顶点若顶点vi和和vj之间的边没有方向，则之间的边没有方向，则称这条边为称这条边为无向边无向边，表示为，表示为(vi, ,vj)。若从顶点若从顶点vi到到vj的边有方向，则称这的边有方向，则称这条边为条边为有向边有向边，表示为，表示为。 如果图的任意两个顶点之间的边都如果图的任意两个顶点之间的边都是是有向边，则称该图为有向边，则称该图为有

7、向图有向图。V1V2V3V4V5V1V2V3V4数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 简单图：简单图：在图中，若不存在顶点到其自身的边，且同在图中，若不存在顶点到其自身的边，且同一条边不重复出现一条边不重复出现。V3V4V5V1V2V3V4V5V1V2非简单图非简单图 非简单图非简单图 简单图简单图V1V2V3V4V5v 数据结构中讨论的都是简单图。数据结构中讨论的都是简单图。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 邻接、依附邻接、依附无向图

8、无向图中，对于任意两个顶点中，对于任意两个顶点vi和顶点和顶点vj，若存在边若存在边(vi，vj)，则称顶点，则称顶点vi和顶点和顶点vj互为邻接点，同时称边互为邻接点，同时称边(vi，vj)依附于顶点依附于顶点vi和顶点和顶点vj。V1V2V3V4V5V1的邻接点：的邻接点： V2 、V4V2的邻接点：的邻接点： V1 、V3 、V5数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 邻接、依附邻接、依附有向图有向图中，对于任意两个顶点中，对于任意两个顶点vi和顶点和顶点vj，若存在弧若存在弧，则称顶点则称顶点vi邻接到顶点邻接

9、到顶点vj，顶点顶点vj邻接自顶邻接自顶点点vi，同时称弧同时称弧依附于顶点依附于顶点vi和顶点和顶点vj 。 V1V2V3V4V1的邻接点：的邻接点： V2 、V3V3的邻接点：的邻接点： V4数据结构（数据结构（C版）版）清华大学出版社清华大学出版社在线性结构中，数据元素之间仅具有线性关系；在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在树结构中，结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关系。在图结构中，任意两个顶点之间都可能有关系。 FECBAD线性结构线性结构ABCDEF树结构树结构V1V2V3V4V5图结构图结构不同结构中逻辑关系的对比

10、不同结构中逻辑关系的对比数据结构（数据结构（C版）版）清华大学出版社清华大学出版社在线性结构中，元素之间的关系为在线性结构中，元素之间的关系为前驱前驱和和后继后继；在树结构中，结点之间的关系为在树结构中，结点之间的关系为双亲双亲和和孩子孩子；在图结构中，顶点之间的关系为在图结构中，顶点之间的关系为邻接邻接。 FECBAD线性结构线性结构ABCDEF树结构树结构V1V2V3V4V5图结构图结构不同结构中逻辑关系的对比不同结构中逻辑关系的对比数据结构（数据结构（C版）版）清华大学出版社清华大学出版社无向完全图无向完全图：在无向图中，如果任意两个顶点之间：在无向图中，如果任意两个顶点之间都存在边，都

11、存在边，则称该图为无向完全图。则称该图为无向完全图。有向完全图有向完全图：在有向图中，如果任意两个顶点之间：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，都存在方向相反的两条弧，则称该图为有向完全图则称该图为有向完全图。 图的基本术语图的基本术语 V1V2V3V1V2V3V46.1 图的逻辑结构图的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社含有含有n个顶点的无向完全图有个顶点的无向完全图有多少多少条边？条边？含有含有n个顶点的有向完全图有个顶点的有向完全图有多少多少条弧？条弧？ 6.1 图的逻辑结构图的逻辑结构含有含有n个顶点的无向完全图有个顶点的无向完全图有

12、n(n-1)/2条边。条边。 含有含有n个顶点的有向完全图有个顶点的有向完全图有n(n-1)条边。条边。 V1V2V3V1V2V3V4数据结构（数据结构（C版）版）清华大学出版社清华大学出版社稀疏图：稀疏图：称边数很少的图为稀疏图；称边数很少的图为稀疏图；稠密图：稠密图：称边数很多的图为稠密图。称边数很多的图为稠密图。顶点的度：顶点的度：在无向图中，顶点在无向图中，顶点v的的度度是指依附于该顶是指依附于该顶点的边数，通常记为点的边数，通常记为TD (v)。6.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 顶点的入度：顶点的入度：在有向图中，顶点在有向图中，顶点v的的入度入度是指以该顶是

13、指以该顶点为弧头的弧的数目，点为弧头的弧的数目，记为记为ID (v)；顶点顶点的的出度：出度：在有向图中，顶点在有向图中，顶点v的的出度出度是指以该顶是指以该顶点为弧尾的弧的数目，记为点为弧尾的弧的数目，记为OD (v)。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社V1V2V3V4V56.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 在具有在具有n个顶点、个顶点、e条边的无向图条边的无向图G中，各顶点中，各顶点的度之和与边数之和的关系？的度之和与边数之和的关系？ = = =niievTD12)(数据结构（数据结构（C版）版）清华大学出版社清华大学出版社V1V2V3V46.

14、1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 在具有在具有n个顶点、个顶点、e条边的有向图条边的有向图G中，各顶点中，各顶点的入度之和与各顶点的出度之和的关系？与边的入度之和与各顶点的出度之和的关系？与边数之和的关系？数之和的关系？evODvIDiiii= = = = = =11)()(nn数据结构（数据结构（C版）版）清华大学出版社清华大学出版社权：权：是指对边赋予的有意义的数值量。是指对边赋予的有意义的数值量。网：网：边上带权的图，也称网图。边上带权的图，也称网图。6.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 V1V2V3V42785数据结构（数据结构（C版）版）清华大

15、学出版社清华大学出版社路径：路径：在无向图在无向图G=(V, E)中，从顶点中，从顶点vp到顶点到顶点vq之间的之间的路径路径是一个顶点序列是一个顶点序列(vp=vi0,vi1,vi2, , vim=vq)，其中，其中，(vij-1,vij)E（1jm）。）。若若G是有向图，则路径也是有是有向图，则路径也是有方向的，顶点序列满足方向的，顶点序列满足E。6.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 V1V2V3V4V5v一般情况下，图中的路径不惟一。一般情况下，图中的路径不惟一。V1 到到V4的路径：的路径： V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4数据结构（数

16、据结构（C版）版）清华大学出版社清华大学出版社路径长度：路径长度：6.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 非带权图非带权图路径路径上边的上边的个数个数带权图带权图路径上路径上各边的各边的权之和权之和V1V2V3V4V5V1 V4：长度为：长度为1V1 V2 V3 V4 ：长度为：长度为3V1 V2 V5V3 V4 ：长度为：长度为4数据结构（数据结构（C版）版）清华大学出版社清华大学出版社路径长度：路径长度：6.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 非带权图非带权图路径路径上边的上边的个数个数带权图带权图路径上路径上各边的各边的权之和权之和V1 V4：长度为：

17、长度为8V1 V2 V3 V4 ：长度为：长度为7V1 V2 V5V3 V4 ：长度为：长度为15V1V2V3V4V5256328数据结构（数据结构（C版）版）清华大学出版社清华大学出版社回路（环）回路（环）：第一个顶点和最后一个顶点相同的路径。：第一个顶点和最后一个顶点相同的路径。简单路径：简单路径：序列中顶点不重复出现的路径。序列中顶点不重复出现的路径。简单回路（简单环）：简单回路（简单环）：除了第一个顶点和最后一个顶点除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。外，其余顶点不重复出现的回路。6.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 V1V2V3V4V5V1V

18、2V3V4数据结构（数据结构（C版）版）清华大学出版社清华大学出版社子图：子图：若图若图G=（V，E），），G=（V，E），），如果如果V V 且且E E ，则称图则称图G是是G的子图。的子图。6.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 V1V2V3V4V5V1V2V3V4V5V1V3V4数据结构（数据结构（C版）版）清华大学出版社清华大学出版社连通图：连通图：在无向图中，如果从一个顶点在无向图中，如果从一个顶点vi到另一个顶到另一个顶点点vj(ij)有路径，则称顶点有路径，则称顶点vi和和vj是连通的。如果图中是连通的。如果图中任意两个顶点都是连通的，则称该图是连通任意两个顶点

19、都是连通的，则称该图是连通图。图。连通分量：连通分量：非连通图的极大连通子图称为连通分量。非连通图的极大连通子图称为连通分量。 6.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 如何求得一个非连通图的连通分量如何求得一个非连通图的连通分量? ?1.含有极大含有极大顶点顶点数；数；2. 依附于这些顶点的所有依附于这些顶点的所有边边。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社连通分量连通分量1 6.1 图的逻辑结构图的逻辑结构V1V2V3V4V5V6V7V1V2V4V5V3V6V7连通分量连通分量2图的基本术语图的基本术语 v连通分量是对无向图的一种划分。连通分量是对无向图

20、的一种划分。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社强连通图：强连通图：在有向图中，对图中任意一对顶点在有向图中，对图中任意一对顶点vi和和vj (ij)，若从顶点若从顶点vi到顶点到顶点vj和从顶点和从顶点vj到顶点到顶点vi均有路径均有路径，则称该有向图是强连通图。，则称该有向图是强连通图。强连通分量：强连通分量：非强连通图非强连通图的极大强连通子图。的极大强连通子图。 6.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 如何求得一个非连通图的连通分量如何求得一个非连通图的连通分量? ?数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.1 图的逻辑结构图

21、的逻辑结构图的基本术语图的基本术语 V1V2V3V4强连通分量强连通分量1 强连通分量强连通分量2V1V3V4V2数据结构（数据结构（C版）版）清华大学出版社清华大学出版社生成树：生成树：n个顶点的连通图个顶点的连通图G的生成树是包含的生成树是包含G中中全全部顶点部顶点的一个极小连通的一个极小连通子图。子图。 生成森林：生成森林：在非连通图中，由每个连通分量都可以得在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分到一棵生成树，这些连通分量的生成树就组成了一个量的生成树就组成了一个非连通图的非连通图的生成森林生成森林。 如何理解极小连通子图如何理解极小连通子图?6.1 图的逻辑结构图

22、的逻辑结构图的基本术语图的基本术语 多多构成回路构成回路少少不连通不连通含有含有n-1条边条边数据结构（数据结构（C版）版）清华大学出版社清华大学出版社V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成树生成树生成森林生成森林6.1 图的逻辑结构图的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社图的抽象数据类型定义图的抽象数据类型定义 ADT GraphData 顶点的有穷非空集合和边的集合顶点的有穷非空集合和边的集合Operation InitGraph 前置条件：图不存在前置条件：图不存在 输入：无输入：无 功能：图的初

23、始化功能：图的初始化 输出：无输出：无 后置条件：构造一个空的图后置条件：构造一个空的图6.1 图的逻辑结构图的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 DFSTraverse 前置条件：图已存在前置条件：图已存在 输入：遍历的起始顶点输入：遍历的起始顶点v 功能：从顶点功能：从顶点v出发深度优先遍历图出发深度优先遍历图 输出：图中顶点的一个线性排列输出：图中顶点的一个线性排列 后置条件：图保持不变后置条件：图保持不变 BFSTraverse 前置条件：图已存在前置条件：图已存在 输入：遍历的起始顶点输入：遍历的起始顶点v 功能：从顶点功能：从顶点v出发广度优先遍历图

24、出发广度优先遍历图 输出：图中顶点的一个线性排列输出：图中顶点的一个线性排列 后置条件：图保持不变后置条件：图保持不变6.1 图的逻辑结构图的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社DestroyGraph 前置条件：图已存在前置条件：图已存在 输入：无输入：无 功能：销毁图功能：销毁图 输出：无输出：无 后置条件：释放图所占用的存储空间后置条件：释放图所占用的存储空间GetVex 前置条件：图已存在前置条件：图已存在 输入：顶点输入：顶点v 功能：在图中查找顶点功能：在图中查找顶点v的数据信息的数据信息 输出：顶点输出：顶点v的数据信息的数据信息 后置条件：图保持不

25、变后置条件：图保持不变endADT6.1 图的逻辑结构图的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社图的遍历操作图的遍历操作图的遍历图的遍历是在从图中是在从图中某某一顶点出发，对图中所一顶点出发，对图中所有顶点有顶点访问一次且仅访问一次且仅访问访问一次。一次。 6.1 图的逻辑结构图的逻辑结构抽象操作，抽象操作，可以是对结点进行的各种可以是对结点进行的各种处理，这里处理，这里简化为输出结点的数据。简化为输出结点的数据。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社图的遍历操作要解决的关键问题图的遍历操作要解决的关键问题 在图中，如何选取遍历的起始顶点？在图中

26、，如何选取遍历的起始顶点？6.1 图的逻辑结构图的逻辑结构n在在线性表线性表中，数据元素在表中的编号就是元素在序列中，数据元素在表中的编号就是元素在序列中的位置，因而其编号是唯一的；中的位置，因而其编号是唯一的；n在在树树中，将结点按层序编号，由于树具有层次性，因中，将结点按层序编号，由于树具有层次性，因而其层序编号也是唯一的；而其层序编号也是唯一的；n在在图图中，任何两个顶点之间都可能存在边，顶点是没中，任何两个顶点之间都可能存在边，顶点是没有确定的先后次序的，所以，顶点的编号不唯一。有确定的先后次序的，所以，顶点的编号不唯一。为了定义操作的方便，将图中的顶点按任意顺序排列起为了定义操作的方

27、便，将图中的顶点按任意顺序排列起来，比如，按顶点的存储顺序。来，比如，按顶点的存储顺序。解决方案：从编号小的顶点开始解决方案：从编号小的顶点开始 。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 从某个起点始可能到达不了所有其它顶点从某个起点始可能到达不了所有其它顶点，怎么办？怎么办？6.1 图的逻辑结构图的逻辑结构图的遍历操作要解决的关键问题图的遍历操作要解决的关键问题解决方案：多次调用从某顶点出发遍历图的算法。解决方案：多次调用从某顶点出发遍历图的算法。v下面仅讨论从某顶点出发遍历图的算法。下面仅讨论从某顶点出发遍历图的算法。数据结构（数据结构（C版）版）清华大学出版社清华大学

28、出版社 因图中可能存在回路，某些顶点可能会被重复访问，因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环。那么如何避免遍历不会因回路而陷入死循环。 在图中，一个顶点可以和其它多个顶点相连，当这样在图中，一个顶点可以和其它多个顶点相连，当这样的顶点的顶点访问过后，如何选取下一个要访问的顶点？访问过后，如何选取下一个要访问的顶点？ 6.1 图的逻辑结构图的逻辑结构图的遍历操作要解决的关键问题图的遍历操作要解决的关键问题解决方案：附设访问标志数组解决方案：附设访问标志数组visitedn 。解决方案：解决方案：深度深度优先遍历和优先遍历和广度广度优先遍历。优先遍历。

29、数据结构（数据结构（C版）版）清华大学出版社清华大学出版社约翰约翰霍普克洛夫特霍普克洛夫特19391939年生于西年生于西雅图。雅图。19611961年进入斯坦福大学研究年进入斯坦福大学研究生院深造，生院深造，19621962年获硕士学位，年获硕士学位，19641964年获博士学位。毕业后先后在年获博士学位。毕业后先后在普林斯顿大学、斯坦福大学等著名普林斯顿大学、斯坦福大学等著名学府工作，也曾任职于一些科学研学府工作，也曾任职于一些科学研究机构如究机构如 NSFNSF（美国科学基金会）美国科学基金会）和和 NRCNRC（美国国家研究院）。美国国家研究院）。罗伯特罗伯特陶尔扬陶尔扬1948194

30、8年年4 4月月3030日生日生于加利福尼亚州于加利福尼亚州 。19691969年本科毕年本科毕业，进入斯坦福大学研究生院，业，进入斯坦福大学研究生院，19721972年获得博士学位。年获得博士学位。1986年图灵奖获得者年图灵奖获得者6.1 图的逻辑结构图的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1. 深度优先遍历深度优先遍历 基本思想基本思想 ： 访问顶点访问顶点v； 从从v的未被访问的邻接点中选取一个顶点的未被访问的邻接点中选取一个顶点w，从从w出发进行深度优先遍历；出发进行深度优先遍历； 重复上述两步，直至图中所有和重复上述两步，直至图中所有和v有路径相通有路

31、径相通的顶点都被访问到。的顶点都被访问到。 6.1 图的逻辑结构图的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社深一层递归深一层递归递归返回递归返回深度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列?6.1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8 V1遍历序列：遍历序列：V1V2 V2V4 V4V5 V5数据结构（数据结构（C版）版）清华大学出版社清华大学出版社深一层递归深一层递归递归返回递归返回深度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列?6.1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8 V1遍

32、历序列：遍历序列：V1V2 V2V4 V4V5V8 V8数据结构（数据结构（C版）版）清华大学出版社清华大学出版社深一层递归深一层递归递归返回递归返回深度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列?6.1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8 V1遍历序列：遍历序列：V1V2 V2V4 V4V5V8数据结构（数据结构（C版）版）清华大学出版社清华大学出版社深一层递归深一层递归递归返回递归返回深度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列?6.1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8 V1遍历序列：遍历序列：V1

33、 V7V2V4V5V8V3 V3V6 V6V7数据结构（数据结构（C版）版）清华大学出版社清华大学出版社2. 广度优先遍历广度优先遍历 基本思想基本思想： 访问顶点访问顶点v； 依次依次访问访问v的各个未被访问的邻接点的各个未被访问的邻接点v1, v2, , vk； 分别从分别从v1，v2，vk出发依次访问它们未被访问出发依次访问它们未被访问的邻接点，并使的邻接点，并使“先先被访问顶点的邻接点被访问顶点的邻接点”先先于于“后被访问顶点的邻接点后被访问顶点的邻接点”被访问。直至图中所有与被访问。直至图中所有与顶点顶点v有路径相通的顶点都被访问到。有路径相通的顶点都被访问到。6.1 图的逻辑结构图

34、的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社广度优先遍历序列广度优先遍历序列?入队序列入队序列?出队序列出队序列? 6.1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：遍历序列：V1V1数据结构（数据结构（C版）版）清华大学出版社清华大学出版社广度优先遍历序列广度优先遍历序列?入队序列入队序列?出队序列出队序列? 6.1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：遍历序列：V1V2V2V3V3数据结构（数据结构（C版）版）清华大学出版社清华大学出版社广度优先遍历序列广度优先遍历序列?入队序列入队序列?出队序列出队序列? 6.

35、1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：遍历序列：V1V2V3V3V4V4V5V5数据结构（数据结构（C版）版）清华大学出版社清华大学出版社广度优先遍历序列广度优先遍历序列?入队序列入队序列?出队序列出队序列? 6.1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：遍历序列：V1V2V3V4V4V5V5V6V6V7V7数据结构（数据结构（C版）版）清华大学出版社清华大学出版社广度优先遍历序列广度优先遍历序列?入队序列入队序列?出队序列出队序列? 6.1 图的逻辑结构图的逻辑结构V1V3V2V4V5V6V7V8遍历序列：遍历序列：V1V2V3V4

36、V5V5V6V6V7V7V8V8数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.2 图的存储结构及实现图的存储结构及实现是否可以采用顺序存储结构存储图是否可以采用顺序存储结构存储图?图的特点：顶点之间的关系是图的特点：顶点之间的关系是m: :n，即，即任何两任何两个顶点之间都可能存在关系（边），无法通过个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。无法采用顺序存储结构。如何存储图如何存储图?考虑图的定义，图是由顶点和边组成的，分别考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点

37、、如何存储边。考虑如何存储顶点、如何存储边。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社邻接矩阵（数组表示法）邻接矩阵（数组表示法）基本思想：用一个一维数组存储图中基本思想：用一个一维数组存储图中顶点顶点的信息，的信息，用一个二维数组（用一个二维数组（称为邻接矩阵称为邻接矩阵）存储图中各顶点）存储图中各顶点之间的之间的邻接邻接关系。关系。6.2 图的存储结构及实现图的存储结构及实现假设图假设图G(V，E)有有n个顶点，则邻接矩阵是一个个顶点，则邻接矩阵是一个nn的方阵，定义为：的方阵，定义为：arcij1 若若(vi, vj)E（或（或E）0 其它其它数据结构（数据结构（C版）版

38、）清华大学出版社清华大学出版社无向图的邻接矩阵的特点？无向图的邻接矩阵的特点？无向图的邻接矩阵无向图的邻接矩阵6.2 图的存储结构及实现图的存储结构及实现V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4主对角线为主对角线为 0 且一定是对称矩阵。且一定是对称矩阵。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社如何求顶点如何求顶点i的度？的度？无向图的邻接矩阵无向图的邻接矩阵6.2 图的存储结构及实现图的存储结构及实现V1V3V4V2V1 V2 V3 V4vertex=0

39、 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4邻接矩阵的第邻接矩阵的第i行（或第行（或第i列）非零元素的个数。列）非零元素的个数。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社如何判断顶点如何判断顶点 i 和和 j 之间是否存在边？之间是否存在边？无向图的邻接矩阵无向图的邻接矩阵6.2 图的存储结构及实现图的存储结构及实现V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4测试邻接矩阵中相应位置的元素测试邻接矩阵

40、中相应位置的元素arcij是否为是否为1。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社如何求顶点如何求顶点 i 的所有邻接点？的所有邻接点？无向图的邻接矩阵无向图的邻接矩阵6.2 图的存储结构及实现图的存储结构及实现V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4将数组中第将数组中第 i 行元素扫描一遍，若行元素扫描一遍，若arcij为为1，则，则顶点顶点 j 为顶点为顶点 i 的邻接点。的邻接点。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.2 图的

41、存储结构及实现图的存储结构及实现有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4有向图的邻接矩阵一定不对称吗？有向图的邻接矩阵一定不对称吗？不一定，例如有向完全图。不一定，例如有向完全图。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.2 图的存储结构及实现图的存储结构及实现有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V

42、2 V3 V4V1V2V3V4如何求顶点如何求顶点 i 的出度？的出度？邻接矩阵的第邻接矩阵的第 i 行元素之和。行元素之和。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.2 图的存储结构及实现图的存储结构及实现有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4如何求顶点如何求顶点 i 的入度？的入度？邻接矩阵的第邻接矩阵的第 i 列元素之和。列元素之和。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.2 图的存储结构及实

43、现图的存储结构及实现有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4如何判断从顶点如何判断从顶点 i 到顶点到顶点 j 是否存在边？是否存在边？测试邻接矩阵中相应位置的元素测试邻接矩阵中相应位置的元素arcij是否为是否为1。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社网图的邻接矩阵网图的邻接矩阵6.2 图的存储结构及实现图的存储结构及实现网图的邻接矩阵可定义为：网图的邻接矩阵可定义为： arcij wij 若若(vi, vj)E（或（

44、或E）0 若若i=j 其他其他V1V2V3V42785 0 2 5 0 0 8 7 0 arc=数据结构（数据结构（C版）版）清华大学出版社清华大学出版社邻接矩阵存储邻接矩阵存储无向图无向图的类的类const int MaxSize=10; template class Mgraph public: MGraph( (T a , int n, int e ) ); MGraph( )( ) void DFSTraverse( (int v) ); void BFSTraverse( (int v) ); private: T vertexMaxSize; int arcMaxSizeMaxSi

45、ze; int vertexNum, arcNum; ;6.2 图的存储结构及实现图的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社邻接矩阵中图的基本操作邻接矩阵中图的基本操作构造函数构造函数 1. 确定图的顶点个数和边的个数；确定图的顶点个数和边的个数；2. 输入顶点信息存储在一维数组输入顶点信息存储在一维数组vertex中；中；3. 初始化邻接矩阵；初始化邻接矩阵；4. 依次输入每条边存储在邻接矩阵依次输入每条边存储在邻接矩阵arc中；中； 4.1 输入边依附的两个顶点的序号输入边依附的两个顶点的序号i, j； 4.2 将邻接矩阵的第将邻接矩阵的第i行第行第j列的

46、元素值置为列的元素值置为1； 4.3 将邻接矩阵的第将邻接矩阵的第j行第行第i列的元素值置为列的元素值置为1；6.2 图的存储结构及实现图的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社template MGraph:MGraph(T a , int n, int e) vertexNum=n; arcNum=e; for (i=0; ivertexNum; i+) vertexi=ai; for (i=0; ivertexNum; i+) /初始化邻接矩阵初始化邻接矩阵 for (j=0; jvertexNum; j+) arcij=0; for (k=0; kij

47、; /边依附的两个顶点的序号边依附的两个顶点的序号 arcij=1; arcji=1; /置有边标志置有边标志 6.2 图的存储结构及实现图的存储结构及实现邻接矩阵中图的基本操作邻接矩阵中图的基本操作构造函数构造函数 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社邻接矩阵中图的基本操作邻接矩阵中图的基本操作深度优先遍历深度优先遍历template void MGraph:DFSTraverse( (int v) ) coutvertexv; visited v=1; for ( (j=0; jvertexNum; j+) ) if ( (arcvj=1 & visitedj=0)

48、) DFSTraverse( ( j ) );6.2 图的存储结构及实现图的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社邻接矩阵中图的基本操作邻接矩阵中图的基本操作广度优先遍历广度优先遍历template void MGraph:BFSTraverse( (int v) ) front=rear=- -1; /假设采用顺序队列且不会发生溢出假设采用顺序队列且不会发生溢出 coutvertexv; visitedv=1; Q+rear=v; while ( (front!=rear) ) v=Q+front; for ( (j=0; jvertexNum; j+) )

49、 if ( (arcvj=1 & visitedj=0 ) ) coutvertexj; visitedj=1; Q+rear=j; 6.2 图的存储结构及实现图的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社邻接表邻接表邻接表存储的基本思想：对于图的每个顶点邻接表存储的基本思想：对于图的每个顶点vi，将所将所有邻接于有邻接于vi的顶点链成一个单链表，称为顶点的顶点链成一个单链表，称为顶点vi的的边边表表（对于有向图则称为出边表），所有边表的头指（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维针和存储顶点信息的一维数组构成了数组构成了顶点表顶点表。 6

50、.2 图的存储结构及实现图的存储结构及实现图的邻接矩阵存储结构的空间复杂度？图的邻接矩阵存储结构的空间复杂度？如果为稀疏图则会出现什么现象？如果为稀疏图则会出现什么现象？ 假设图假设图G有有n个顶点个顶点e条边，则存储该图需要条边，则存储该图需要O(n2) 。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社邻接表有两种结点结构：顶点表结点和边表结点邻接表有两种结点结构：顶点表结点和边表结点。vertexfirstedge adjvex next 顶点表顶点表 边边 表表 vertex：数据域，存放顶点信息。数据域，存放顶点信息。 firstedge：指针域，指向边表中第一个结点。指针

51、域，指向边表中第一个结点。 adjvex：邻接点域，边的终点在顶点表中的下标。邻接点域，边的终点在顶点表中的下标。next：指针域，指向边表中的下一个结点。指针域，指向边表中的下一个结点。 6.2 图的存储结构及实现图的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社struct ArcNode int adjvex; ArcNode *next;template struct VertexNode T vertex; ArcNode *firstedge;定义邻接表的结点定义邻接表的结点 6.2 图的存储结构及实现图的存储结构及实现vertexfirstedge ad

52、jvex next数据结构（数据结构（C版）版）清华大学出版社清华大学出版社10323101 V1 V2 V3 V40123vertex firstedge6.2 图的存储结构及实现图的存储结构及实现V1V3V4V2无向图的邻接表无向图的邻接表边表中的结点表示什么？边表中的结点表示什么？每个结点对应图中的一条边，每个结点对应图中的一条边，邻接表的空间复杂度为邻接表的空间复杂度为O(n+e)。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社10323101 V1 V2 V3 V40123vertex firstedge6.2 图的存储结构及实现图的存储结构及实现V1V3V4V2无向图的

53、邻接表无向图的邻接表如何求顶点如何求顶点 i 的度？的度？顶点顶点i的边表中结点的个数。的边表中结点的个数。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社如何判断顶点如何判断顶点 i 和顶点和顶点 j之间是否存在边之间是否存在边?测试顶点测试顶点 i 的边表中是否存的边表中是否存在终点为在终点为 j 的结点。的结点。6.2 图的存储结构及实现图的存储结构及实现10323101 V1 V2 V3 V40123vertex firstedgeV1V3V4V2无向图的邻接表无向图的邻接表数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.2 图的存储结构及实现图的存储结构及实现

54、有向图的邻接表有向图的邻接表V1V2V3V41220 V1 V2 V3 V40123vertex firstedge如何求顶点如何求顶点 i 的出度？的出度？顶点顶点 i 的出边表中结点的个数。的出边表中结点的个数。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.2 图的存储结构及实现图的存储结构及实现有向图的邻接表有向图的邻接表V1V2V3V41220 V1 V2 V3 V40123vertex firstedge如何求顶点如何求顶点 i 的入度？的入度？各顶点的出边表中以顶点各顶点的出边表中以顶点 i 为为终点的结点个数。终点的结点个数。数据结构（数据结构（C版）版）清华大学

55、出版社清华大学出版社6.2 图的存储结构及实现图的存储结构及实现有向图的邻接表有向图的邻接表V1V2V3V41230 V1 V2 V3 V40123vertex firstedge如何求顶点如何求顶点 i 的所有邻接点？的所有邻接点？遍历顶点遍历顶点 i 的边表，该边表中的的边表，该边表中的所有终点都是顶点所有终点都是顶点 i 的邻接点。的邻接点。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社6.2 图的存储结构及实现图的存储结构及实现网图的邻接表网图的邻接表V1V2V3V427852 1 V1 V2 V3 V40123vertex firstedge5 28 37 0数据结构（数

56、据结构（C版）版）清华大学出版社清华大学出版社邻接表存储邻接表存储有向图有向图的的类类const int MaxSize=10; /图的最大顶点数图的最大顶点数template class ALGraph public: ALGraph( (T a , int n, int e) ); ALGraph; void DFSTraverse( (int v) ); void BFSTraverse( (int v) ); private: VertexNode adjlistMaxSize; int vertexNum, arcNum; ;6.2 图的存储结构及实现图的存储结构及实现数据结构（数据

57、结构（C版）版）清华大学出版社清华大学出版社邻接表中图的基本操作邻接表中图的基本操作构造函数构造函数 1. 确定图的顶点个数和边的个数；确定图的顶点个数和边的个数；2. 输入顶点信息，初始化该顶点的边表；输入顶点信息，初始化该顶点的边表；3. 依次输入边的信息并存储在边表中；依次输入边的信息并存储在边表中； 3.1 输入边所依附的两个顶点的序号输入边所依附的两个顶点的序号i和和j； 3.2 生成邻接点序号为生成邻接点序号为j的边表结点的边表结点s； 3.3 将结点将结点s插入到第插入到第i个边表的头部；个边表的头部；6.2 图的存储结构及实现图的存储结构及实现数据结构（数据结构（C版）版）清华

58、大学出版社清华大学出版社template ALGraph:ALGraph(T a , int n, int e) vertexNum=n; arcNum=e; for (i=0; ivertexNum; i+) /输入顶点信息，初始化边表输入顶点信息，初始化边表 adjlisti.vertex=ai; adjlisti.firstedge=NULL; 6.2 图的存储结构及实现图的存储结构及实现邻接表中图的基本操作邻接表中图的基本操作构造函数构造函数 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社s for (k=0; kij; s=new ArcNode; s-adjvex=j;

59、 s-next=adjlisti.firstedge; adjlisti.firstedge=s; 6.2 图的存储结构及实现图的存储结构及实现12 V1 V2 V3 V40123数据结构（数据结构（C版）版）清华大学出版社清华大学出版社邻接表中图的基本操作邻接表中图的基本操作深度优先遍历深度优先遍历template void ALGraph:DFSTraverse( (int v) ) cout-adjvex; if ( (visitedj=0) ) DFSTraverse( (j) ); p=p-next; 6.2 图的存储结构及实现图的存储结构及实现数据结构（数据结构（C版）版）清华大学

60、出版社清华大学出版社邻接表中图的基本操作邻接表中图的基本操作广度优先遍历广度优先遍历template void ALGraph:BFSTraverse( (int v) ) front=rear=- -1; cout-adjvex; if ( (visitedj=0) ) cout-next; 6.2 图的存储结构及实现图的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社十字链表十字链表 邻接表邻接表6.2 图的存储结构及实现图的存储结构及实现逆邻接表逆邻接表将邻接表与逆邻接表合二为一将邻接表与逆邻接表合二为一?为什么要合并？为什么要合并？V1V2V3V412 3 0v