tailieunhanh - Lecture Algorithms and data structures - Chapter 29: Graphs - BF&DF Traversal

This chapter extends your knowledge of query formulation to advanced matching problems. To solve these advanced matching problems, additional parts of the SELECT statement are introduced. This chapter continues with the learning approaches of Chapter 4: provide many examples to imitate and problem-solving guidelines to help you reason through difficult problems. | Review Graph Directed Graph Undirected Graph Sub-Graph Spanning Sub-Graph Degree of a Vertex Weighted Graph Elementary and Simple Path Link List Representation 1 Traversing a Graph Breadth First Search (BFS) Depth First Search (DFS) 2 Traversing a Graph Many application of graph requires a structured system to examine the vertices and edges of a graph G That is a graph traversal, which means visiting all the nodes of the graph There are two graph traversal methods (a) Breadth First Search (BFS) Think Queue (b) Depth First Search (DFS) Think Stack 3 Overview Goal To systematically visit the nodes of a graph A tree is a directed, acyclic, graph (DAG) If the graph is a tree, DFS is exhibited by preorder, postorder, and (for binary trees) inorder traversals BFS is exhibited by level-order traversal 4 Example 0 7 1 5 4 3 2 6 Policy: Visit adjacent nodes in increasing index order 5 Preorder DFS: Start with Node 5 0 7 1 5 4 3 2 6 5 1 0 3 2 7 6 4 6 Preorder DFS: Start with Node 5 0 7 1 5 4 3 2 6 5 Push 5 7 Preorder DFS: Start with Node 5 0 7 1 5 4 3 2 6 5 Pop/Visit/Mark 5 8 Preorder DFS: Start with Node 5 0 7 1 5 4 3 2 6 5 1 2 Push 2, Push 1 9 Preorder DFS: Start with Node 5 0 7 1 5 4 3 2 6 5 1 2 Pop/Visit/Mark 1 10 Preorder DFS: Start with Node 5 0 7 1 5 4 3 2 6 5 1 0 2 4 2 Push 4, Push 2, Push 0 11 Preorder DFS: Start with Node 5 0 7 1 5 4 3 2 6 5 1 0 2 4 2 Pop/Visit/Mark 0 12 Preorder DFS: Start with Node 5 0 7 1 5 4 3 2 6 5 1 0 3 7 2 4 2 Push 7, Push 3 13 Preorder DFS: Start with Node 5 0 7 1 5 4 3 2 6 5 1 0 3 7 2 4 2 Pop/Visit/Mark 3 14 Preorder DFS: Start with Node 5 0 7 1 5 4 3 2 6 5 1 0 3 2 7 2 4 2 Push 2 15 Preorder DFS: Start with Node 5 0 7 1 5 4 3 2 6 5 1 0 3 2 7 2 4 2 Pop/Mark/Visit 2 16 Preorder DFS: Start with Node 5 0 7 1 5 4 3 2 6 5 1 0 3 2 7 2 4 2 Pop/Mark/Visit 7 17 Preorder DFS: Start with Node 5 0 7 1 5 4 3 2 6 5 1 0 3 2 7 6 2 4 2 Push 6 18 Preorder DFS: Start with Node 5 0 7 1 5 4 3 2 6 5 1 0 3 2 7 6 2 4 2 Pop/Mark/Visit 6 19 Preorder DFS: Start with | Review Graph Directed Graph Undirected Graph Sub-Graph Spanning Sub-Graph Degree of a Vertex Weighted Graph Elementary and Simple Path Link List Representation 1 Traversing a Graph Breadth First Search (BFS) Depth First Search (DFS) 2 Traversing a Graph Many application of graph requires a structured system to examine the vertices and edges of a graph G That is a graph traversal, which means visiting all the nodes of the graph There are two graph traversal methods (a) Breadth First Search (BFS) Think Queue (b) Depth First Search (DFS) Think Stack 3 Overview Goal To systematically visit the nodes of a graph A tree is a directed, acyclic, graph (DAG) If the graph is a tree, DFS is exhibited by preorder, postorder, and (for binary trees) inorder traversals BFS is exhibited by level-order traversal 4 Example 0 7 1 5 4 3 2 6 Policy: Visit adjacent nodes in increasing index order 5 Preorder DFS: Start with Node 5 0 7 1 5 4 3 2 6 5 1 0 3 2 7 6 4 6 Preorder DFS: Start with Node 5 0 7 1 5 4 3