Graphs

In this discuss we will look at patterns for solving graph problems. IMO the most challenging part of solving graph problems, is modeling the problem as a graph problem. Once the problem is modeled as a graph problem, the rest of the algorithm around the graph problems are quite standard and usually involves some of kind of traversal either BFS or DFS on the graph object. The complexity estimation of the graph problem also requires careful evaluation of the vertices and edges.

So what type of problems are modeled using graph problems. The problems which I have discussed in other posts are of sorting or selection are just define on n nodes and there has been no need to define the relationship between these nodes. Graph problems are modeled by also defining the relationship between the nodes.

For example a normal sorting problem would be like: sort the course based on the grades in the course, a similar sorting graph problem would be sorting the courses based on the requirements on other courses (no cycles) which is a dependency relationship which is defined by edges between the courses.

Similar problems can be modeled for searching, for example search a node, which is connect with another node. Or optimization problem of finding the shortest/minimum path between two nodes where the nodes are connected by some weights.

So for the graph problems, it is important to look out for if there is a relationship between nodes defined in the problem. If yes, then it is about defining the nodes and their relationship with other nodes to model the graph problem.

In this article I would be looking into the patterns for traversal of graphs, like DFS and BFS and what kind of problems can be solved using those algorithms. In further articles on graph, I will inspecting some of the advanced algorithms build using the traversal as the foundation.

So there are two types of graphs, un-directed i.e. for example all edges can be considered from a to b and also b to a. And directed, where the edge has specific direction i.e. for example a to b.

DFS Template for DFS is quite straight forward using the recursive format.

1. Mark the passed vertex as visited.
2. Iterate over all the neighbors of the vertex from the adj list or map.
3. If the neighbor vertices are not visited, run dfs on each of the vertices.

# DFS
def dfs(node: int):
  visited[node] = True
  for v in adjList[node]:
    if v not in visited:
      dfs(v)

Time Complexity: O(V + E), which will the sum of vertices and edges in the graph. Space Complexity: O(V), Max space of the recursive call stack is number of vertices in the graph in worst case.

BFS

Template for BFS on a component of the graph, and a visited map of nodes.

1. Create a queue, add the source node to the queue.
2. Iterate over the queue till it is empty.
3. Pop the left most vertex from the queue, and mark it as visited.
4. Iterate over all the connected vertices of the node by iterating over the list of the vertex.
5. If the neighbor vertex is not visited as the queue.

# BFS
def bfs(node: int):
  q = deque()
  # Always mark the node as visited before adding to the queue.
  visited[node] = True
  q.append(node)
  while len(q) > 0:
    v = q.popleft()
    for e in adjList[v]:
      if not visited[e]:
        # Mark it as visited before appending to the queue, so that it won't be added multiple times to the queue.
        visited[e] = True
        q.append(e)

Time Complexity: O(V + E), which will the sum of vertices and edges in the graph. Space Complexity: O(V), Max space of the queue is number of vertices in the graph.

Graph Traversal

Once the DFS and BFS templates are defined, basically the problem will.

1. Create a graph representation i.e. adjacency List or adjacency Map
2. Define BFS or DFS template for the graph traversal.
3. Run an outer loop over the nodes of the graph, so that on each node DFS and BFS runs if not already visited.

Problems

Based on the above template, we can into the traversal problems for these types of graph.

• No of connected components

from collections import defaultdict,deque
class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        # build the graph: adjList or adjMap
        adjList = defaultdict(list)
        for edge in edges:
            # Add two edges a -> b and b -> a as undirected graph
            adjList[edge[0]].append(edge[1])
            adjList[edge[1]].append(edge[0])

        # DFS
        def dfs(node: int):
            visited[node] = True
            for v in adjList[node]:
                if v not in visited:
                    dfs(v)
        # BFS
        def bfs(node: int):
            q = deque()
            q.append(node)
            visited[node] = True
            while len(q) > 0:
                v = q.popleft()
                for e in adjList[v]:
                    if not visited[e]:
                        visited[e] = True
                        q.append(e)
        # define visited map
        visited = defaultdict(bool)
        c = 0
        # Iterate over the vertices to run DFS or BFS
        for i in range(n):
            if i not in visited:
                # dfs(i) or bfs(i)
                bfs(i)
                c += 1
        return c

Similar is the problem Number of Provinces

The graph is defined as adjacency matrix rather, and need to find number of components.

def findCircleNum(self, edges: List[List[int]]) -> int:
    def dfs(node: int):
        visited[node] = True
        for i, e in enumerate(edges[node]):
            if i != node and e == 1 and i not in visited:
                dfs(i)

    visited = defaultdict(bool)
    c = 0
    for i in range(len(edges)):
        if i not in visited:
            dfs(i)
            c += 1
    return c

• Keys and Rooms

In this problem each room key is an edge to the next room which can be explored using one of traversal algorithm. The solution is about checking if there is one connected component.

def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
    def dfs(node: int):
        if node in visited:
            return
        visited[node] = True
        for v in rooms[node]:
            dfs(v)

    def bfs(node: int):
        q = deque()
        q.append(node)
        visited[node] = True
        while q:
            v = q.popleft()
            for e in rooms[v]:
                if e not in visited:
                    visited[e] = True
                    q.append(e)

    visited = defaultdict(bool)
    # bfs(0)
    dfs(0)
    # If the graph is connected, i.e. all nodes get visited when traversal starts at 0, then graph can be fully explored.
    return len(visited) == len(rooms)

Detecting Cycles in Directed Graphs

DFS

1. A cycle is detected in DFS traversal by detecting a back edge between nodes in the graph.
2. A back edge is defined as an edge from node to an already visited vertex in the graph which is not an immediate parent to the node.
3. A back edge is an edge which goes up the recursive tree to an ancestor node which is not the parent of the current vertex.

So basically there will be cycles in the undirected graph if the neighbor is already visited and is not the immediate parent of the node.

The above DFS template can be modified a little to define the change.

# DFS return True if cycle else return False
def dfs(node: int) -> bool:
  visited[node] = True
  for v in adjList[node]:
    if v not in visited:
      parent[v] = node
      if dfs(v): # If there is cycle in the rest graph traversal, return True
        return True
    else:
      if parent[node] != v:
        return True
  return False

BFS

1. A cycle is detected in BFS traversal by detecting a cross edge between nodes in the graph.
2. A cross edge is defined as an edge from node to already visited vertex in the graph which is not immediate parent of the node.
3. A cross edge will be an edge connecting two vertices in the same level or immediate level in the BFS level order tree structure.

So basically, every time we see a visited neighbor of a node that can be a cross edge if it is not immediate parent of the node. This is because in the case of undirected graph we will be adding a->b and b->a as the edges, so when exploring b vertex after being added as neighbor of a in the code it will see vertex a as already visited but that doesn’t make a cycle in the graph as it is the parent of b. To keep track of the immediate parents, we can update another map parent like visited and check there. Whereas a graph like a<->b, a<->c, b<->c does make a cycle.

The above BFS template can be modified a little to define the change.

# BFS detect cycles return True if cycle else return false
def bfs(node: int) -> bool:
  q = deque()
  q.append(node)
  visited[node] = True
  while len(q) > 0:
    v = q.popleft()
    for e in adjList[v]:
      if not visited[e]:
        # register parent of vertex e which are connected with v
        parent[e] = v
        visited[e] = True
        q.append(e)
      else: # If e already visited it can be the parent of v, so check if parent[v] != e for detecting cross edge
        if parent[e] != v: # True, means there is a cross b/w v and e
          return True
  return False

• Graph Valid Tree

A tree can be defined as a connected graph with no cycles. So basically in this problem, we are trying to find if there are no cycles in the graph as well as a single component similar to the Keys and Rooms problem.

