Python Implementation of Directed Graphs: Core Concepts and Algorithms

Directed Graph (Digraph): Asymmetric Relationship Modeling

A Directed Graph (Digraph) is a specialized graph where edges have a direction—connecting a “source vertex” to a “target vertex” (e.g., “A → B” denotes a one-way relationship from A to B, not vice versa). Unlike undirected graphs (where edges are bidirectional), digraphs model asymmetric relationships like social media follows, web hyperlinks, or task dependencies.

I. Core Concepts & Terminology (Digraph-Specific)

Building on general graph terminology, digraphs introduce direction-specific properties:

1. Key Definitions

Directed Edge (Arc): An edge from vertex u to v (written u → v), where u is the tail and v is the head.
Outdegree: Number of outgoing edges from a vertex (e.g., in a social network, the number of accounts a user follows).
Indegree: Number of incoming edges to a vertex (e.g., the number of followers a user has).
Directed Path: A sequence of vertices where each consecutive pair is connected by a directed edge (e.g., A → B → C—only valid in the direction of edges).
Directed Cycle: A directed path that starts and ends at the same vertex (e.g., A → B → C → A—all edges follow direction).
DAG (Directed Acyclic Graph): A digraph with no directed cycles (critical for task scheduling, topological sorting).
Strongly Connected: Every pair of vertices u and v has a directed path from u to v and vice versa.
Weakly Connected: The underlying undirected graph (ignoring edge directions) is connected.

2. Example Digraph

plaintext

Vertices: A, B, C, D, E
Edges: A→B, A→C, B→D, C→D, D→E, E→C

Outdegrees: A=2, B=1, C=1, D=1, E=1
Indegrees: A=0, B=1, C=2, D=2, E=1
Directed Cycles: D→E→C→D
Strongly Connected Component (SCC): {C, D, E} (all pairs have mutual directed paths)

II. Directed Graph Implementation (Python)

We’ll extend the general Graph class to enforce directed edges, add digraph-specific methods (indegree/outdegree, cycle detection, topological sort), and use an adjacency list (most efficient for sparse digraphs).

1. DirectedGraph Class

python

运行

from collections import deque

class DirectedGraph:
    def __init__(self):
        self.graph = {}  # Adjacency list: {vertex: [(target_vertex, weight), ...]}

    # -------------------------- Core Operations --------------------------
    def add_vertex(self, vertex):
        """Add a vertex (no duplicates)"""
        if vertex not in self.graph:
            self.graph[vertex] = []
            return True
        return False

    def add_edge(self, u, v, weight=1):
        """Add a directed edge u→v (weight optional)"""
        if u not in self.graph or v not in self.graph:
            raise ValueError("Both vertices must exist in the graph")
        # Add edge only in the direction u→v (no reverse edge)
        self.graph[u].append((v, weight))

    def get_outdegree(self, vertex):
        """Return outdegree of a vertex (number of outgoing edges)"""
        if vertex not in self.graph:
            raise ValueError("Vertex not in graph")
        return len(self.graph[vertex])

    def get_indegree(self, vertex):
        """Return indegree of a vertex (number of incoming edges)"""
        if vertex not in self.graph:
            raise ValueError("Vertex not in graph")
        indegree = 0
        for u in self.graph:
            for (v, _) in self.graph[u]:
                if v == vertex:
                    indegree += 1
        return indegree

    # -------------------------- Traversal Algorithms --------------------------
    def dfs_iterative(self, start_vertex):
        """Depth-First Search (DFS) → iterative (stack-based)"""
        if start_vertex not in self.graph:
            raise ValueError("Start vertex not in graph")
        visited = set()
        stack = [start_vertex]
        traversal = []
        while stack:
            vertex = stack.pop()
            if vertex not in visited:
                visited.add(vertex)
                traversal.append(vertex)
                # Push neighbors in reverse order to maintain consistent traversal order
                for (neighbor, _) in reversed(self.graph[vertex]):
                    if neighbor not in visited:
                        stack.append(neighbor)
        return traversal

    def bfs(self, start_vertex):
        """Breadth-First Search (BFS) → iterative (queue-based)"""
        if start_vertex not in self.graph:
            raise ValueError("Start vertex not in graph")
        visited = set()
        queue = deque([start_vertex])
        traversal = []
        while queue:
            vertex = queue.popleft()
            if vertex not in visited:
                visited.add(vertex)
                traversal.append(vertex)
                for (neighbor, _) in self.graph[vertex]:
                    if neighbor not in visited:
                        queue.append(neighbor)
        return traversal

    # -------------------------- Digraph-Specific Algorithms --------------------------
    def has_cycle(self):
        """Detect if the digraph contains a directed cycle (DFS-based)"""
        visited = set()
        recursion_stack = set()  # Tracks vertices in the current DFS path

        def _has_cycle(vertex):
            if vertex not in visited:
                visited.add(vertex)
                recursion_stack.add(vertex)
                # Check all outgoing edges
                for (neighbor, _) in self.graph[vertex]:
                    if neighbor not in visited and _has_cycle(neighbor):
                        return True
                    elif neighbor in recursion_stack:
                        # Found a back edge → cycle exists
                        return True
            # Remove vertex from recursion stack after DFS completes
            if vertex in recursion_stack:
                recursion_stack.remove(vertex)
            return False

        # Check all vertices (handles disconnected digraphs)
        for vertex in self.graph:
            if _has_cycle(vertex):
                return True
        return False

    def topological_sort(self):
        """Perform topological sort (only valid for DAGs) → returns sorted vertex list"""
        if self.has_cycle():
            raise ValueError("Cannot perform topological sort on a cyclic digraph")
        
        # Kahn's Algorithm (in-degree based)
        indegree = {vertex: self.get_indegree(vertex) for vertex in self.graph}
        queue = deque([v for v in indegree if indegree[v] == 0])  # Start with vertices of in-degree 0
        topo_order = []

        while queue:
            vertex = queue.popleft()
            topo_order.append(vertex)
            # Reduce in-degree of neighbors
            for (neighbor, _) in self.graph[vertex]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    queue.append(neighbor)

        # Verify all vertices are included (digraph is connected DAG)
        if len(topo_order) != len(self.graph):
            raise ValueError("Digraph has a cycle (topological sort incomplete)")
        return topo_order

    def shortest_path_dag(self, start_vertex):
        """Find shortest path from start_vertex to all others (only for DAGs) → uses topological sort"""
        if self.has_cycle():
            raise ValueError("Shortest path DAG algorithm requires an acyclic graph")
        if start_vertex not in self.graph:
            raise ValueError("Start vertex not in graph")
        
        # Step 1: Get topological order
        topo_order = self.topological_sort()
        # Step 2: Initialize distances (infinity except start_vertex)
        INF = float('inf')
        distance = {vertex: INF for vertex in self.graph}
        distance[start_vertex] = 0

        # Step 3: Relax edges in topological order
        for u in topo_order:
            if distance[u] != INF:
                for (v, weight) in self.graph[u]:
                    if distance[v] > distance[u] + weight:
                        distance[v] = distance[u] + weight

        return distance

    # -------------------------- Helper Methods --------------------------
    def get_vertices(self):
        return list(self.graph.keys())

    def get_edges(self):
        """Return all directed edges as (u, v, weight)"""
        edges = []
        for u in self.graph:
            for (v, weight) in self.graph[u]:
                edges.append((u, v, weight))
        return edges

    def __str__(self):
        """String representation (adjacency list with directions)"""
        result = []
        for u in self.graph:
            targets = ", ".join([f"{v} (w={w})" for (v, w) in self.graph[u]])
            result.append(f"{u} → [{targets}]")
        return "\n".join(result)

2. Test the DirectedGraph

python

运行

if __name__ == "__main__":
    # Test 1: Cyclic Digraph
    cyclic_dag = DirectedGraph()
    vertices = ["A", "B", "C", "D", "E"]
    for v in vertices:
        cyclic_dag.add_vertex(v)
    cyclic_dag.add_edge("A", "B", 2)
    cyclic_dag.add_edge("A", "C", 1)
    cyclic_dag.add_edge("B", "D", 3)
    cyclic_dag.add_edge("C", "D", 1)
    cyclic_dag.add_edge("D", "E", 2)
    cyclic_dag.add_edge("E", "C", 1)  # Creates cycle D→E→C→D

    print("=== Cyclic Directed Graph ===")
    print(cyclic_dag)
    print("Outdegree of A:", cyclic_dag.get_outdegree("A"))  # Output: 2
    print("Indegree of C:", cyclic_dag.get_indegree("C"))    # Output: 2 (from A and E)
    print("Has cycle?", cyclic_dag.has_cycle())              # Output: True

    # Test 2: DAG (Acyclic Digraph) for Topological Sort & Shortest Path
    dag = DirectedGraph()
    dag_vertices = ["Task1", "Task2", "Task3", "Task4", "Task5"]
    for v in dag_vertices:
        dag.add_vertex(v)
    dag.add_edge("Task1", "Task2", 1)
    dag.add_edge("Task1", "Task3", 2)
    dag.add_edge("Task2", "Task4", 3)
    dag.add_edge("Task3", "Task4", 1)
    dag.add_edge("Task4", "Task5", 2)

    print("\n=== DAG (Acyclic Directed Graph) ===")
    print(dag)
    print("Has cycle?", dag.has_cycle())  # Output: False
    print("Topological Sort:", dag.topological_sort())  # Output: ['Task1', 'Task2', 'Task3', 'Task4', 'Task5'] (or similar valid order)
    print("Shortest Paths from Task1:", dag.shortest_path_dag("Task1"))
    # Output: {'Task1': 0, 'Task2': 1, 'Task3': 2, 'Task4': 3 (1+3 or 2+1), 'Task5': 5 (3+2)}

    # Traversals
    print("\nDFS from Task1:", dag.dfs_iterative("Task1"))  # Output: ['Task1', 'Task2', 'Task4', 'Task5', 'Task3'] (order may vary)
    print("BFS from Task1:", dag.bfs("Task1"))              # Output: ['Task1', 'Task2', 'Task3', 'Task4', 'Task5']

