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 .