The modified dfs/bfs template can be used in the problem.

def validTree(self, n: int, edges: List[List[int]]) -> bool:
    adjList = defaultdict(list)
    # Create adjacency List
    for e in edges:
        # undirected graphs add both the edges
        adjList[e[0]].append(e[1])
        adjList[e[1]].append(e[0])

    def dfs(node: int) -> bool:
        visited[node] = True
        for v in adjList[node]:
            if v not in visited:
                parent[v] = node
                if dfs(v):
                    return True
            else:
                if parent[node] != v:
                    return True
        return False

    def bfs(node: int) -> bool:
        q = deque()
        q.append(node)
        visited[node] = True
        while len(q) > 0:
            v = q.popleft()
            for e in adjList[v]:
                if not visited[e]:
                    # register parent of vertex e which are connected with v
                    parent[e] = v
                    visited[e] = True
                    q.append(e)
                else: # If e already visited it can be the parent of v, so check if parent[v] != e for detecting cross edge
                    if parent[v] != e: # True, means there is a cross b/w v and e
                        return True
        return False

    parent = defaultdict(int)
    visited = defaultdict(bool)
    parent[0] = -1
    hasCycle = dfs(0)
    if hasCycle:
        return False
    if len(visited) != n:
        return False
    return True

Another similar problem related to cross edge and back edge is about determining graph is bipartite: Is Graph Bipartite?

1. A Tree is always bipartite, as each level can be part of alternative group and there is no edge in same group.
2. A graph with odd cycle is not bipartite, because each consecutive labelling of the nodes always result in last two adjacent nodes in the cycle in same group. Such a triangle graph like: 1(R) -> 2(B) -> 3(R) -> 1(R) is not bipartite.
3. A graph with even cycle is still bipartite, because each consecutive labelling of the nodes always result in last two adjacent nodes in the cycle in different group. Such a a rectangle like: 1(R) -> 2(B) -> 3(R) -> 4(B) -> 1(R)
4. When doing a BFS having a cross edges in the same level or adjacent level creates a cycle in the graph. But the cross edge in the same level will cause the graph to be non-bipartite as the cycle will be odd in length, whereas the adjacent level cross edge will lead to even cycle which doesn’t cause the graph to be non bipartite.
5. Similarly in the DFS back edges creates cycle in the graph. A back edge which goes to an ancestor which is part of the same group will result in the graph not being bipartite, whereas the edge to the graph which is no part of the same group should be fine and not change bipartite property of the graph.

Keeping all this in mind, we can detect if the graph is bipartite by labelling the nodes in two groups and checking if the cross edge in BFS or back edge in DFS goes to the same group neighbor, when the neighbor is already visited.

def isBipartite(self, graph: List[List[int]]) -> bool:
    def dfs(node: int) -> bool:
        visited[node] = True
        for v in graph[node]:
            if v not in visited:
                # make the group opposite of the parent
                group[v] = not group[node]
                if not dfs(v):
                    return False
            else:
                # neighbor already visited, check group is not same, then not bipartite
                if group[v] == group[node]:
                    return False
        return True

    def bfs(node: int) -> bool:
        # If a bipirate graph component will have nodes without cycles or with back edges/cross edges which create cycles but only going to separate groups or adjacent level.
        q = deque()
        q.append(node)
        visited[node] = True
        while q:
            v = q.popleft()
            for u in graph[v]:
                if u not in visited:
                    visited[u] = True
                    # make the group opposite of the parent
                    group[u] = not group[v]
                    q.append(u)
                else:
                    # neighbor already visited, check group is same, then not bipartite
                    if group[v] == group[u]:
                        return False
        return True

    visited = defaultdict(bool)
    group = defaultdict(bool)
    for node in range(len(graph)):
        if node not in visited:
            if not bfs(node): # or dfs(node)
                return False
    return True

Other problems which about graph bipartite?

• Possible Bipartition
• Possible to divide graph into two colors where no adjacent node is of the same color.