Data Structure and Algorithm 5 | Graph Algorithms

1. Graph Representation

(1) Adjacency Matrix

The adjacency matrix with shape $n \times n$ is a symmetric matrix that has {0, 1} as its values, where 1 means two nodes are connected.

(2) Adjacency List

Adjacency list is a list of length $n$ stores the list of edge information.

(3) Connected Nodes

A node in the graph is defined by,

x
1
class Node:
2
    def __init__(self, value):
3
        self.value = value
4
        self.edges = [] 
5
    def add(self, target):
6
        self.edges.append(target)
7
    def __repr__(self): 
8
        return str(self.value)

This is the common implementation due to nice mapping to objects.

(4) Node with Labelled Edges

8
1
class LNode:
2
    def __init__(self, value):
3
        self.value = value
4
        self.edges = {}
5
    def add(self, label, target):
6
        self.edges[label] = target
7
    def __repr__(self): 
8
        return str(self.value)

2. Graph Algorithms

(1) Recall: DFS Search

Time complexity $O(n)$.

xxxxxxxxxx
10
1
def dfsSearch(root, x, visited):
2
  
3
    if not root: return None
4
    if root in visited: return None
5
    
6
    visited.add(root)
7
    
8
    if root.val == x: 
9
        return root
10
      
11
    for p in root.edges:
12
        return dfsSearch(p, visited)

(2) Reachable Nodes

Start from a node, then get a set of nodes it can reach by,

xxxxxxxxxx
10
1
def reachable(root, reaches, visited):
2
  
3
    if root in visited: return None
4
    
5
    visited.add(root)
6
    
7
    for q in root.edges:
8
        reaches.add(q)
9
        reachable(q, reaches, visited)
10
        
11
    return reaches

(3) Detecting Cycles

x
1
def iscyclic(p):
2
    return iscyclic_(p, p, set())
3
​
4
def iscyclic_(start, p, visited):
5
  
6
    if p in visited: 
7
        if p is start: return True
8
        else: return False
9
      
10
    visited.add(p)
11
    
12
    for q in p.edges:
13
        if iscyclic_(start, q, visited): return True 
14
    return False

(4) Find First Path

xxxxxxxxxx
1
def path(p, q):
2
    return path_(p, q, [p], set())
3
​
4
def path_(p, q, path, visited):
5
  
6
    if p is q: return path
7
    if p in visited: return None
8
    
9
    visited.add(p)
10
    
11
    for t in p.edges:
12
        pa = path_(t, q, path+[t], visited)
13
        if pa is not None: return pa
14
        
15
    return None

(5) Find all Path

x
1
def allpaths(p, q):
2
    allpaths = []
3
    allpaths_(p, q, [p], allpaths, set())
4
    return allpaths
5
​
6
def allpaths_(p, q, path, allpaths, visited):
7
  
8
    if p is q:
9
        allpaths.append(path)
10
        return
11
    if p in visited: return None
12
    
13
    visited.add(p)
14
    
15
    for e in p.edges:
16
        allpaths_(e, q, path+[e], allpaths, visited)
17
        
18
    return None

(7) BFS Search

x
1
def bfsSearch(root, x): 
2
​
3
    visited = {root}
4
    worklist = [root] 
5
    
6
    while len(worklist) > 0: 
7
      
8
        p = worklist.pop(0)
9
        
10
        if p.val == x:
11
            return True
12
        
13
        for q in p.edges:
14
            if q not in visited:
15
                worklist.append(q)
16
                visited.add(q)
17
                
18
     return False

(8) Shortest Path

x
1
def shortestPath(root, target): 
2
  
3
    visited = {root}
4
    worklist = [[root]]
5
    
6
    while len(worklist) > 0: 
7
      
8
        path = worklist.pop(0)
9
        p = path[-1]
10
        
11
        if p.value == target.value:
12
            return path
13
          
14
        for q in p.edges:
15
            if q not in visited:
16
                worklist.append(path+[q])
17
                visited.add(q)
18
                
19
    return None

(9) Depth/Distance

xxxxxxxxxx
1
def depths(p):
2
    reaches = dict()
3
    depths_(p, reaches, depth=0)
4
    return reaches
5
​
6
def depths_(p, reaches, depth):
7
  
8
    if p in reaches: return None
9
    
10
    reaches[p] = depth
11
    
12
    for q in p.edges:
13
        depths_(q, reaches, depth+1)

(10) Find Neighbour within k Distance

xxxxxxxxxx
13
1
def neighbors(p, k):
2
    reaches = dict()
3
    neighbors_(p, k, reaches, depth=0)
4
    return reaches
5
​
6
def neighbors_(p, k, reaches, depth):
7
  
8
    if p in reaches or depth > k: return None
9
    
10
    reaches[p] = depth
11
    
12
    for q in p.edges:
13
        neighbors_(q, k, reaches, depth+1)

(11) DFS Based Topological Sort

Here visited set is added not because we are caring about the cycles. It means that we don't take the nodes we have visited into the account because these nodes have already beem sorted.

xxxxxxxxxx
10
1
def topoSort(nodes):
2
  
3
    sorted = []
4
    visited = set()
5
    
6
    while len(visited) < len(nodes):
7
        todo = [node for node in nodes.values() if node not in visited]
8
        if len(todo) > 0:
9
            postorder(todo[0], sorted, visited)
10
            
11
    return sorted

Here it requires a post order DFS as we have written in the searching part.

xxxxxxxxxx
9
1
def postorder(p, sorted, visited):
2
  
3
    if p in visited: return
4
    
5
    visited.add(p)
6
    
7
    for q in p.edges:
8
        postorder(q, sorted, visited)
9
    sorted.append(p)