expertfunda logo Top Interview Questions Binary Tree Binary Search Tree Graph

Graph Problems and Terminology

Graph Problems and Graph Terminology - expertfunda
Graph For Faang
Crispy Things in Graph
Graph Problems and Tricks
Shortest Path in Graph
Mastering Graph Algorithm

Cheatsheet for graph Problems in the coding interviews

Graph Problems and Graph Terminology are important to understand the syllabus of FAANG Interviews preparation.

What is important and what should be cover before jumping over problem, is important.

Since, if we skip a topic to understand the graph theory then you will always skip to solve the problem and so we should not skip any graph theory topics.

So, Let's see the common graph problems that we will discuss in future articles.

The common graph problems are categorized as below:

1. Traversal Problems

Traversal problems in graph includes navigating all the nodes of a graph (or visiting the all vertices of a graph).

Graph Traversal is similar in concept to a tree traversal.

The tree traversals visit every node exactly once in preorder, inorder, or postorder.

There are many tree traversals algorithms exist because many problems need the nodes to be visited in a particular order.

Similarly Graph Traversal algorithms starts from a starting vertex and try to visit the remaining vertices from there.

We can find many possible trouble cases:-

There may be possibility that we are unable to reach all the vertices from a starting vertex.

This occurs when the graph is not connected.

Another problem can found like the graph might contain cycles

We must make sure that this cycle should not cause the traversal algorithm to go into infinite loop.

So, there are two main traversal algorithms:-

  • 1. Breadth-First Search (BFS):

    • Find the shortest path in an unweighted graph.

    • Level-order traversal in trees.

  • 2. Depth-First Search (DFS):

    • Find connected components in a graph.

    • Detect cycles in a graph.

    • Topological sorting of a Directed Acyclic Graph (DAG).

2. Shortest Path Problems

  • Dijkstra's Algorithm:

    • Find the shortest path from a source vertex to all other vertices in a weighted graph with non-negative weights.

  • Bellman-Ford Algorithm:

    • Find the shortest path from a source vertex to all other vertices in a graph that may have negative weights.

  • Floyd-Warshall Algorithm:

    • Find shortest paths between all pairs of vertices in a weighted graph.

  • A* Algorithm:

    • Find the shortest path in a weighted graph using heuristics (used in pathfinding algorithms).

Please checkout our best article on Shortest path in a graph.

Shortest path in a graph

3. Minimum Spanning Tree (MST) Problems

  • Kruskal’s Algorithm:

    • Find the Minimum Spanning Tree (MST) of a graph using a union-find data structure.

  • Prim’s Algorithm:

    • Find the MST by growing the tree from an initial vertex using a priority queue.

4. Cycle Detection Problems

  • Cycle Detection in Directed Graphs:

    • Use DFS to detect cycles in a directed graph (e.g., to check if a graph is a DAG).

  • Cycle Detection in Undirected Graphs:

    • Use union-find data structure to detect cycles in an undirected graph.

5. Connectivity Problems

  • Connected Components:

    • Find all connected components in an undirected graph.

  • Articulation Points:

    • Find vertices whose removal increases the number of connected components.

  • Bridges:

    • Find edges whose removal increases the number of connected components.

6. Topological Sorting

  • Topological Sorting:

    • Order vertices in a Directed Acyclic Graph (DAG) such that for every directed edge (u, v), vertex u comes before v.

7. Graph Coloring

  • Graph Coloring:

    • Assign colors to vertices of a graph such that no two adjacent vertices share the same color (used in scheduling problems).

  • Chromatic Number:

    • Determine the minimum number of colors needed to color a graph.

8. Flow Problems

  • Maximum Flow:

    • Find the maximum flow from a source to a sink in a flow network (using algorithms like Ford-Fulkerson, Edmonds-Karp).

  • Minimum Cut:

    • Find the smallest cut (set of edges) that separates the source and sink in a flow network.

9. Matching Problems

  • Maximum Bipartite Matching:

    • Find the maximum matching in a bipartite graph (e.g., job assignment problems).

  • Hungarian Algorithm:

    • Solve the assignment problem where each task is assigned to exactly one worker to minimize cost.

10. Distance Problems

  • Diameter of a Graph:

    • Find the longest shortest path between any pair of vertices in a graph.

  • K-Shortest Paths:

    • Find multiple shortest paths between two vertices in a weighted graph.

These problems cover a broad spectrum of graph theory and are commonly encountered in various domains, including computer science, operations research, and optimization.