本次课的主要内容 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