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: