Directed Graphs

Definition and Terminology

Directed Graph (Digraph)

Structure: set of vertices V and directed edges E ⊆ V × V. Edge (u,v) indicates a link from u to v. Directionality: edges have orientation; (u,v) ≠ (v,u) unless explicitly present.

Vertices and Edges

Vertices: nodes representing entities. Edges: ordered pairs representing relationships or connections with direction.

Terminology

In-degree: number of incoming edges to vertex. Out-degree: number of outgoing edges from vertex. Path: sequence of edges following direction. Cycle: path starting and ending at same vertex without repeating edges.

Representations of Directed Graphs

Adjacency Matrix

Definition: |V|×|V| matrix A, A[i][j] = 1 if edge (i,j) exists, else 0. Storage: O(|V|²). Access: constant time edge query.

Adjacency List

Definition: array or list of lists; each vertex stores list of adjacent vertices it directs to. Storage: O(|V| + |E|). Efficient for sparse graphs.

Edge List

Definition: list of all edges as pairs (u,v). Simple, space O(|E|), inefficient for queries.

Key Properties and Metrics

Degree

In-degree: count of edges entering vertex. Out-degree: count of edges leaving vertex. Degree distribution: vertex degree frequency across graph.

Paths and Reachability

Path: sequence of edges following direction. Reachable: vertex v is reachable from u if path from u to v exists.

Cycles and Acyclicity

Cycle: path returning to start vertex. Directed Acyclic Graph (DAG): no cycles. DAG important for scheduling and ordering.

Graph Traversal Algorithms

Depth-First Search (DFS)

Mechanism: explore as far as possible along each branch. Use: detect cycles, topological sorting, connectivity.

Breadth-First Search (BFS)

Mechanism: explore neighbors level by level. Use: shortest path in unweighted graphs, reachability.

Traversal Complexity

Time: O(|V| + |E|) for adjacency list, O(|V|²) for adjacency matrix.

DFS(vertex v): mark v as visited for each neighbor u of v: if u not visited: DFS(u)

Topological Sorting

Definition

Linear ordering of vertices such that for every directed edge (u,v), u appears before v.

Existence

Only possible in Directed Acyclic Graphs (DAGs). Cyclic graphs have no topological order.

Algorithms

Kahn’s Algorithm: repeatedly remove nodes with zero in-degree. DFS-based: order vertices by finish times.

KahnTopologicalSort(Graph G): L = empty list S = set of nodes with in-degree 0 while S not empty: remove n from S append n to L for each neighbor m of n: remove edge (n,m) if in-degree(m) == 0: add m to S if edges remain: error "Graph has cycles" else: return L

Strongly Connected Components

Definition

Maximal subsets where every vertex reachable from every other vertex in subset.

Importance

Identify clusters, simplify graph by component condensation.

Algorithms

Kosaraju’s Algorithm, Tarjan’s Algorithm: both run in O(|V| + |E|).

Applications in Computer Science

Dependency Resolution

Package managers, build systems model dependencies as DAGs for correct order of operations.

State Machines

Model states and transitions with directed edges; used in compilers, protocol design.

Web Graphs and Social Networks

Web pages linked by hyperlinks, social media follow relationships modeled as directed graphs.

Important Algorithms on Directed Graphs

Shortest Path Algorithms

Dijkstra’s Algorithm: positive edge weights. Bellman-Ford: supports negative weights, detects negative cycles.

Cycle Detection

DFS based: track recursion stack to detect back edges indicating cycles.

Maximum Flow

Ford-Fulkerson, Edmonds-Karp algorithms solve flow problems in directed networks.

Computational Complexity

Traversal and Search

DFS, BFS: O(|V| + |E|) for adjacency list. O(|V|²) for adjacency matrix.

Topological Sort

Linear time O(|V| + |E|) via DFS or Kahn’s algorithm.

Strongly Connected Components

Linear time algorithms: O(|V| + |E|).

Data Structures for Implementation

Arrays and Lists

Adjacency lists use arrays of linked lists or dynamic arrays for neighbors. Efficient for sparse graphs.

Matrices

Adjacency matrices use 2D arrays. Suitable for dense graphs or fixed vertex sets.

Hash Maps and Sets

Used for dynamic graphs, quick edge existence checks, and flexible vertex indexing.

Examples and Use Cases

Directed Acyclic Graph (DAG)

Task scheduling: vertices represent tasks; edges represent precedence constraints.

Web Page Link Graph

Pages as vertices; hyperlinks as directed edges. Used in PageRank algorithm.

Finite State Machines (FSM)

States as vertices; transitions as directed edges. Model computation and control flow.

Challenges and Limitations

Handling Cycles

Cycles complicate ordering and traversal; require cycle detection and special handling.

Scalability

Large graphs need efficient storage and parallel algorithms for processing.

Dynamic Updates

Insertion/deletion of edges and vertices requires restructuring data structures efficiently.

References

• R. Diestel, Graph Theory, Springer, 5th Ed., 2017, pp. 1-450.
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, 3rd Ed., 2009, pp. 631-666.
• J. E. Hopcroft, R. E. Tarjan, "Efficient Algorithms for Graph Manipulation," Communications of the ACM, vol. 16, no. 6, 1973, pp. 372-378.
• U. Brandes, T. Erlebach (Eds.), Network Analysis: Methodological Foundations, Springer, 2005, pp. 1-450.
• D.B. West, Introduction to Graph Theory, 2nd Ed., Prentice Hall, 2001, pp. 125-178.