Name for the elements in a Graph
Node or Vertex (nodes, vertices)
Let V={v1,v2,…}, the set of vertices
|V| = n (number of vertices)
Name for the connection btwn two elements in a Graph
Edges/Links
Let E={e1,e2,…} or {(v1,v2),(v4,v7),…}
|E| = m
- can be directed or undirected
- Can be weighted w/ a strength value
What’s an Adjacency Matrix
For a graph with n = |V| vertices,
An n×n matrix
Each cell is the relationship of the column vertex and row vertex ñ
* holds 1 (if there’s an edge) or 0 (if not)
What’s the performance of an Adjacency Matrix
For a graph with n vertices:
- Takes up O(n^2) space
Speed:
- O(1) to check if an edge exists
- O(1) to create an edge btwn two vertices
Takes a lot of space, but is very fast
What’s the performance of an Adjacency List
For a graph with n vertices:
- Takes up O(m) space (m = # of edges)
- Worst-case is O(m^2) but this rarely happens
(Note: n < m < n^2)
Speed:
- O(n) to check if an edge exists
- O(n) to create an edge btwn two vertices (b/c you need to check if one already exists)
Takes less space, but is slower
What’s an Adjacency List
An array of pointers (linked list inside each)
Each index is for a node
Linked list inside stores the neighbors (other nodes with edges)
When are two nodes Adjacent
When they’re connected by an edge
a – b
When are two edges adjacent
If they have a vertex in common
a – b – c
What is a Path
A sequence of adjscent edges from one vertex to another
What is the small world property?
In most networks, the shortest path between two nodes tend to be pretty short
(If there is a path btwn them, its usually short)
What’s a Component / connected component
“A maximal set of vertices such that there exists a path btwn every pair of vertices in the set”
Aka: the largest set of vertices where they all connect
How does Breadth First Search (BFS) work
- Set all vertices to dist(u) = infinity
- Set current vertex to dist(u) = 0
- Put current vertex into a queue
- While queue isn’t empty:
a) take curr node out of queue
b) for all neighbors (v) of curr node (u)
1) if v hasNot been processed yet (dist=infinity)
a) put v into the queue
b) make dist(v) = dist(u) + 1
Explicitely uses a queue
WILL FIND THE SHORTEST PATH
Breadth First Search (BFS) runtime
O(m + n)
m = # of vertices n = # of nodes
How does Depth First Search (DFS) work
For a node:
- Set visited(u) = true
- For each neighbor (v) of curr node (u)
a) if not visited, explore that node
Implicitely uses a Stack
