连通和DFS ■f 路线：以顶点开始、顶点和边交替出现、以顶点结束的序列 vo,e1,V1,.e,vh,其中每条边e,的两个端点恰为顶点V1和v ●起点：o ●终点：7 ●长度：1 V5 e e3 ■平凡路线：1=0 e6 eA ■迹：路线，且边在序列中不重复出现 e2 V2 VA ■路：迹，且顶点在序列中不重复出现 ·内顶点：路中除起点和终点外的其它顶点 es 2023/2/27 11
n 路线：以顶点开始、顶点和边交替出现、以顶点结束的序列 v0, e1, v1, … el , vl ，其中每条边ei 的两个端点恰为顶点vi-1和vi l 起点：v0 l 终点：vl l 长度：l n 平凡路线：l = 0 n 迹：路线，且边在序列中不重复出现 n 路：迹，且顶点在序列中不重复出现 l 内顶点：路中除起点和终点外的其它顶点 2023/2/27 11 连通和DFS v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6
连通和DFS ■若图中存在-v路线，则一定存在u-v迹吗？ ●V3,e2,2,e4,V4,e3,V1,e1,'2,e4,V4 ■若图中存在-v迹，则一定存在v路吗？ e3 e6 V2 es e2 V4 V3 2023/2/27 12
n 若图中存在u-v路线，则一定存在u-v迹吗？ l v3, e2, v2, e4, v4, e3, v1, e1, v2, e4, v4 n 若图中存在u-v迹，则一定存在u-v路吗？ 2023/2/27 12 连通和DFS v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6
连通和DFS ■若图中存在-v路线，则一定存在-v迹吗？ ●V3,e2,V2,e4,v4,e3,V1,e1,v2,e4,V4 ■若图中存在-v迹，则一定存在-v路吗？ ■若图中存在v路线和v-1w路线 则一定存在v路线吗？ e e3 e6 eA e2 V4 es 2023/2/27
n 若图中存在u-v路线，则一定存在u-v迹吗？ l v3, e2, v2, e4, v4, e3, v1, e1, v2, e4, v4 n 若图中存在u-v迹，则一定存在u-v路吗？ n 若图中存在u-v路线和v-w路线， 则一定存在u-w路线吗？ 2023/2/27 13 连通和DFS v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6
连通和DFS ■顶点u和v连通：存在-v路 V5 e e3 e6 eA e V2 V4 es V3 2023/2/27 14
n 顶点u和v连通：存在u-v路 2023/2/27 14 连通和DFS v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6
连通和DFS ■顶点u和v连通：存在-v路 ■连通关系是定义在顶点集上的等价关系。 V5 e e e6 eA e2 V2 V4 es 3 2023/2/27
n 顶点u和v连通：存在u-v路 n 连通关系是定义在顶点集上的等价关系。 2023/2/27 15 连通和DFS v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6