Graph Algorithms Cheat Sheet For Coding Interviews

# Using a BFS algorithm
import collections
def bfs(graph, root):

    visited, queue = set(), collections.deque([root])
    visited.add(root)

    while queue:
        # Dequeuing a vertex from queue
        vertex = queue.popleft()
        print(str(vertex) + " ", end="")

        # If not visited, marking it as visited, and

# enqueuing it
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)


if __name__ == '__main__':
    graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
    print("Below is the Breadth First Traversal: ")
    bfs(graph, 0)

# Using DFS algorithm
def dfs(graph, start, visited=None):
 if visited is None:
        visited = set()
    visited.add(start)

    print(start)

    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited


graph = {'0': set(['1', '2']),
         '1': set(['0', '3', '4']),
         '2': set(['0']),
         '3': set(['1']),
         '4': set(['2', '3'])}

dfs(graph, '0')

import sys
 
# Providing the graph with vertices and edges
v_graph = [[0, 0, 1, 1, 0, 0, 0],
                  [0, 0, 1, 0, 0, 1, 0],
                  [1, 1, 0, 1, 1, 0, 0],
                  [1, 0, 1, 0, 0, 0, 1],
                  [0, 0, 1, 0, 0, 1, 0],
                  [0, 1, 0, 0, 1, 0, 1],
                  [0, 0, 0, 1, 0, 1, 0]]
 
e_graph = [[0, 0, 1, 2, 0, 0, 0],
               [0, 0, 2, 0, 0, 3, 0],
               [1, 2, 0, 1, 3, 0, 0],
               [2, 0, 1, 0, 0, 0, 1],
               [0, 0, 3, 0, 0, 2, 0],
               [0, 3, 0, 0, 2, 0, 1],
               [0, 0, 0, 1, 0, 1, 0]]
 
# Finding the vertex that has to be visited next
def node_to_visit():
 
   global visited_and_distance
    v = -10
    for index in range(vertices):
        if visited_and_distance[index][0] == 0 /
            and (v < 0 or visited_and_distance[index][1] <=
                 visited_and_distance[v][1]):
            v = index
    return v
 
 
vertices = len(v_graph[0])
 
visited_and_distance = [[0, 0]]
for i in range(vertices-1):
    visited_and_distance.append([0, sys.maxsize])
 
for vertex in range(vertices):
 
    # Finding next vertex to be visited
    to_visit = node_to_visit()
    for neighbor_index in range(vertices):
 
        # Updating new distances
        if v_graph[to_visit][neighbor_index] == 1 and /
                visited_and_distance[neighbor_index][0] == 0:
            new_distance = visited_and_distance[to_visit][1] /
                + e_graph[to_visit][neighbor_index]
            if visited_and_distance[neighbor_index][1] > new_distance:
                visited_and_distance[neighbor_index][1] = new_distance
 
        visited_and_distance[to_visit][0] = 1
 
i = 0
 
# Printing the distance
for distance in visited_and_distance:
    print("Computed Distance of ", chr(ord('a') + i),
          " from source vertex is: ", distance[1])
    i = i + 1

# Using Bellman-Ford Algorithm
class Graph:
 
    def __init__(self, vertices):
        self.V = vertices # Vertices in the graph
        self.graph = [] # Array of edges
 
# Adding edges
    def add_edge(self, s, d, w):
        self.graph.append([s, d, w])
 
    # Printing the solution
    def print_solution(self, dist):
        print("Vertex Distance from Source")
        for i in range(self.V):
            print("{0}/t/t{1}".format(i, dist[i]))
 
    def bellman_ford(self, src):
 
        # Filling the distance array and predecessor array
        dist = [float("Inf")] * self.V
        # Marking the source vertex
        dist[src] = 0
 
        # Relaxing edges |V| - 1 times
        for _ in range(self.V - 1):
            for s, d, w in self.graph:
                if dist[s] != float("Inf") and dist[s] + w < dist[d]:
                    dist[d] = dist[s] + w
 
        # Step 3: Detecting negative cycle in a graph
        for s, d, w in self.graph:
            if dist[s] != float("Inf") and dist[s] + w < dist[d]:
                print("Graph contains negative weight cycle")
                return
 
        # No negative weight cycle found!
        # Printing the distance and predecessor array
 
        self.print_solution(dist)
g = Graph(5)
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 4)
g.add_edge(1, 3, 3)
g.add_edge(2, 1, 6)
g.add_edge(3, 2, 2)
 
g.bellman_ford(0)

# Total number of vertices
vertices = 4
 
INF = 999
 
# implementing the floyd-warshall algorithm
def floyd_warshall(Graph):
    distance = list(map(lambda a: list(map(lambda b: b, a)), Graph))
 
    # Adding the vertices individually
    for k in range(vertices):
        for a in range(vertices):
            for b in range(vertices):
                distance[a][b] = min(distance[a][b], distance[a][k] + distance[k][b])
    solution(distance)
 
 
