数据结构之图

2020/10/10 posted in 面试

可以用矩阵来表示图的两个点是否连通，用数组存储每个顶点:

图还可以用邻接表表示:

图的遍历主要有深度优先和广度优先两种方法：

类型	数据结构	特性
深度优先搜索	栈	不保留全部节点，有入栈出栈的操作，效率低，占用空间小
广度优先搜索	队列	保留全部节点，效率高，占用空间大

Evan的博客