连通和DFS ■深度优先搜索(DFS)算法 ·从图中的一个指定顶点出发，有序地遍历和该顶点连通的所有顶点 ●遍历顶点的顺序是优先向图的“深处”访问，即倾向于远离出发点 算法2.1：DFS 输人：图G=(V,E),顶点u 初值：V中所有顶点的visited初值为false e6 1u.visited←-true; eA 2 foreach(u,v)∈Edo e2 3 if v.visited false then DFS(G,v); 2023/2/27 26
n 深度优先搜索（DFS）算法 l 从图中的一个指定顶点出发，有序地遍历和该顶点连通的所有顶点 l 遍历顶点的顺序是优先向图的“深处”访问，即倾向于远离出发点 2023/2/27 26 连通和DFS
连通和DFS ■深度优先搜索(DFS)算法 ·从图中的一个指定顶点出发，有序地遍历和该顶点连通的所有顶点 ●遍历顶点的顺序是优先向图的“深处”访问，即倾向于远离出发点 算法2.1：DFS 输人：图G=(V,E),顶点u 初值：V中所有顶点的visited初值为false e6 1u.visited←-true; eA 2 foreach(u,v)∈Edo e NA 3 if v.visited false then 4 DFS(G,v); 2023/2/27 27
n 深度优先搜索（DFS）算法 l 从图中的一个指定顶点出发，有序地遍历和该顶点连通的所有顶点 l 遍历顶点的顺序是优先向图的“深处”访问，即倾向于远离出发点 2023/2/27 27 连通和DFS
连通和DFS ■深度优先搜索(DFS)算法 ·从图中的一个指定顶点出发，有序地遍历和该顶点连通的所有顶点 ●遍历顶点的顺序是优先向图的“深处”访问，即倾向于远离出发点 算法2.1：DFS e 输人：图G=(V,E),顶点u 初值：V中所有顶点的visited初值为false e6 1u.visited←-true; eA 2 foreach(u,v)∈Edo N 3 if v.visited false then DFS(G,v); 2023/2/27 28
n 深度优先搜索（DFS）算法 l 从图中的一个指定顶点出发，有序地遍历和该顶点连通的所有顶点 l 遍历顶点的顺序是优先向图的“深处”访问，即倾向于远离出发点 2023/2/27 28 连通和DFS
连通和DFS ■深度优先搜索(DFS)算法 ·从图中的一个指定顶点出发，有序地遍历和该顶点连通的所有顶点 ●遍历顶点的顺序是优先向图的“深处”访问，即倾向于远离出发点 算法2.1：DFS 输人：图G=(V,E),顶点u e 初值：V中所有顶点的visited初值为false e6 1u.visited←-true; eA 2 foreach(u,v)∈Edo e 3 if v.visited false then 4 DFS(G,v); es 2023/2/27
n 深度优先搜索（DFS）算法 l 从图中的一个指定顶点出发，有序地遍历和该顶点连通的所有顶点 l 遍历顶点的顺序是优先向图的“深处”访问，即倾向于远离出发点 2023/2/27 29 连通和DFS
连通和DFS ■深度优先搜索(DFS)算法 ·从图中的一个指定顶点出发，有序地遍历和该顶点连通的所有顶点 ●遍历顶点的顺序是优先向图的“深处”访问，即倾向于远离出发点 ■从顶点u出发运行DFS算法，为什么恰能访问与连通的所有顶点？ ●为什么连通的都能访问？ ·为什么访问的都连通？ 算法2.1：DFS e3 输人：图G=(V,E),顶点u 初值：V中所有顶点的visited初值为false e6 1u.visited←-true; 2 foreach(u,v)∈Edo A 3 if v.visited false then DFS(G,v); 2023/2/27 30
n 深度优先搜索（DFS）算法 l 从图中的一个指定顶点出发，有序地遍历和该顶点连通的所有顶点 l 遍历顶点的顺序是优先向图的“深处”访问，即倾向于远离出发点 n 从顶点u出发运行DFS算法，为什么恰能访问与u连通的所有顶点？ l 为什么连通的都能访问？ l 为什么访问的都连通？ 2023/2/27 30 连通和DFS