Graph(图)

文档摘要

Graph(图) 在面试的过程中,一般不会考到图相关的问题,因为图相关的问题难,而且描述起来很麻烦. 但是也会问道一下常见的问题,比如,最短路径,最小支撑树,拓扑排序都被问到过. 图常用的表示方法有两种: 分别是邻接矩阵和邻接表. 邻接矩阵是不错的一种图存储结构,对于边数相对顶点较少的图,这种结构存在对存储空间的极大浪费. 因此,找到一种数组与链表相结合的存储方法称为邻接表. 邻接矩阵表示的无向图邻接表表示的无向图最短路径 Dijkstra 维护一个最短路径的的集合(sptSet)和最短距离数组, 直到遍历所有的点, 初始化起始点的距离是0, 集合为空. 初始化起始点s到所有的点的距离是INF, 注意s到s的距离是0.