Skip to main content Link Search Menu Expand Document (external link)
Algo Notes

Graphs

Table of contents

  1. Detecting Cycles in a Directed Graph
  2. Detecting Cycles in an Undirected Graph
  3. References

Graph: G = (V, E), where for graph G, V is a set of vertices, and E is a set of edges. Every edge E is a tuple (v, w) where v, w $\in$ V

Subgraph: A subgraph s is a set of edges e and vertices v such that $e \in E$ and $v \in V$

Representation: Adjacency Matrix and Adjacency List

Detecting Cycles in a Directed Graph

Use DFS and maintain a stack of nodes, if a visited node is present in the stack, cycle detected. [Leetcode #207]

Time Complexity: O(V+E) Space Complexity:O(V)

def DFS(visited, i, stack)
    visited[i], stack[i] = True, True
    for j in adj[i]:
        if not visited[i]:
            if DFS(visited, j, stack): return True
        elif stack[j]: return True
    stack[j]=False
    return False
def detectCycle(V, adj):
    visited, stack = [False]*V, [False]*V
    for i in range(V):
        if not visited[i]:
            if DFS(visited, i, stack): return True
    return False

Detecting Cycles in an Undirected Graph

Use DFS and a cycle is present if an adjacent vertex is already visited and is not the parent of the current vertex

Time Complexity: O(V+E) Space Complexity:O(V)

def DFS(visited, i, parent)
    visited[i] = True
    for j in adj[i]:
        if not visited[i]:
            if DFS(visited, j, i): return True
        elif parent!=j: return True
    return False
def detectCycle(V, adj):
    visited = [False]*V
    for i in range(V):
        if not visited[i]:
            if DFS(visited, i, -1): return True
    return False

References