Graph Theory Interview Questions and Answers

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.).

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. 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.

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.

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).

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.

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.

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.

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(
n2) space complexity)

Inefficient when the graph is sparse, meaning that there is a lot less edges than N2 nodes. It is slow to iterate over all edges It is slow to add/delete a node; a complex operation

O(
n2)

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

Whenever someone gives you a problem, think graphs. They are the most fundamental and flexible way of representing any kind of a relationship. Computer Networks: Graphs model intuitively model computer networks and the Internet. Often nodes will represent end-systems or routers, while edges represent connections between these systems. Data Structures: Any data structure that makes use of pointers to link data together is making use of a graph of some kind. This includes tree structures and linked lists which are used all the time.

Pathing and Maps: Trying to find shortest or longest paths from some location to a destination makes use of graphs. This can include pathing like you see in an application like Google maps, or calculating paths for AI characters to take in a video game, and many other similar problems. Constraint Satisfaction: A common problem in AI is to find some goal that satisfies a list of constraints. For example, for a University to set it's course schedules, it needs to make sure that certain courses don't conflict, that a professor isn't teaching two courses at the same time, that the lectures occur during certain timeslots, and so on. Constraint satisfaction problems like this are often modeled and solved using graphs. Molecules: Graphs can be used to model atoms and molecules for studying their interaction and structure among other things. Project management related problems. A sequence of events can be pictured as a directed graph (if you don't have cycles then thats even better). So, now you can sort the events according to their priority, find the event that is the most crucial (that is would free a lot of other projects), find the duration needed to solve the total project (path problem), etc. Your source code is tree structured, and a tree is a type of graph. Whenever you hear people talking about an AST (Abstract Syntax Tree), they're talking about a kind of graph. State machines are graphs. State machines are used in network protocols, regular expressions, games, and all kinds of other fields. Program optimization algorithms that compilers use are based on graphs (e.g., figure out call graph, flow control, lots of static analysis). Optical character recognition. Picture a page of text scanned at an angle, with some noise in the image, where you must find the space between lines of text. Dependence graphs. Graphs can be used to represent dependences or precedences among items. Such graphs are often used in large projects in laying out what components rely on other components and used to minimize the total time or cost to completion while abiding by the dependences.

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.

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. 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.

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

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.

