edges often have directions and weights

digraphs (directed graphs)

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

digraph implementations

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

weighted graphs

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:

  1. cheapest way to connect all vertices (minimal spanning tree problem) - for undirected weighted graphs
  2. cheapest way to get form A to B (shortest path problem) - for directed weighted graphs