Graph Algorithms

Prereq: Graph Intro

Tree vs Graph Traversal

A Tree is a connected, acyclic undirected graph. Statistically, most interview graph problems are about connected and undirected graphs. So for simplicity, we're gonna define a tree as a graph without cycle. The search algorithms we have learned in tree modules are applicable to graphs as well.

Hopefully, by this point, you are very familiar with DFS on tree and BFS on tree. Since the difference between a tree and a graph is the potential of having a cycle, we just have to handle this situation. We use an extra visited to keep track of vertices we have already visited to prevent re-visiting and getting into infinite loops. visited can be any data structure that can answer existence queries quickly. For example, a hash set or an array where each element maps to a vertex in the graph can both do this in constant time.



Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

  >>> a = [1, 2, 3]
  >>> a[-1]

Get premium for instant access to all content and solutions