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

• Cơ sở dữ liệu
• Data structures
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Design techniques
• Cấu trúc dữ liệu
• Ebook Data structures and algorithms made easy
• Data structures and algorithms made easy
• Data structures and algorithmic puzzles
• Data structures for storing strings
• Algorithms design techniques
• algorithms
• data structure lectures
• structured document data
• teaching data structures
• algorithms in data structures
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Programming assignments
• Data structures organize data
• Resource constraints
• Lecture Data structures and algorithms
• Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Lecture ECE 250
• Memory allocation
• Computer science
• Design of data structures
• Algorithms in Java
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming