Skip to main content

Graph Introduction

Here are some important topics related to graphs that are commonly covered in technical interviews:

  1. Graph representation: How to represent a graph in memory, including adjacency matrix and adjacency list representations.
  2. Traversal algorithms: How to traverse a graph, including Depth-First Search (DFS) and Breadth-First Search (BFS).
  3. Shortest path algorithms: How to find the shortest path between two nodes in a graph, including Dijkstra's algorithm and A*.
  4. Minimum spanning tree algorithms: How to find a minimum spanning tree in a graph, including Kruskal's algorithm and Prim's algorithm.
  5. Topological sorting: How to order the nodes in a directed acyclic graph (DAG) such that for every directed edge uv, vertex u comes before v in the ordering using DFS or Kahn's Algorithm.
  6. Disjoint Set Union (Union Find): Given an element, how to find the set that it belongs to and Given two sets, how to merge them into a single set.
  7. Strongly connected components: How to find the strongly connected components in a directed graph, using Tarjan's algorithm and Kosaraju's Algorithm.
  8. Graph coloring: How to color the nodes in a graph such that no two adjacent nodes have the same color, using the Welsh-Powell algorithm or the DSATUR algorithm.
  9. Maximum flow: How to find the maximum flow in a flow network, using the Ford-Fulkerson algorithm or the Edmonds-Karp algorithm.
  10. Network flow: How to model and solve network flow problems, including the max-flow min-cut theorem and the Ford-Fulkerson algorithm.
  11. Graph theory concepts: Understanding of basic graph theory concepts, such as degrees of a node, connectedness, and bipartiteness.

It's also helpful to be familiar with various types of graphs, such as directed and undirected graphs, weighted and unweighted graphs, and tree and cycle graphs.

Standard Graph Problems​

  1. Cycle Detection
  2. Articulation Point
  3. Disjoint Set Union

Topics​