A graph is a defined as: G = (V, E) V = set of vertices E = set of edges undirected: {v, w} unordered pairs directed: (v, w) ordered pairs
Applications of Graphs:
- web crawling (following links and crawling through things iteratively)
- social networks (find friends and friends of friends — what is two or three levels of seperation away from you)
- network broadcast — the packet has to traverse the network
- garbage collection in modern programming languages
Graph representation:
- Adjacency Lists:
- Array adj of V
- Linked lists
- for each vertex, uEV
- Adj[u] stores u’s neighbours