Interview Questions on Graphs (C Language)

šŸ“˜ Basic Graph Concepts ā€“ Short Answer Interview Questions

  1. How are graphs represented in C?
    Typically using adjacency matrix or adjacency list structures.
  2. What is the difference between adjacency matrix and adjacency list?
    Matrix uses 2D array (O(VĀ²) space), list uses array of linked lists (O(V+E) space).
  3. How do you implement a graph using adjacency list in C?
    Use array of struct nodes, where each node contains linked list of neighbors.
  4. What are the advantages of adjacency matrix representation?
    O(1) edge lookup, simple implementation for dense graphs.
  5. When would you prefer adjacency list over adjacency matrix?
    For sparse graphs, when memory efficiency is important.
  6. What is the time complexity of DFS on a graph?
    O(V + E) where V is vertices, E is edges.
  7. How do you detect a cycle in an undirected graph?
    Use DFS and check for back edges to visited nodes.
  8. What is the difference between BFS and DFS?
    BFS explores level by level, DFS goes deep first.
  9. Can a graph be represented using structures in C?
    Yes, typically with a struct containing vertex count and adjacency information.
  10. How do you find the shortest path in an unweighted graph?
    Use BFS which naturally finds shortest paths in unweighted graphs.
  11. What is topological sorting and where is it used?
    Linear ordering of vertices where u comes before v for every directed edge (u,v). Used in task scheduling.
  12. How do you implement Dijkstra's algorithm in C?
    Use priority queue to always expand the least-cost node, updating distances.
  13. What is a spanning tree of a graph?
    Subgraph that is a tree and connects all vertices together.
  14. How do you find minimum spanning tree using Kruskal's algorithm?
    Sort edges by weight, add them in order if they don't form a cycle (using Union-Find).
  15. What is the use of const in graph function parameters?
    Prevents modification of graph structure through the pointer.
  16. How do you represent a weighted graph in C?
    In adjacency matrix: store weights instead of 1/0. In list: include weight in edge nodes.
  17. What is the role of static keyword when used with graph variables inside a function?
    Preserves graph content between function calls.
  18. How do you dynamically allocate memory for a graph?
    Use malloc for adjacency matrix or array of linked lists for adjacency list.
  19. What does the realloc function do for dynamic graphs?
    Resizes dynamically allocated graph memory while preserving content.
  20. How do you pass a subgraph to a function?
    Pass pointer to starting vertex and optionally size information.
  21. What is pointer arithmetic and how is it related to graph adjacency matrices?
    Pointer arithmetic lets you navigate matrix rows/columns using pointer offsets.
  22. How do you implement graph traversal without recursion?
    Use explicit stack for DFS or queue for BFS.
  23. How do you find connected components in a graph?
    Use DFS or BFS to explore all reachable nodes from each unvisited node.
  24. What is a dynamic graph and how is it implemented in C?
    Graph that can grow/shrink at runtime using malloc/realloc.
  25. How do you transpose a graph (reverse all edges)?
    For adjacency matrix: transpose the matrix. For list: build new list with reversed edges.
  26. Can graphs be returned from functions in C?
    Return pointer to graph structure or dynamically allocated memory.
  27. What's the difference between shallow and deep copying graphs?
    Shallow copy copies pointers only; deep copy duplicates entire graph structure.
  28. How do you merge two graphs into one?
    Combine vertex sets and edge sets, handling duplicates appropriately.
  29. What is the difference between stack and heap allocation of graphs?
    Stack: fixed size, fast. Heap: dynamic size, must be manually managed.
  30. What is the time complexity of inserting a new vertex in a graph?
    O(1) for adjacency list, O(V) for adjacency matrix (need to resize).

šŸ“— Advanced Graph Algorithms ā€“ Short Answer Interview Questions

  1. How do you implement Floyd-Warshall algorithm in C?
    Use triple nested loops to compute all-pairs shortest paths through intermediate nodes.
  2. What is the memory layout of an adjacency list in C?
    Array of pointers, each pointing to a linked list of adjacent nodes.
  3. Difference between directed and undirected graph representation?
    Undirected: edges appear twice in adjacency list. Directed: once.
  4. Can you dynamically allocate an array of graphs? How?
    Yes. Allocate array of graph pointers, then allocate each graph individually.
  5. How do you find articulation points in a graph?
    Use DFS with discovery times and low values to identify critical nodes.
  6. What is the difference between cyclic and acyclic graphs?
    Cyclic contains cycles, acyclic does not (like trees).
  7. How do you implement Bellman-Ford algorithm?
    Relax all edges V-1 times, then check for negative weight cycles.
  8. How do you find all possible paths between two nodes?
    Use modified DFS that backtracks and records paths.
  9. How to find the shortest path in a graph with negative weights?
    Use Bellman-Ford algorithm which handles negative weights.
  10. How do you pass an array of graphs to a function?
    As Graph *arr[] or Graph **arr parameter.
  11. Can you return an array of graphs from a function?
    Return pointer to dynamically allocated array of graphs.
  12. How do you implement Prim's algorithm for MST?
    Use priority queue to always add the minimum weight edge from growing MST.
  13. What happens if you access graph index out of bounds?
    Leads to undefined behavior or segmentation fault.
  14. What is a graph pool and how does it work?
    Memory area where identical graph components may share storage.
  15. How do you initialize an array of graphs with empty graphs?
    Use Graph arr[N] = {NULL}; or loop to initialize each.
  16. How do you check if a graph is bipartite?
    Use BFS/DFS with two-coloring, checking for conflicts.
  17. How do you find strongly connected components in a directed graph?
    Use Kosaraju's algorithm (two-pass DFS) or Tarjan's algorithm.
  18. How to compute maximum flow in a flow network?
    Use Ford-Fulkerson method with BFS (Edmonds-Karp implementation).
  19. What are common pitfalls in graph implementation?
    Memory leaks, incorrect edge representation, cycle detection errors.
  20. What is the space complexity of storing a graph with V vertices and E edges?
    O(VĀ²) for matrix, O(V+E) for adjacency list representation.
Related Graph Resources
Basic Programs
MCQs
Problem Solving Tricks
Tech Hub