Graph

图的表示方法有哪些？（Representing graphs）

three criteria

• how much memory, or space
• how long it takes to determine whether a given edge is in the graph
• how long it takes to find the neighbors of a given vertex

1）Edge lists

To represent an edge, we just have an array of two vertex numbers, or an array of objects containing the vertex numbers of the vertices that the edges are incident on.

[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5], [3,8], [4,5], [4,9], [7,8], [7,9] ]

Edge lists are simple, but if we want to find whether the graph contains a particular edge, we have to search through the edge list.

2）Adjacency matrices

With an adjacency matrix, we can find out whether an edge is present in constant time, by just looking up the corresponding entry in the matrix.

Two disadvantage: First, it takes lots of space to represent only a few edges. Second, if you want to find out which vertices are adjacent to a given vertex , you have to look at all |V|∣V∣ entries in row ii.

3) Adjacency lists

邻接表结合了邻接矩阵和edge list. 对每个顶点，储存所有的相邻的顶点。