Top 19 Graph Theory Interview Questions And Answers

Question 1

What is a Graph?

Accepted Answer

A **graph** is a common data structure that consists of a finite set of **nodes** (or **vertices**) and a set of **edges** connecting them. A pair `(x,y)` is referred to as an edge, which communicates that the **x vertex** connects to the **y vertex**.

Graphs are used to solve real-life problems that involve representation of the problem space as a **network**. Examples of networks include telephone networks, circuit networks, social networks (like LinkedIn, Facebook etc.).

![](https://miro.medium.com/max/1640/1*4s5Z7gVwVqmKcslgiamRyw.png)

Question 2

What's the difference between the data structure Tree and Graph?

Accepted Answer

**Graph:**
* Consists of a set of vertices (or nodes) and a set of edges connecting some or all of them
* Any edge can connect any two vertices that aren't already connected by an identical edge (in the same direction, in the case of a directed graph)
* Doesn't have to be connected (the edges don't have to connect all vertices together): a single graph can consist of a few disconnected sets of vertices
* Could be directed or undirected (which would apply to all edges in the graph)

**Tree:**
* A type of graph (fit with in the category of Directed Acyclic Graphs (or a DAG))
* Vertices are more commonly called "nodes"
* Edges are directed and represent an "is child of" (or "is parent of") relationship
* Each node (except the root node) has exactly one parent (and zero or more children)
* Has exactly one "root" node (if the tree has at least one node), which is a node without a parent
* Has to be connected
* Is acyclic, meaning it has no cycles: "a cycle is a path [AKA sequence] of edges and vertices wherein a vertex is reachable from itself"
* Trees aren't a recursive data structure

![](https://miro.medium.com/max/2262/1*-yHATwTlY2hwceJ93-D-cw.jpeg)

Question 3

List some ways of representing Graphs

Accepted Answer

* **Edge Lists**. We have an array of two vertex numbers, or an array of objects containing the vertex numbers of the vertices that the edges are incident on (plus weight). Edge lists are simple, but if we want to find whether the graph contains a particular edge, we have to search through the edge list. If the edges appear in the edge list in no particular order, that's a linear search through `E` edges.
```js
[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5], [3,8], [4,5], [4,9], [7,8], [7,9] ]
```
* **Adjacency Matrices.** With an adjacency matrix, we can find out whether an edge is present in constant time, by just looking up the corresponding entry in the matrix - we can query whether edge `(i, j)` is in the graph by looking at `graph[i][j]` value. For a sparse graph, the adjacency matrix is mostly `0s`, and we use lots of space to represent only a few edges. For an undirected graph, the adjacency matrix is _symmetric_.
```js
[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
  [1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
  [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
  [0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
  [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
  [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]
```
* **Adjacency Lists**. For each vertex `i`, store an array of the vertices adjacent to it (or array of _tuples_ for weighted graph). To find out whether an edge `(i,j)` is present in the graph, we go to `i's` adjacency list in constant time and then look for `j` in `i's` adjacency list.
```js
[ [1, 6, 8],   // 0
  [0, 4, 6, 9],  // 1
  [4, 6],        // 2
  [4, 5, 8],
  [1, 2, 3, 5, 9],
  [3, 4],
  [0, 1, 2],
  [8, 9],
  [0, 3, 7],
  [1, 4, 7] ]    // N
```

![](https://www.educative.io/api/edpresso/shot/6738347923865600/image/4587527119831040)

Question 4

Name some common types and categories of Graphs

Accepted Answer

* In an **undirected graph**, nodes are connected by edges that are all _bidirectional_. For example if an edge connects node 1 and 2, we can traverse from node 1 to node 2, and from node 2 to 1. * In a **directed graph**, nodes are connected by directed edges – they only go in _one direction_. For example, if an edge connects node 1 and 2, but the arrow head points towards 2, we can only traverse from node 1 to node 2 – not in the opposite direction. * A **weight** is a numerical value attached to each individual edge. If edges in our graph have weights then your graph is said to be a **weighted graph** * if the edges do not have weights, the graph is said to be **unweighted** * A **cyclic graph** is a directed graph which contains a path from at least one node back to itself. In simple terms cyclic graphs contain a cycle. * An **acyclic graph** is a directed graph which contains absolutely no cycle, that is no node can be traversed back to itself. * **Dense graph** is a graph in which the number of edges is close to the _maximal (max)_ number of edges. * **Sparse graph** is a graph in which the number of edges is close to the _minimal (min)_ number of edges. Sparse graph can be a **disconnected** graph.
![](https://dist.neo4j.com/wp-content/uploads/20181121091034/graph-properties-graph-algorithms-2.png)
* A graph is **connected** if any two vertices of the graph are connected by a path. * A graph is **disconnected** if at least two vertices of the graph are not connected by a path. ![](https://i1.wp.com/www.steveclarkapps.com/wp-content/uploads/2019/03/Screenshot-2019-04-30-at-15.15.11.png?resize=812%2C330&ssl=1) * In a **multigraph**, there can be more than one edge from vertex 1 to vertex 2. * In a **simple graph** there is at most one. ![](https://miro.medium.com/max/1536/1*gc_apWNe2s9lXzbvl_HTYg.png)

Question 5

Provide some practical examples of using Depth-First Search (DFS) vs Breadth-First Search (BFS)?

Accepted Answer

* **Depth-first searches** are often used in simulations of games (and game-like situations in the real world). In a typical game you can choose one of several possible actions. Only some paths in a game tree lead to your win. Some lead to a win by your opponent, when you reach such an ending, you must back up, or backtrack, to a previous node and try a different path. In this way you explore the tree until you find a path with a successful conclusion. Another example, given a family tree if one were looking for someone on the tree who’s still alive, then it would be safe to assume that person would be on the bottom of the tree. This means that a BFS would take a very long time to reach that last level. A DFS, however, would find the goal faster.

* The **breadth-first search** has an interesting property: It first finds all the vertices that are one edge away from the starting point, then all the vertices that are two edges away, and so on. This is useful if you’re trying to find the shortest path from the starting vertex to a given vertex. Breadth-first search can be used for finding the neighbour nodes in peer to peer networks like BitTorrent, GPS systems to find nearby locations, social networking sites to find people in the specified distance.

Question 6

Explain what is `A*` Search?

Accepted Answer

**A*** (pronounced as "A star") is a computer algorithm that is widely used in _pathfinding_ and _graph traversal_. The algorithm efficiently plots a walkable path between multiple nodes, or points, on the graph. It's used to handle real-life pathfinding scenarios. Most NPCs and AI players rely on A* to intelligently search for a path, fast and efficient.

A* search relies on a knowledge and **heuristic cost function** for the given node as a way to decide which node it should visit next. In most cases, this cost function is denoted as `f(x)`. A* is an extension of _Dijkstra's algorithm_ with some characteristics of _breadth-first search (BFS)_.

Question 7

What is difference between BFS and Dijkstra's algorithms when looking for shortest path?

Accepted Answer

* **Breadth-first search** is just Dijkstra's algorithm with all edge weights equal to 1. 
  - BFS basically just expands the search by one “step” (link, edge, whatever you want to call it in your application) on every iteration, which happens to have the effect of finding the smallest number of steps it takes to get to any given node from your source (“root”)
  - Breadth-first search can be viewed as a special-case of Dijkstra's algorithm on unweighted graphs, where the priority queue degenerates into a FIFO queue. 
  - Operations on a regular queue are `O(1)`. 
  - BFS runs in `O(E+V)`.

* **Dijkstra's** algorithm is conceptually breadth-first search that _respects_ edge costs. 
  - For example, in routing the distances (or weights) could be assigned by speed, cost, preference, etc.
  - Dijkstra's uses a priority queue data structure to keep track of the frontier of unvisited nodes. 
  - Operations on a priority queue are `O(log n)`. 
  - Dijkstra's runs in `O((V+E)*log(V))`

The process for exploring the graph is structurally the same in both cases.

Question 8

Explain what is DFS (Depth First Search) algorithm for a Graph and how does it work?

Accepted Answer

**Depth First Traversal** or **Depth First Search** is a **edge based** _recursive_ algorithm for traversing (visiting) all the vertices of a graph or tree data structure using a **stack**. The purpose of the algorithm is to mark each vertex as visited while _avoiding_ cycles. DFS traverse/visit each vertex exactly once and each edge is inspected exactly twice. DFS is a genuinely recursive algorithm that uses stack for _backtracking_ purposes, not for storing the vertex discovery "front" (as is the case in BFS).

The **DFS** algorithm works as follows:

* Start by putting any one of the graph's vertices on top of a **stack**.
* Take the top item of the stack and add it to the **visited list**.
* Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the top of the stack.
* Keep repeating steps 2 and 3 until the stack is empty.

**DFS example step-by-step**:
* Considering A as the starting vertex which is explored and stored in the stack.
* B successor vertex of A is stored in the stack.
* Vertex B have two successors E and F, among them alphabetically E is explored first and stored in the stack.
* The successor of vertex E, i.e., G is stored in the stack.
* Vertex G have two connected vertices, and both are already visited, so G is popped out from the stack.
* Similarly, E s also removed.
* Now, vertex B is at the top of the stack, its another node(vertex) F is explored and stored in the stack.
* Vertex F has two successor C and D, between them C is traversed first and stored in the stack.
* Vertex C only have one predecessor which is already visited, so it is removed from the stack.
* Now vertex D connected to F is visited and stored in the stack.
* As vertex D doesn’t have any unvisited nodes, therefore D is removed.
* Similarly, F, B and A are also popped.
* The generated output is – A, B, E, G, F, C, D.

![](https://techdifferences.com/wp-content/uploads/2017/10/Untitledeeg.jpg)

Question 9

Compare Adjacency Lists or Adjacency Matrices for Graphs representation

Accepted Answer

In graph theory, a graph representation is a technique to store graph into the memory of computer. * **Adjacency Matrix**. Adjacency matrix is a _sequential_ representation so it can be represented as an **array**. In this representation, we have to construct a NxN matrix A. If there is any edge from a vertex i to vertex j, then the corresponding element of A, `a(i, j) = 1`, otherwise `a(i, j)= 0`. * **Pros**: * Representation is easier to implement and follow * It is fast to lookup and check for presence or absence of a specific edge between any two nodes O(1) * It is fast to add a new edge O(1) * **Cons**: * It takes a lot of space (O(n²) space complexity) * Inefficient when the graph is sparse, meaning that there is a lot less edges than N^{2 nodes.
* It is slow to iterate over all edges
* It is slow to add/delete a node; a complex operation O(n²)

![](https://static.javatpoint.com/tutorial/graph-theory/images/graph-representations1.png)

* **Adjacency List**. Adjacency list is a _linked_ representation. In this representation, for each vertex in the graph, we maintain the list of its _neighbours_. It means, every vertex of the graph contains list of its adjacent vertices.
* **Pros**:
* Memory usage depends on the number of edges (not number of nodes), which might save a lot of memory if the adjacency matrix is sparse
* It is fast to iterate over all edges because you can access any node neighbors directly
* It is fast to add/delete a node; easier than the matrix representation
* It fast to add a new edge O(1)
* **Cons**:
* Finding the presence or absence of specific edge between any two nodes is slightly slower than with the matrix `O(k)`; where `k` is the number of neighbours nodes

![](https://static.javatpoint.com/tutorial/graph-theory/images/graph-representations5.png)}

Question 10

Explain the BSF (Breadth First Search) traversing method

Accepted Answer

**Breadth First Search** (**BFS**) is the traversing method used in graphs. It uses a queue for storing the visited vertices. In this method the emphasize is on the vertices of the graph, one vertex is selected at first then it is visited and marked. The vertices adjacent to the visited vertex are then visited and stored in the queue sequentially. A node is fully explored before visiting any other node in the graph, in other words, it traverses shallowest unexplored nodes first.

The **BST** algorithm works as follows:

* Start by putting any one of the graph's vertices at the back of a **queue**.
* Take the front item of the queue and add it to the visited list.
* Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the back of the queue.
* Keep repeating steps 2 and 3 until the queue is empty.

**BST** example **step-by-step**:

We have a graph whose vertices are A, B, C, D, E, F, G. Considering A as starting point. The steps involved in the process are:

* Vertex A is expanded and stored in the queue.
* Vertices B, D and G successors of A, are expanded and stored in the queue meanwhile Vertex A removed.
* Now B at the front end of the queue is removed along with storing its successor vertices E and F.
* Vertex D is at the front end of the queue is removed, and its connected node F is already visited.
* Vertex G is removed from the queue, and it has successor E which is already visited.
* Now E and F are removed from the queue, and its successor vertex C is traversed and stored in the queue.
* At last C is also removed and the queue is empty which means we are done.
* The generated Output is – A, B, D, G, E, F, C.

![](https://techdifferences.com/wp-content/uploads/2017/10/BFS-correction.jpg)

Top 19 Graph Theory Interview Questions

What is a Graph?

What's the difference between the data structure Tree and Graph?

List some ways of representing Graphs

Name some common types and categories of Graphs

What is difference between BFS and Dijkstra's algorithms when looking for shortest path?

Explain what is DFS (Depth First Search) algorithm for a Graph and how does it work?

What are some applications of Graphs?

Provide some practical examples of using Depth-First Search (DFS) vs Breadth-First Search (BFS)?

Explain what is `A*` Search?

Compare Adjacency Lists or Adjacency Matrices for Graphs representation

Explain the BSF (Breadth First Search) traversing method

What is Bipartite Graph? How to detect one?

Explain what is heuristic cost function in `A*` Search and how to calculate one?

Why does a Breadth First Search (BFS) use more memory than Depth First Search (DFS)?

How do we know whether we need to use BSF or DSF algorithm?

Why is the complexity of DFS `O(V+E)`?

What are key differences between BFS and DFS?

Illustrate the difference in peak memory consumption between DFS and BFS

What's the difference between best-first search and `A*` Search?

Top 19 Graph Theory Interview Questions

What is a Graph?

What's the difference between the data structure Tree and Graph?

List some ways of representing Graphs

Name some common types and categories of Graphs

What is difference between BFS and Dijkstra's algorithms when looking for shortest path?

Explain what is DFS (Depth First Search) algorithm for a Graph and how does it work?

What are some applications of Graphs?

Provide some practical examples of using Depth-First Search (DFS) vs Breadth-First Search (BFS)?

Explain what is A* Search?

Compare Adjacency Lists or Adjacency Matrices for Graphs representation

Explain the BSF (Breadth First Search) traversing method

What is Bipartite Graph? How to detect one?

Explain what is heuristic cost function in A* Search and how to calculate one?

Why does a Breadth First Search (BFS) use more memory than Depth First Search (DFS)?

How do we know whether we need to use BSF or DSF algorithm?

Why is the complexity of DFS O(V+E)?

What are key differences between BFS and DFS?

Illustrate the difference in peak memory consumption between DFS and BFS

What's the difference between best-first search and A* Search?

Explain what is `A*` Search?

Explain what is heuristic cost function in `A*` Search and how to calculate one?

Why is the complexity of DFS `O(V+E)`?

What's the difference between best-first search and `A*` Search?