CITS2200 - Lecture 20

← Back to Home

CITS2200 - Lecture 19
Depth-First Search - Slides

Graph Concepts Recap

Subgraphs

• Subgraph $-$ vertices and edges are subset of larger graph

  

• Spanning subgraph $-$ subgraph that contains all vertices of graph

  

Connectivity

• A graph is connected if there is a path between every pair of vertices

  

• A connected component is a maximal connected subgraph

  

Trees and Forests

• A free tree is an undirected and connected graph with no cycles

  • Different from rooted tree!

  

• A forest is an undirected graph without cycles

  • i.e. it is composed of smaller trees (and possibly lone vertices)

  

• A spanning tree is a tree that is also a spanning subgraph

  • The edges must be chosen carefully to prevent cycles

  

• A spanning forest is a forest that is also a spanning subgraph

---

Depth-First Search

• Depth-first search (DFS) is a traversal technique used commonly for rooted trees and graphs
  • It explores as deeply as possible before backtracking
  • For rooted trees, it starts at the root and traverses to a leaf

As DFS explores, edges get classified:

• Discovery edge $-$ leads to an unexplored vertex
  • Forms the DFS spanning tree
• Back edge $-$ leads to an already-visited vertex
  • Indicates a cycle in the graph

DFS of a graph $G$, must start at a vertex, known as $v$

• If we encounters every vertex in the graph, then $G$ is a connected graph
• Otherwise, DFS must be called for every connected component of $G$

---

Properties of DFS

• Property 1 $-$ $DFS(G,v)$ visits all vertices and edges in the connected component of $v$
• Property 2 $-$ discovery edges form a spanning tree of the connected component of $v$

Complexity Analysis of DFS

Assuming we are using an adjacency list representation:

Operation	Cost
Label a vertex or edge	$O(1)$
Each vertex labeled twice (UNEXPLORED → VISITED)	$O(n)$ total
Each edge labeled twice	$O(m)$ total
incidentEdges called once per vertex	$O(m)$ total
Total	$O(n+m)$

---

Applications of DFS

• Path finding $-$ find a path between two vertices
  • Push vertices onto a stack S
  • When you hit your destination, return S.elements() → path
• Cycle Detection $-$ find a simple cycle
  • Wait until a back edge is found
  • Then pop stack until original vertex is reached
  • Popped elements form the cycle

---

CITS2200 - Lecture 21