Graph Algorithms Cheat Sheet For Coding Interviews

# Using a BFS algorithmimport collectionsdef 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 algorithmdef 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 visitedgraph = {'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 edgesv_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 nextdef 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 vvertices = 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] = 1i = 0# Printing the distancefor 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 Algorithmclass 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}{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 verticesvertices = 4INF = 999# implementing the floyd-warshall algorithmdef 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 solutiondef 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 verticesvertices = 5# graph representationgraph = [[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 vertexselected_vertex = [0, 0, 0, 0, 0]# setting the number of edges to 0number_of_edges = 0# choosing 0th vertex and setting it to Trueselected_vertex[0] = True# printing the edge and the corresponding weightprint("Edge : Weight
")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 Kruskals 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 graphclass 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 defaultdictMAX_INT = float('Inf')# the function returns the vertex with minimum weightdef 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 weightsdef 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 distancesdef 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 Algorithmdef 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 ('
The shortest distance with vertex ' +                        str(src) + ' as the source is as:
')        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 notfrom collections import defaultdictclass 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 Falsereturn True# Considering a random graphg1 = 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")