graph representation 2种标准方法

www.geeksforgeeks.org/graph-and-its-representations/


n: number of vertices



1. adjacency list


An array of linked lists 或者 set, size of array = narray[i] represents the linked list of vertices adjacent to the ith vertex.
如果是带weight，每个listNode存weight



Pros:
• Saves space O(|V|+|E|) . In the worst case, there can be C(V, 2) number of edges in a graph thus consuming O(V^2) space.
• Adding a vertex is easier.
Cons:
• Queries like whether there is an edge from vertex u to vertex v are not efficient and can be done O(V).


2. Adjacency Matrix

V*V 的的maxtrix int[][] adj
adj[i][j] = 1表示有一条边从vertex i 到 vertex j对于undirected图是对称的。adj[i][j] = w, 表示weighted graph


Pros：
• remove edge O(1) time
• Queries like v是否connect u O(1)time

Cons：
• Space O(n^2), 如果edge很少比较浪费。
• 再加一个点的复杂度是O(n^2)