图的定义
图就是由顶点、边、权重的集合。
顶点
顶点一般表示对象属性特征
边
边表示对象事物的关系
权重
权重表示关系的比重
度
连接某一个顶点的边个数之和
若边一旦有方向，就把度分类成入度和出度
图的表示
邻接列表
每一个顶点会存储一个从它这里开始的边的列表
邻接列表只描述出度的边，即指向该顶点之外的边和顶点
如下图：
AdjacencyList.png
邻接矩阵
矩阵行和列都表示顶点，由两个顶点共同决定两个顶点是否相连、如果相连这个值表示的是相连边的权重。
如下图：
AdjacencyMatrix.png
小结
在 稀疏图的情况下，每一个顶点都只会和少数几个顶点相连，这种情况下相邻列表是最佳选择。如果这个图比较密集，每一个顶点都和大多数其他顶点相连，那么相邻矩阵更合适。
常用的图的遍历算法
- 广度优先算法
- 深度优先算法
- 最小生成树算法
- 最小路径算法
链接：
https://www.jianshu.com/p/70952b51f0c8
参考
https://github.com/raywenderlich/swift-algorithm-club/tree/master/Graph
网友评论