edges often have directions and weights
digraphs = directed graphs
normal graphs, except that edges have a sense of direction
i.e., v → w ≠ w → v
in a directed graph,
each vertex has an outdegree and indegree
outdegree = $\deg(\text v)$ = number of edges from v to __
indegree = $\deg^{-1}(\text v)$ = number of edges from __ to v
paths / cycles are not directed paths or directed cycles
reachability is defined in terms of the existence of a directed path from v to w
strong connectivity = each vertex is reachable from every other vertex
directed acyclic graph = a digraph with no directed cycles
virtually the same as undirected graphs, except edge pairs have a sense of direction
| array of edges | adjacency matrix | adjacency list | |
|---|---|---|---|
| space complexity | E | V^2 | V + E |
| initialise graph | 1 | V^2 | V |
| insert edge | E | 1 | deg(v) |
| remove edge | E | 1 | deg(v) |
| is path(x, y) | E * log(V) | V^2 | V + E |
| copy graph | E | V^2 | V + E |
| destroy graph | 1 | V | V + E |
| is edge | E | 1 | deg(v) |
traversing a digraph is identical to traversing a normal graph
similar to normal graphs, except the edges have a sense of cost or weight
each edge is now (src, dest, weight) instead of (src, dest)
two main problems to solve with weighted graphs: