Week 10 Notes: Adjacency Lists + Cow Contest

[varmichelle]

Adjacency matrix: (N*N with space for each node-node pair)
Pros: easy to use, linear access time
Cons: takes up a lot of memory

Adjacency list: (N with list of neighbors for each node)
If graph with no weights (or equal weights), just store a list of neighbors
If graph with weights, store a list of (neighbor, distance) pairs
Pros: less memory
Cons: more difficult to use, slower
Could use array of vectors, vector of vectors, array of maps, array of sets, array of linked lists
Array of maps is easiest bc you can directly access graph[a][b] (in a similar way)
Example:
Map<int,boolean> (no weights or equal weights) or <int,int> (weights) graph[N];
if (graph[a][b]==true) or if (graph[a][b] != INF) // then a and b are connected
// note: if map is empty, accessing the value should give the default value (false for boolean, 0 for int)

When to use which:
Use adjacency list for graphs with relatively few edges, can be many vertices (sparse graphs)
Use adjacency matrix for graphs with relatively few vertices, can be many edges (dense graphs)

Solution to cow contest:
Construct a directed graph with paths from winner to loser
Run Floyd-Warshall
for (int c = 0; c < N; c++)
boolean answer = true;
for (int d = 0; d < N; d++)
if (d == c) continue
if (graph[c][d] == INF && graph[d][c] == INF
answer = false
if (answer) count++
print count