TAILIEUCHUNG - Lecture Data structures and algorithms in Java (6th edition): Chapter 14.2 - Goodrich, Tamassia, Goldwasser

This chapter provides knowledge of DFS. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Depth-First Search 3/25/14 15:22 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Depth-First Search A B D E C © 2014 Goodrich, Tamassia, Goldwasser Depth-First Search 1 Subgraphs q   A subgraph S of a graph G is a graph such that n   n   q   The vertices of S are a subset of the vertices of G The edges of S are a subset of the edges of G Subgraph A spanning subgraph of G is a subgraph that contains all the vertices of G Spanning subgraph © 2014 Goodrich, Tamassia, Goldwasser Depth-First Search 2 1 Depth-First Search 3/25/14 15:22 Connectivity q   q   A graph is connected if there is a path between every pair of vertices A connected component of a graph G is a maximal connected subgraph of G © 2014 Goodrich, Tamassia, Goldwasser Connected graph Non connected graph with two connected components Depth-First Search 3 Trees and Forests q   A (free) tree is an undirected graph T such that T is connected n   T has no cycles This definition of tree is different from the one of a rooted tree n   q   q   A forest is an undirected graph without cycles The connected components of a forest are trees © 2014 Goodrich, Tamassia, Goldwasser Depth-First Search Tree Forest 4 2 Depth-First Search 3/25/14 15:22 Spanning Trees and Forests q   q   q   q   A spanning tree of a connected graph is a spanning subgraph that is a tree A spanning tree is not unique unless the graph is a tree Spanning trees have applications to the design of communication networks A spanning forest of a graph is a spanning subgraph that is a forest Graph Spanning tree © 2014 Goodrich, Tamassia, Goldwasser Depth-First Search 5 Depth-First Search q   q   Depth-first search (DFS) is a general technique for traversing a graph A DFS traversal of a graph G n   n   n   n   Visits all the vertices and edges of G Determines whether G .

• Cơ sở dữ liệu
• Data structures
• Data structures and algorithms
• Computer science
• Design of data structures
• Algorithms in Java
• 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
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Lecture ECE 250
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Memory allocation
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming