📗 -> 11/21: Graphs
🎤 Vocab
❗ Unit and Larger Context
Small summary
✒️ -> Scratch Notes
Basic Terminology
G = (V,E)
- V = Set nodes/vertices
- E = Set edges
|V| = n, E=O(n^2)
Dense Graph:
Sparse Graph:
| Nodes/Vert | Edges |
|---|---|
| Cities | Roads |
| Social Netw | Friends |
| Person | Interaction of 15 mins |
Variants:
- Undirected
- Directed
- Weighted
- X - Multigraph?
Adj List / Adj Matrix
int AdjList(n):
AdjList(i) = All vertices adjaent to i
- i -> a, all verticies you can walk to from i, w/ one edge
int AdjMatrix(n)(n):
A(i)(j) = 1, A connection from i -> j
| Adj List | Adj Matrix | |
|---|---|---|
| Lookup | O(n) | O(1) |
| Space | O(V+E) | O(n^2) |
| Use Case | Sparse graphs - Facebook, most people not connected to whole world | Else |
BFS
Queue G = empty
q.push(s)
while (G is not Empty) {
u = G.pop
...
}
DFS
Uses:
- Identify if graph has a cycle (generally bad)
- DFS can tell you which ‘task’ to start first?
- Topological sort?
- Helps with building trees in graphs
Input: G(V,E) no source node
Output: Two time stamps for every
(1)
d[v] = time node is first discovered
f[v] = time node is finished
(2)
classification of edges into 4 types
- tree edge. If only focused on tree edges, create a tree graph
- back edge. Only eists if there is a cycle
- forward edge. Edge from ancestor to descendants
(3 and 4 are very similar)
- cross edge. An edge two trees or subtrees
(3)
// w=white, g=grey, b=black, represen
DFS_visit(u)
color[u] = g
time++
[u] = time
for (v in Adj[u]) {
if (color[v] == w) {
DFS_visit(v)
}
}
color[u] = b
time++
...
return
🔗 -> Links
Resources
- Put useful links here
Connections
- Link all related words