[ [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.

[ [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.

[ [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
1
2
3
4
A graph
{"1" : [[2, 1], [3,1]],
  "2" : [[3, 3]],
  "3" : [[4, 4]],
  "4" : [[1, 5]]}
Adjacency matrixAdjacency list
[[0, 1, 1, 0],
[0, 0, 3, 0],
[0, 0 ,0 , 4],
[5, 0, 0 ,0]]
1
1
34
5

Say, you have a connected graph with V nodes and E edges. In DFS, you traverse each node exactly once. Therefore, the time complexity of DFS is at least O(V) .

Now, any additional complexity comes from how you discover all the outgoing paths or edges for each node which, in turn, is dependent on the way your graph is implemented. If an edge leads you to a node that has already been traversed, you skip it and check the next. Typical DFS implementations use a hash table to maintain the list of traversed nodes so that you could find out if a node has been encountered before in O(1)

time (constant time).

If your graph is implemented as an adjacency matrix (a V x V array), then, for each node, you have to traverse an entire row of length V in the matrix to discover all its outgoing edges. Please note that each row in an adjacency matrix corresponds to a node in the graph, and the said row stores information about edges stemming from the node. So, the complexity of DFS is O(V * V) = O(V^2) . If your graph is implemented using adjacency lists, wherein each node maintains a list of all its adjacent edges, then, for each node, you could discover all its neighbors by traversing its adjacency list just once in linear time. For a directed graph, the sum of the sizes of the adjacency lists of all the nodes is E (total number of edges). So, the complexity of DFS is O(V) + O(E) = O(V + E) . For an undirected graph, each edge will appear twice. Once in the adjacency list of either end of the edge. So, the overall complexity will be O(V) + O (2E) ~ O(V + E) . There are different other ways to implement a graph. You can reason the complexity accordingly.

A graph is bipartite when the graph vertices are parted into two disjoint sets; no two adjacent vertices would reside in the same set. A bipartite graph must not contain odd cycle (a cycle with an odd number of vertices). BFS (Breadth First Search) can be used in detecting a bipartite graph. Another method of checking a bipartite graph is to check the occurrence of an odd cycle in the graph.

Key differences between BFS and DFS are: BFS is vertex-based algorithm while DFS is an_ edge-based_ algorithm. Queue data structure is used in BFS. On the other hand, DFS uses stack or recursion. Memory space is efficiently utilised in DFS ( O(log n) ) while space utilisation in BFS ( O(n) ) is not effective. A depth-first search uses a stack, which contains nodes from root to the node being searched. So at most the radius of the graph (or depth of the tree). A breadth-first search uses a queue, which contains nodes at the front of the search. So at most all nodes at distance d. If you have a balanced (or mostly so) k-ary tree, it's depth, i.e. radius, will be only O(log n) , while the lowest layer will contain O(n) nodes ( n/2 for binary tree and even more for higher degrees). BFS is optimal algorithm while DFS is not optimal. DFS may produce a much longer path than BFS. DFS constructs narrow and long trees. As against, BFS constructs wide and short tree. 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).

In general it may or may not depending on the particular graph. A depth-first search uses a stack, which contains nodes from root to the node being searched. So at most the radius of the graph. A breadth-first search uses a queue, which contains nodes at the front of the search. So at most all nodes at distance d. In general graph all you can say is that it's at most all nodes in the tree in either case. But if you have a balanced

(or mostly so)
k-ary tree, it's depth, i.e. radius, will be only O(log n) , while the lowest layer will contain O(n)
nodes ( n/2 for binary tree and even more for higher degrees). For example, in a (balanced) tree with 1023

nodes the DFS has to keep track of 10 nodes, while the BFS has to keep track of 512 nodes. So depth-first search will only use O(log n) memory and breadth-first search will use O(n) . For balanced k-ary trees; for other cases different results are possible (but for most common graphs diameter will still be significantly less than circumference). Note that BFS doesn't always use more memory: More specifically, BFS uses O(branchingFactor^maxDepth) or O(maxWidth) memory, where-as DFS only uses

O(maxDepth) .
If maxWidth < maxDepth , BFS should use less memory (assuming you use similar representations for both), but

this is rarely true.

First think about: BSF searches for siblings first. DFS obviously searches for children first. So relationship type searches across fields would probably lend itself to BFS, where hierarchical (trees, folders, ranks, etc) would be more suited as a DFS. BFS is going to use more memory depending on the branching factor ( O(branchingFactor^maxDepth) ), however, BFS is a complete algorithm meaning if you are using it to search for something in the lowest depth possible, BFS will give you the optimal solution. BFS space complexity is O(b^d) , the branching factor raised to the

depth (can be a lot of memory).

DFS on the other hand, is much better about space however it may find a suboptimal solution. Meaning, if you are just searching for a path from one vertex to another, you may find the suboptimal solution (and stop there) before you find the real shortest path. DFS space complexity is O(|V|) ... meaning that the most memory it can take up is the longest possible path (the radius of the graph). The time complexity for both is O(b^d) meaning it is based on the branching factor and the depth searched. BFS and DFS have the same worst case that is searching the entire tree. In terms of implementation, BFS is usually implemented with Queue , while DFS uses a Stack . Some other considerations you may apply: If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better. If the tree is very deep and solutions are rare, depth first search (DFS) might take an extremely long time, but BFS could be faster. If the tree is very wide, a BFS might need too much memory, so it might be completely impractical. If solutions are frequent but located deep in the tree, BFS could be impractical. If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).

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) . The cost function is calculated as a sum of two other functions: g(x) - The function that represents the cost of moving from the starting node to a given node. h(x) - The estimated cost from the given node to the goal node.

f(x) = g(x)+h(x)

We obviously don't know the exact movement cost from the given note to the goal node, which is the reason why h(x) is also often referred to as the "heuristic". The calculation of h(x) can be done in various ways: The Manhattan distance from node n to the goal is often used. This is a standard heuristic for a grid. It's measured as he distance between two points measured along axes at right angles. In a plane with p1 at (x1, y1) and p2 at (x2, y2) , it is |x1 - x2| + |y1 - y2| .

function heuristic(node) =
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
return D * (dx + dy)

The Euclidean Distance Heuristic. If your units can move at any angle (instead of grid directions), then

you should probably use a straight line distance:

function heuristic(node) =
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
return D * sqrt(dx * dx + dy * dy)
If h(x) = 0 , A* becomes

Dijkstra's algorithm, which is guaranteed to find a shortest path. The heuristic function must be: admissible, h(x) <= dist(x, t) , which means it can never overestimate the cost to reach the goal. Both the Manhattan distance and h(x) = 0 are admissible. monotone, h(u) <= cost(u, v) + h(v) (triangle inequality) It must be cheap to compute. It should be certainly O(1) , and should preferably look at the current node alone. The algorithm always picks the node with the lowest f(x) value. The fewer steps we take from the starting point combined with how close we get to the goal makes the value of f(x) lower if we're going with the shortest path to the goal. Walking away from the goal, and making more steps than needed to get there increases the f(x) function.

The most prominent and extreme example that illustrates the difference in peak memory consumption between DFS and BFS (as well as pseudo-DFS) is a star-graph: a single central vertex surrounded by a large number (say, 1000 ) of peripheral vertices, with each peripheral vertex connected to the central vertex by an edge. If you run BFS on this graph using the central vertex as origin, the queue size will immediately jump to 1000 . The same thing will obviously happen if you use pseudo-DFS (i.e. if you simply replace the queue with a stack). But classic DFS algorithm will need stack depth of only 1 (!) to traverse this entire graph. See the difference? 1000 versus 1 . This is what is meant by better space efficiency of DFS.

Best-first search algorithm visits next state based on heuristics function

f(n) = h with lowest heuristic value
(often called greedy). It doesn't consider cost of the path to that particular state. All it cares about is
that which next state from the current state has lowest heuristics. Heuristic evaluation function f(n) , in

general, may depend on the description of n , the description of the goal, the information gathered by the search up to that point, and most important, on any extra knowledge about the problem domain. A* search algorithm visits next state based on heuristics

f(n) = h + g where
h component is same heuristics
applied as in Best-first search but

g component is path from the initial state to the particular state. Therefore it doesn't chooses next state only with lowest heuristics value but one that gives lowest value when considering it's heuristics and cost of getting to that state.