III. Key Digraph Algorithms & Use Cases

Digraphs enable specialized algorithms to solve problems unique to directed relationships:

1. Cycle Detection

Purpose: Identify if a digraph contains a directed cycle (critical for task scheduling, avoiding infinite loops).
Algorithm: DFS-based (tracks recursion stack to detect back edges) or Kahn’s Algorithm (checks if topological sort is possible).
Use Cases:
- Validating task dependencies (e.g., “Task A must complete before Task B”—no cycles allowed).
- Detecting deadlocks in operating systems (processes waiting for resources in a cycle).

2. Topological Sort

Purpose: Order vertices such that all directed edges go from earlier to later in the order (only possible for DAGs).
Algorithm: Kahn’s Algorithm (in-degree based) or DFS-based (post-order traversal + reverse).
Use Cases:
- Task scheduling (e.g., building software with dependent modules, course prerequisites).
- Compilation order (compilers use topological sort to process dependencies).

3. Shortest Path in DAGs

Purpose: Find the shortest path from a source to all other vertices in a weighted DAG (more efficient than Dijkstra’s Algorithm).
Algorithm: Topological sort + edge relaxation (O(V + E) time).
Use Cases:
- Project scheduling (minimum time to complete all tasks with weighted durations).
- Network routing (finding minimum latency paths in acyclic networks).

4. Strongly Connected Components (SCCs)

Purpose: Identify subgraphs where every pair of vertices is mutually reachable (e.g., clusters in a directed network).
Algorithm: Kosaraju’s Algorithm (two passes of DFS) or Tarjan’s Algorithm (single DFS with stack tracking).
Use Cases:
- Social network analysis (identifying echo chambers or tightly connected user groups).
- Compression of digraphs (collapse SCCs into single nodes for simpler analysis).

IV. Time & Space Complexity

Operation/Algorithm	Time Complexity	Space Complexity
Add Vertex/Edge	O(1)	O(1)
Get Indegree/Outdegree	O(V + E) / O(1)	O(1)
DFS/BFS	O(V + E)	O(V)
Cycle Detection (DFS)	O(V + E)	O(V)
Topological Sort (Kahn’s)	O(V + E)	O(V)
Shortest Path in DAG	O(V + E)	O(V)
SCC (Kosaraju’s)	O(V + E)	O(V + E)

V. Practical Applications of Directed Graphs

Digraphs model asymmetric relationships—here are their most impactful use cases:

Social Media: Model user follows (A follows B → A→B), retweets, or mentions to recommend content or detect influencers.
Web Graphs: Model web pages (vertices) and hyperlinks (directed edges) for search engine ranking (e.g., Google’s PageRank algorithm).
Task Scheduling: Use DAGs to model task dependencies (e.g., “bake cake” requires “mix ingredients” first) for project management tools.
Network Routing: Model data flow directions (e.g., packets from router A to B) to optimize routing paths and detect bottlenecks.
Compilers: Use DAGs to represent intermediate code (expression trees) and optimize computations (e.g., eliminating redundant calculations).
Biology: Model biochemical pathways (e.g., enzyme A catalyzes reaction B → A→B) or gene regulatory networks.
Finance: Model transaction flows (e.g., money transfers from account A to B) to detect fraud or money laundering.

VI. Directed Graph vs. Undirected Graph (Key Differences)

Feature	Directed Graph (Digraph)	Undirected Graph
Edge Direction	Edges have direction (u→v ≠ v→u)	Edges are bidirectional (u-v = v-u)
Degree Metrics	Indegree (incoming) + Outdegree (outgoing)	Single degree (total edges connected)
Cycles	Directed cycles (u→v→u)	Undirected cycles (u-v-u)
Path Validity	Paths must follow edge directions	Paths ignore edge directions
Use Cases	Asymmetric relationships (follows, hyperlinks, dependencies)	Symmetric relationships (friendships, roads, connections)