图(数据结构), since 2020.02.26

数据结构的实现 

1 Edge list structure边列表

用非排序list分别保存一个图的顶点(V)和边(E)。V保存(n个)顶点名。E保存(m个)边名，并且每个边对象包含两个指针，分别是该边的两个顶点。

复杂度分析:

添加顶点，O(1)；添加一条边，O(1)；删除一个顶点(考虑到要在E中删除所有相关边)，O(m)，删除一个边，O(1).

顶点用set表示更快。

2 Adjacent list structure邻近列表

用一个list保存图的顶点V，每个vertex对应一个collection I(v)，这个I(v)中保存顶点v的incident edge(无无向图)。传统上I(v)是个list，所以这种表达方式成为adjacent list.

复杂度分析: 6

2020.02.27 

3 Adjacent map structure(all-round optimal性能最佳)

用list/dict保存顶点V，每个顶点v对应了一个map/dict，其中的key是与v相连的其他顶点，value是两个顶点相连的边。(we let the opposite endpoint of each incident edge serve as a key in the map, with the edge structure serving as the value.)

{..., v : {u: e, w: g}, ...}

该表达在graph的4种表达方式里全方面性能最优。

4 adjacent matrix structure(适用于dense graph)

根据顶点个数n生成一个n*n的矩阵M，vertices are indiced from 0 to n-1，矩阵中的M(i, j)点保存的顶点i到顶点j的信息。如果用boolean表达，1则表示两点间有边，否则为0；对有向图，1和-1可用于表达incoming和outgoing。如果非boolean表达，矩阵中的值可保存边的权值。该矩阵是对称阵。对于sparse graph，这种表达过于redundant。该表达适用于dense graph.

图的四种表达的复杂度对比

reference:

1 M. Goodrich and etc, Data Structures and Algorithms in Python.