南京大学：《图论与算法》课程教案讲稿（Graph Theory and Algorithms, GTA）第03周 连通和遍历

商有京大竖 NANJING UNIVERSITY 第2章连通和遍历 程龚 2023/2/27

第2章 连通和遍历 程龚 2023/2/27 1

遍历一上帝视角 ■它能爬到所有顶点吗？如何爬？ e e3 e2 eA V4 es 2023/2/27

n 它能爬到所有顶点吗？如何爬？ 2023/2/27 2 遍历——上帝视角 v1 v2 v3 v4 e1 e2 e3 e4 e5

遍历—蚂蚁视角 ■我能爬到所有顶点吗？如何爬？ VI V3 e e2 es VA 2023/2/27

n 我能爬到所有顶点吗？如何爬？ 2023/2/27 3 遍历——蚂蚁视角 v1 v2 v3 v4 e1 e2 e4

遍历—蚂蚁视角 确保爬过有可能爬到的所有顶点， 并减少不必要的重复爬行 V3 e es N4 2023/2/27

n 确保爬过有可能爬到的所有顶点， 并减少不必要的重复爬行 2023/2/27 4 遍历——蚂蚁视角 v1 v2 v3 v4 e1 e2 e4

遍历—第一人称视角 风山公方适地八困号 ←经图 上 五广道 林中 小 1m 人大 南南工大样口有经石器区送保司 1 2中n 子 d 大 南京地铁 https://www.njmetro.com.cn/njdtweb/dtweb/images/map_new.jpg http://www.dianping.com/review/833785054 2023/2/27

2023/2/27 5 遍历——第一人称视角 https://www.njmetro.com.cn/njdtweb/dtweb/images/map_new.jpg http://www.dianping.com/review/833785054

本次课的主要内容 2.1连通和DFS 2.2割点和割边 2.3距离和BFS 2023/2/27

2.1 连通和DFS 2.2 割点和割边 2.3 距离和BFS 2023/2/27 6 本次课的主要内容

本次课的主要内容 2.1连通和DFS 2.2割点和割边 2.3距离和BFS 2023/2/27

2.1 连通和DFS 2.2 割点和割边 2.3 距离和BFS 2023/2/27 7 本次课的主要内容

连通和DFS ■路线：以顶点开始、顶点和边交替出现、以顶点结束的序列 voe1,V1,…ehv,其中每条边e,的两个端点恰为顶点y和v ●起点：0 ●终点：w ●长度：1 e3 e6 e2 2 eA V4 es 2023/2/27 8

n 路线：以顶点开始、顶点和边交替出现、以顶点结束的序列 v0, e1, v1, … el , vl ，其中每条边ei 的两个端点恰为顶点vi-1和vi l 起点：v0 l 终点：vl l 长度：l 2023/2/27 8 连通和DFS v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6

连通和DFS ■f 路线：以顶点开始、顶点和边交替出现、以顶点结束的序列 vo,e1,V1,…ez,v,其中每条边e,的两个端点恰为顶点y1和y ●起点：o ●终点： ●长度：1 V5 e3 ■平凡路线：1=0 e6 V2 es e2 V4 es 2023/2/27 9

n 路线：以顶点开始、顶点和边交替出现、以顶点结束的序列 v0, e1, v1, … el , vl ，其中每条边ei 的两个端点恰为顶点vi-1和vi l 起点：v0 l 终点：vl l 长度：l n 平凡路线：l = 0 2023/2/27 9 连通和DFS v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6

连通和DFS ■路线：以顶点开始、顶点和边交替出现、以顶点结束的序列 vo,e1,V1,.e,v1,其中每条边e的两个端点恰为顶点y.1和v ●起点：% ●终点：w ●长度：1 e3 ■平凡路线：1=0 e6 V2 eA ■迹：路线，且边在序列中不重复出现 V3 2023/2/27 10

n 路线：以顶点开始、顶点和边交替出现、以顶点结束的序列 v0, e1, v1, … el , vl ，其中每条边ei 的两个端点恰为顶点vi-1和vi l 起点：v0 l 终点：vl l 长度：l n 平凡路线：l = 0 n 迹：路线，且边在序列中不重复出现 2023/2/27 10 连通和DFS v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6