数据结构的实现
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.
网友评论