# Printing the desired solution
def solution(distance):
    for a in range(vertices):
        for b in range(vertices):
            if(distance[a][b] == INF):
                print("INF", end=" ")
            else:
                print(distance[a][b], end=" ")
        print(" ")
 
 
Graph = [[0, 3, INF, 5],
         [2, 0, INF, 4],
         [INF, 1, 0, INF],
         [INF, INF, 2, 0]]
floyd_warshall(Graph)

INF = 9999999
# graph's vertices
vertices = 5
 
# graph representation
graph = [[0, 9, 75, 0, 0],
         [9, 0, 95, 19, 42],
         [75, 95, 0, 51, 66],
         [0, 19, 51, 0, 31],
         [0, 42, 66, 31, 0]]
 
# creating an array for tracking the selected vertex
selected_vertex = [0, 0, 0, 0, 0]
# setting the number of edges to 0
number_of_edges = 0
 
# choosing 0th vertex and setting it to True
selected_vertex[0] = True
# printing the edge and the corresponding weight
print("Edge : Weight/n")
while (number_of_edges < vertices - 1):
    min = INF
    a = 0
    b = 0
    for i in range(vertices):
        if selected_vertex[i]:
            for j in range(vertices):
                if ((not selected_vertex[j]) and graph[i][j]):
                    if min > graph[i][j]:
                        min = graph[i][j]
                        a = i
                        b = j
    print(str(a) + "-" + str(b) + ":" + str(graph[a][b]))
    selected_vertex[b] = True
    number_of_edges += 1

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []
 
    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])
 
    # Search function
 
    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])
 
def apply_union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1
 
    # Applying Kruskal’s algorithm
    def kruskal_algo(self):
        result = []
        i, e = 0, 0
        self.graph = sorted(self.graph, key=lambda item: item[2])
        parent = []
        rank = []
        for node in range(self.V):
            parent.append(node)
            rank.append(0)
        while e < self.V - 1:
            u, v, w = self.graph[i]
            i = i + 1
            x = self.find(parent, u)
            y = self.find(parent, v)
            if x != y:
                e = e + 1
                result.append([u, v, w])
                self.apply_union(parent, rank, x, y)
        for u, v, weight in result:
            print("%d - %d: %d" % (u, v, weight))
 
g = Graph(6)
g.add_edge(0, 1, 4)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 2)
g.add_edge(1, 0, 4)
g.add_edge(2, 0, 4)
g.add_edge(2, 1, 2)
g.add_edge(2, 3, 3)
g.add_edge(2, 5, 2)
g.add_edge(2, 4, 4)
g.add_edge(3, 2, 3)
g.add_edge(3, 4, 3)
g.add_edge(4, 2, 4)
g.add_edge(4, 3, 3)
g.add_edge(5, 2, 2)
g.add_edge(5, 4, 3)
g.kruskal_algo()

from collections import defaultdict
 
# making a Class for representing a graph
class Graph:
	def __init__(self, vertices):
    	# dictionary that contains adjacency List
		self.graph = defaultdict(list)
        # number of vertices
		self.V = vertices
 
	# function for adding an edge to graph
	def addEdge(self, u, v):
		self.graph[u].append(v)
 
	# A recursive function used by topologicalSort
	def topologicalSortUtil(self, v, visited, stack):
 
		# Marking the current node as visited.
		visited[v] = True
 
 
		for i in self.graph[v]:
			if visited[i] == False:
				self.topologicalSortUtil(i, visited, stack)
 
		# Pushing current vertex to stack that stores result
		stack.append(v)
 
	# Topological Sort function.
	def topologicalSort(self):
 
		# Marking all the vertices as not visited
		visited = [False]*self.V
		stack = []
 
 
		# the sort starts from all vertices one by one
		for i in range(self.V):
			if visited[i] == False:
				self.topologicalSortUtil(i, visited, stack)
 
		# Printing contents of the stack
		print(stack[::-1])
g = Graph(6)
g.addEdge(5, 2)
g.addEdge(5, 0)
g.addEdge(4, 0)
g.addEdge(4, 1)
g.addEdge(2, 3)
g.addEdge(3, 1)
 
print ("The topological sort of the given graph is as")
 
 
g.topologicalSort()

from collections import defaultdict
MAX_INT = float('Inf')
# the function returns the vertex with minimum weight
def min_distance(dist, visited):
 
    (min, min_vertex) = (MAX_INT, 0)
    for v in range(len(dist)):
        if min > dist[v] and visited[v] == False:
            (min, min_vertex) = (dist[v], v)
 
    return min_vertex
 
 
