/
graph.theory.txt
92 lines (74 loc) · 6.79 KB
/
graph.theory.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
GRAPH
COMPARISON ==> #If the focus|importance is on:
# - nodes and adjacency: node list, adjacency list, adjacency matrix
# - edges and incidency: edge list, incidence list, incidence matrix
#Complexity:
# - time:
# - adjacency|incidency list > adjacency|incidency matrix > node|edge list
# - space:
# - node|edge list > adjacency|incidency list > adjacency|incidency matrix
# - adjacency matrix is better than incidency matrix if dense (size > order),
# worst otherwise
#Specific cases:
# - nodes or edges have values: no adjacency|incidence matrix
# - some isolated nodes: no edge list
# - graph structure is known: use node list
SENTINEL NODE ==> #Like sentinel value but for graphs
#I.e. node used to indicate end of walk
/=+===============================+=\
/ : : \
)==: DATA STRUCTURES :==(
\ :_______________________________: /
\=+===============================+=/
NODE LIST ==> #Representing a graph as a multiset of nodes, i.e. [EDGE..., NODE_VALUE]
#Variants:
# - if graph structure is known (e.g. line graph or balanced binary tree),
# can be multiset of NODE_VALUE instead
# - more space|time efficient
EDGE LIST ==> #Representing a graph as a multiset of edges, i.e. [NODE, NODE2, EDGE_VALUE]
ADJACENCY LIST ==> #Representing a graph as a associative array with:
# - KEY: current node
# - VAL: [ADJACENT_NODE..., NODE_VALUE]
#Variants:
# - if nodes have no values, can represent them as indices instead, i.e. use a list of
# lists (neighbors)
# - more space efficient
INCIDENCE LIST ==> #Similar to adjacency list, but using [ADJACENT_EDGE..., NODE_VALUE] as VAL
ADJACENCY MATRIX ==> #Representing a graph as a square matrix:
# - columns represent child node, rows parent node
# - i.e. for undirected graphs, matrix is symmetric
# - cells are incremented if nodes are adjacent
# - for simple graphs: it is either 0 (no edge) or 1 (an edge)
# - for non-simple graphs:
# - it can be anything
# - loops increment by 2
#"(a,b,c) adjacency matrix":
# - instead of incrementing cells, use b if there is no edge, a if there is an edge,
# c if there is a loop
# - i.e. normal adjacency matrix is a (1,0,2) adjacency matrix (for graphs with single edges)
# - "seidel [adjacency] matrix" is (-1,1,0) adjacency matrix
INCIDENCE MATRIX ==> #Representing a graph as a square matrix:
# - columns represent node, row edge
# - cells is 1 if node and edge are incident, 0 otherwise
# - for directed graph, -1 if parent, 1 if child (or 1 for parent, 2 for child)
#Comparison with adjacency matrix:
# - more space efficient if size < order, less otherwise.
/=+===============================+=\
/ : : \
)==: TREE :==(
\ :_______________________________: /
\=+===============================+=/
REPRESENTATIONS ==> #Often using a node list:
# - NODE_VALUE ("sequential representation"/"ahnentafel's list"):
# - when max outdegree is static
# - waste space if tree is not complete
# - often following BFS order
# - using a random access array
# - [NODE_VALUE, ...CHILDREN_POINTER|INDEX] ("linked representation")
# - using either linked lists of random access arrays
#Rarely used:
# - adjacency matrix: density is often low
# - adjacency|incidence list: often operations start at root, so associative array not needed
# - edge list, incidence list|matrix: often nodes are more important than edges