type
status
date
slug
summary
tags
category
icon
password
什么是图论和图？
图论 (Graph theory) 是数学的一个分支，图是图论的主要研究对象。图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。
图论相关算法
DFS 全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。
DFS 最显著的特征在于其 递归调用自身。同时与 BFS 类似，DFS 会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保 每个点仅访问一次。符合以上两条规则的函数，便是广义上的 DFS。
代码框架如下：
- 栈实现(可以与DFS对应)
- 递归实现
BFS 全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索。
所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。
这样做的结果是，BFS 算法找到的路径是从起点开始的 最短 合法路径。换言之，这条路径所包含的边数最小。
在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。
具体实现：
注意：实际上，堆优化 Dijkstra 就是优先队列 BFS。
Dijkstra算法(用于在加权图中找出从一个指定起点节点到其他所有节点的最短路径)
- 朴素版
- 堆优化版
Floyd-Warshall 算法(解决所有节点对最短路径问题)
经典代码如下：
- 作者:Luck
- 链接:https://enblog.top/article/1c0ad491-793a-80b4-b182-f0c5073f14cd
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。