tailieunhanh - Depth-First Search

Depth-First Search From the given vertex, visit one of its adjacent vertices and leave others; Then visit one of the adjacent vertices of the previous vertex; Continue the process, visit the graph as deep as possible until. | Depth-First Search 1. 2. 3. From the given vertex, visit one of its adjacent vertices and leave others; Then visit one of the adjacent vertices of the previous vertex; Continue the process, visit the graph as deep as possible until: A visited vertex is reached; An end vertex is reached. Depth-First Traversal 1. 2. 3. 4. 5. 6. 7. Depth-first traversal of a graph: Start the traversal from an arbitrary vertex; Apply depth-first search; When the search terminates, backtrack to the previous vertex of the finishing point, Repeat depth-first search on other adjacent vertices, then backtrack to one level up. Continue the process until all the vertices that are reachable from the starting vertex are visited. Repeat above processes until all vertices are visited. 0 source 0 8 9 2 1 4 3 source 5 7 6 8 9 2 1 4 3 5 7 6 1 Algorithm The pseudocode of depth-first traversal algorithm: Boolean visited[]; void DepthFirst(Graph G) { Vertex u; for each vertex u in V do visited[u] = false; for each vertex u in V do if visited[u] = false then RDFS(u); } void RDFS(Vertex u){ visited[u] = true; Visit(u); for each vertex w in Adj[u] do if visited[w] = false then RDFS(w); } Example: Depth-First Traversal An adjacent list of a graph: 2 Example: Depth-First Traversal Function calls of depth-first traversal of the graph visit 0 visit 7 (first on 0’s list) visit 1 (first on 7’s list) check 7 on 1’s list check 0 on 1’s list visit 2 (second on 7’s list) check 7 on 2’s list check 0 on 2’s list check 0 on 7’s list visit 4 (fourth on 7’s list) visit 6 (first on 4’s list) check 4 on 6’s list check 0 on 6’s list Example: Depth-First Traversal visit 5 (second on 4’s list) check 0 on 5’s list check 4 on 5’s list visit 3 (third on 5’s list) check 5 on 3’s list check 4 on 3’s list check 7 on 4’s list check 3 on 4’s list check 5 on 0’s list check 2 on 0’s list check 1 on 0’s list check 6 on 0’s list End recursive calls 3 Using a stack DFS can be implemented with stack, since

• Cơ sở dữ liệu
• Depth First Search
• Depth First Traversal
• Using a stack
• The paths traversed by BFS
• BFS tree
• Path finding with DFS
• Advanced Algorithms Analysis and Design
• Lecture Advanced Algorithms Analysis and Design
• Bài giảng Phân tích và thiết kế thuật toán nâng cao
• Breadth first search algorithm
• Parenthesis theorem
• công nghệ thông tin
• cơ sở dữ liệu
• giải thuật
• Depth First Search (DFS)
• White path theorem
• Applications of depth first search
• Strongly connected components
• Distributed Systems
• Lecture Distributed Systems
• Wave Traversal
• Traversal algorithms
• Classical depth first search
• Classical depth first search algorithm
• State space search
• State space of the 8 puzzle
• State space of tic tac toe
• Search Strategies
• Iterative Deepening
• Lecture Data Structure and Algorithms
• Data Structure and Algorithms
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Breath First Search
• Implement storage structures for graphs using C/C++
• Lecture Algorithms
• Bài giảng Thuật toán
• Undirected Graphs
• Breadth first search
• Graph definition
• thuật toán Depth First Search
• xác định đỉnh kề trong DFS
• độ phức tạp của thuật toán
• tài liệu học đại học
• các tính chất của BFS
• Algorithms unplugged
• Insertion sort
• Fast sorting algorithms
• Parallel sorting
• Cycles in graphs
• Distributed computing
• Distributed systems communication
• Theory of distributed computing
• Message Passing Systems
• Depth First search spanning tree
• Share memory systems