Skip to main content

Digraphs (Directed Graphs)

image

  1. Path

  2. Shortest path

  3. Topological Sorting (can you draw a digraph so that all edges point upwards)

  4. Strong Connectivity

  5. Transitive closure (For which vertices v and w is there a path from v to w)

  6. PageRank

image

image

image

  1. Reachability - Find all vertices reachable from s along a directed path. (Use DFS)

image

image

image

  1. image

image

Edge-Weighted Graph API​

We use adjacency-list representation for representing a weighted graph, where each edge has a weight associated with it

Topological Sort