# removing negative weights
def Dijkstra_algo(graph, modified_graph, src):
 
    # vertices in the graph
    vertices = len(graph)
 
    # Dictionary for checking if a given vertex is
    # in the shortest path tree
    sptSet = defaultdict(lambda : False)
 
    # computing distance of all vertices from the source
 
    for count in range(vertices):
 
        # The current vertex that is not yet included in the
        # shortest path tree
        currentV = min_distance(distance, sptSet)
        sptSet[currentV] = True
 
        for v in range(vertices):
            if ((sptSet[v] == False) and
                (distance[v] > (distance[currentV] +
                modified_graph[currentV][v])) and
                (graph[currentV][v] != 0)):
 
                distance[v] = (distance[currentV] +
                                modified_graph[currentV][v]);
 
    # Printing the Shortest distance from the source
    for v in range(vertices):
        print ('Vertex ' + str(v) + ': ' + str(distance[v]))
 
# computing shortest distances
def Bellman_algo(edges, graph, vertices):
 
    # Adding a source and calculating its min
    # distance from other nodes
    distance = [MAX_INT] * (vertices + 1)
    distance[vertices] = 0
 
    for a in range(vertices):
        edges.append([vertices, a, 0])
 
    for a in range(vertices):
        for (src, des, weight) in edges:
            if((distance[src] != MAX_INT) and
                    (distance[src] + weight < distance[des])):
                distance[des] = distance[src] + weight
 
 
    return distance[0:vertices]
 
# Function for implementing Johnson Algorithm
def Johnson_algo(graph):
 
    edges = []
 
    # Creating a list of edges for Bellman-Ford Algorithm
    for a in range(len(graph)):
        for b in range(len(graph[a])):
 
            if graph[a][b] != 0:
                edges.append([a, b, graph[a][b]])
 
    # Weights for modifying the original weights
    modify_weights = Bellman_algo(edges, graph, len(graph))
 
    modified_graph = [[0 for x in range(len(graph))] for y in
                    range(len(graph))]
 
    # Modifying the weights to get rid of negative weights
    for a in range(len(graph)):
 
        for b in range(len(graph[a])):
 
            if graph[a][b] != 0:
                modified_graph[a][b] = (graph[a][b] +
                        modify_weights[a] - modify_weights[b]);
 
    print ('The modified graph is as: ' + str(modified_graph))
 
    # Running Dijkstra for every vertex
    for src in range(len(graph)):
        print ('/nThe shortest distance with vertex ' +
                        str(src) + ' as the source is as:/n')
        Dijkstra_algo(graph, modified_graph, src)
 
 
graph = [[0, -5, 2, 3],
         [0, 0, 4, 0],
         [0, 0, 0, 1],
         [0, 0, 0, 0]]
 
Johnson_algo(graph)
 

# Using Kosaraju's algorithm to check if a given directed graph is
# strongly connected or not
 
from collections import defaultdict
 
class Graph:
 
	def __init__(self, vertices):
     	# vertices of a graph
		self.V = vertices
        # dictionary for storing a graph
		self.graph = defaultdict(list)
 
	# function for adding an edge to graph
	def addEdge(self, u, v):
		self.graph[u].append(v)
 
	# A function for performing DFS
	def DFSUtil(self, v, visited):
 
		# Marking the current node as visited
		visited[v] = True
 
 
		for i in self.graph[v]:
			if visited[i] == False:
				self.DFSUtil(i, visited)
 
	# Function returning the transpose of this graph
 
	def getTranspose(self):
 
		g = Graph(self.V)
 
 
		for i in self.graph:
 
			for j in self.graph[i]:
				g.addEdge(j, i)
 
		return g
 
	# main function returns true if the graph is strongly connected
	def isSC(self):
 
		# Marking all the vertices as not visited for 1st DFS
		visited =[False]*(self.V)
 
		# Performing DFS traversal starting from the first vertex.
		self.DFSUtil(0,visited)
 
		# Return false if DFS traversal doesn't visit all vertices
		if any(i == False for i in visited):
			return False
 
		# Creating a reversed graph
		gr = self.getTranspose()
 
		# Marking all the vertices as not visited for 2nd DFS
		visited =[False]*(self.V)
 
		# Doing DFS for the reversed graph starting from the first vertex.
		# Starting Vertex must be same starting point of first DFS
		gr.DFSUtil(0,visited)
 
		# returning false if all vertices are not visited in second DFS
		if any(i == False for i in visited):
			return False
 
return True
 
# Considering a random graph
g1 = Graph(5)
g1.addEdge(0, 1)
g1.addEdge(1, 2)
g1.addEdge(2, 3)
g1.addEdge(3, 0)
g1.addEdge(2, 4)
g1.addEdge(4, 2)
print ("Yes the graph is strongly connected." if g1.isSC() else "Not strongly connected")
 
g2 = Graph(4)
g2.addEdge(0, 1)
g2.addEdge(1, 2)
g2.addEdge(2, 3)
print ("Yes the graph is strongly connected." if g2.isSC() else "Not strongly connected")