图搜索算法
图搜索算法
图搜索算法是一类用于解决在图中寻找从起始节点到目标节点的路径问题的算法。常见的图搜索算法包括深度优先搜索（DFS）、广度优先搜索（BFS）、Dijkstra算法和A算法等。
- 深度优先搜索（DFS）
深度优先搜索是一种递归遍历算法，从起始节点开始，递归访问所有与其直接或间接相连的节点，直到到达目标节点或遍历完整个图。实现方式可以使用栈或递归实现。
深度优先搜索的时间复杂度为 $O(V+E)$，其中 $V$ 表示节点数，$E$ 表示边数。
以下是深度优先搜索的伪代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14function DFS(Graph, start, target):
visited = set()
stack = []
stack.push(start)
while stack is not empty:
node = stack.pop()
if node is target:
return True
visited.add(node)
for neighbor in Graph.get_neighbors(node):
if neighbor not in visited:
stack.push(neighbor)
return False
以下是深度优先搜索的 C++ 实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
using namespace std;
bool dfs(vector<vector<int>>& graph, int start, int target) {
unordered_set<int> visited;
stack<int> s;
s.push(start);
while (!s.empty()) {
int node = s.top();
s.pop();
if (node == target) {
return true;
}
visited.insert(node);
for (int neighbor : graph[node]) {
if (visited.find(neighbor) == visited.end()) {
s.push(neighbor);
}
}
}
return false;
}
- 广度优先搜索（BFS）
广度优先搜索是一种迭代遍历算法，从起始节点开始，按照距离递增的顺序遍历所有与其直接相连的节点，直到到达目标节点或遍历完整个图。实现方式可以使用队列实现。
广度优先搜索的时间复杂度为 $O(V+E)$，其中 $V$ 表示节点数，$E$ 表示边数。
以下是广度优先搜索的伪代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14function BFS(Graph, start, target):
visited = set()
queue = []
queue.enqueue(start)
while queue is not empty:
node = queue.dequeue()
if node is target:
return True
visited.add(node)
for neighbor in Graph.get_neighbors(node):
if neighbor not in visited:
queue.enqueue(neighbor)
return False
以下是广度优先搜索的 C++ 实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
bool bfs(vector<vector<int>>& graph, int start, int target) {
unordered_set<int> visited;
queue<int> q;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
if (node == target) {
return true;
}
visited.insert(node);
for (int neighbor : graph[node]) {
if (visited.find(neighbor) == visited.end()) {
q.push(neighbor);
}
}
}
return false;
}
- Dijkstra 算法
Dijkstra 算法是一种单源最短路径算法，用于求解起始节点到图中所有其他节点的最短路径。算法的基本思想是维护一个距离表，记录起始节点到其他节点的当前最短路径，然后不断选取距离表中距离最小的节点，更新与其相邻节点的距离表，直到所有节点都被更新。
Dijkstra 算法适用于没有负权边的有向图或无向图。时间复杂度为 $O((V+E)\log V)$，其中 $V$ 表示节点数，$E$ 表示边数。
以下是 Dijkstra 算法的伪代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18function Dijkstra(Graph, start):
dist = {}
prev = {}
Q = PriorityQueue()
for node in Graph:
dist[node] = inf
prev[node] = None
Q.enqueue(node, dist[node])
dist[start] = 0
while Q is not empty:
node = Q.dequeue()
for neighbor in Graph.get_neighbors(node):
alt = dist[node] + Graph.get_edge_weight(node, neighbor)
if alt < dist[neighbor]:
dist[neighbor] = alt
prev[neighbor] = node
Q.decrease_priority(neighbor, alt)
return dist, prev
以下是 Dijkstra 算法的 C++ 实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
typedef pair<int, int> pii;
vector<int> dijkstra(vector<vector<pii>>& graph, int start) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, start});
dist[start] = 0;
while (!pq.empty()) {
int d = pq.top().first;
int node = pq.top().second;
pq.pop();
if (dist[node] < d) {
continue;
}
for (auto& [neighbor, weight] : graph[node]) {
int alt = dist[node] + weight;
if (alt < dist[neighbor]) {
dist[neighbor] = alt;
pq.push({dist[neighbor], neighbor});
}
}
}
return dist;
}
相关参考文献：Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
这篇文章是Dijkstra算法的原始论文，作者E.W. Dijkstra在其中提出了该算法，并证明了其正确性和效率。
- A算法
A 算法是一种启发式搜索算法，用于求解起始节点到目标节点的最短路径。它是在 Dijkstra 算法的基础上加入了一个估价函数，用来评估从当前节点到目标节点的距离。A* 算法的基本思想是不断选取估价函数值最小的节点，更新与其相邻节点的距离表和估价函数值，直到到达目标节点。
A 算法适用于有向图或无向图。时间复杂度最坏为 $O(b^d)$，其中 $b$ 表示每个节点的平均分支因子，$d$ 表示起始节点到目标节点的最短路径长度。当估价函数是一致的时候，A 算法可以保证找到最短路径。
以下是 A 算法的伪代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24function A_star(Graph, start, goal):
open_set = {start}
closed_set = {}
g_score = {start: 0}
f_score = {start: heuristic(start, goal)}
came_from = {}
while open_set is not empty:
current = min(open_set, key=f_score.get)
if current == goal:
return reconstruct_path(came_from, current)
open_set.remove(current)
closed_set.add(current)
for neighbor in Graph.get_neighbors(current):
if neighbor in closed_set:
continue
tentative_g_score = g_score[current] + Graph.get_edge_weight(current, neighbor)
if neighbor not in open_set or tentative_g_score < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = tentative_g_score
f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
if neighbor not in open_set:
open_set.add(neighbor)
return None
其中，heuristic 函数是估价函数，用来评估从当前节点到目标节点的距离。在 A 算法中，估价函数需要满足以下条件：
估价函数的值必须始终大于等于从当前节点到目标节点的真实距离。
估价函数的值越小，当前节点到目标节点的距离越小。
常见的估价函数有曼哈顿距离、欧几里得距离等。
以下是 A* 算法的 C++ 实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
typedef pair<int, int> pii;
vector<int> astar(vector<vector<pii>>& graph, int start, int goal, function<int(int, int)> heuristic) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, start});
dist[start] = 0;
while (!pq.empty()) {
int d = pq.top().first;
int node = pq.top().second;
pq.pop();
if (node == goal) {
break;
}
for (auto& neighbor : graph[node]) {
int v = neighbor.first;
int w = neighbor.second;
int nd = dist[node] + w;
if (nd < dist[v]) {
dist[v] = nd;
pq.push({dist[v] + heuristic(v, goal), v});
}
}
}
if (dist[goal] == INT_MAX) {
return {};
}
vector<int> path;
int node = goal;
while (node != start) {
path.push_back(node);
node = prev[node];
}
path.push_back(start);
reverse(path.begin(), path.end());
return path;
}
int main() {
vector<vector<pii>> graph = {
{{1, 5}, {2, 3}}, // node 0
{{0, 5}, {2, 1}}, // node 1
{{0, 3}, {1, 1}, {3, 6}, {4, 9}}, // node 2
{{2, 6}, {4, 2}}, // node 3
{{2, 9}, {3, 2}} // node 4
};
int start = 0, goal = 4;
auto heuristic = [](int a, int b) { return abs(a - b); }; // manhattan distance
vector<int> path = astar(graph, start, goal, heuristic);
if (path.empty()) {
cout << "No path found!" << endl;
} else {
for (int node : path) {
cout << node << " ";
}
cout << endl;
}
return 0;
}
在上面的示例中，我们采用了曼哈顿距离作为估价函数。我们定义了一个 lambda 表达式来实现曼哈顿距离的计算。具体来说，我们假设起始节点和目标节点分别为 $(x_1, y_1)$ 和 $(x_2, y_2)$，则曼哈顿距离为 $|x_1 - x_2| + |y_1 - y_2|$。我们在 A* 算法中，将每个节点看作一个坐标 $(x, y)$，将估价函数定义为当前节点到目标节点的曼哈顿距离。
A 算法的时间复杂度最坏为 $O(b^d)$，其中 $b$ 表示每个节点的平均分支因子，$d$ 表示起始节点到目标节点的最短路径长度。在实践中，A 算法通常比 Dijkstra 算法快，因为它能够充分利用启发信息，减少搜索空间。
相关参考文献：Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.
这篇文章是A算法的原始论文，作者P.E. Hart、N.J. Nilsson和B. Raphael在其中提出了A算法，并证明了其正确性和相对于其他启发式搜索算法的优越性。
参考文献
以下是与前面所述图搜索算法相关的一些经典参考文献：
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
这本书是计算机科学领域的经典教材，详细介绍了各种图搜索算法，包括深度优先搜索、广度优先搜索、Dijkstra算法、Bellman-Ford算法、A*算法、Kruskal算法、Prim算法和Ford-Fulkerson算法。Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
这篇论文首次提出了Dijkstra算法，用于求解单源最短路径问题。Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90.
这篇论文首次提出了Bellman-Ford算法，用于求解带有负权重的单源最短路径问题。Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.
这篇论文首次提出了A*算法，用于解决启发式搜索中的最短路径问题。Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 48-50.
这篇论文首次提出了Kruskal算法，用于求解无向图中的最小生成树问题。Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6), 1389-1401.
这篇论文首次提出了Prim算法，也是用于求解无向图中的最小生成树问题。Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8, 399-404.
这篇论文首次提出了Ford-Fulkerson算法，用于解决最大流问题。“Artificial Intelligence: A Modern Approach” by Stuart Russell and Peter Norvig
这本经典的人工智能教材包含了大量关于图搜索算法的内容，其中包括深度优先搜索、广度优先搜索、迭代加深搜索、A*算法等。书中还讨论了如何使用启发式函数来优化搜索过程，以及如何处理环路、重复状态等问题。该书通俗易懂，适合初学者学习。“Graph Theory and Its Applications” by Jonathan L. Gross and Jay Yellen
该书是关于图论的一本经典教材，其中涵盖了图搜索算法的基本原理和实现方法，包括深度优先搜索、广度优先搜索、Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法等。该书对算法的实现细节进行了详细的介绍，适合对图搜索算法有一定了解的读者学习。“Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
该书是算法设计和分析的经典教材，其中也包括了大量的图搜索算法内容，包括深度优先搜索、广度优先搜索、Dijkstra算法、Bellman-Ford算法、A*算法等。该书对算法的时间和空间复杂度进行了详细的分析，对算法的优化也进行了探讨，适合对算法设计和分析有一定了解的读者学习。“Algorithms” by Robert Sedgewick and Kevin Wayne
该书是一本算法入门教材，其中包括了大量的图搜索算法内容，包括深度优先搜索、广度优先搜索、Dijkstra算法、Bellman-Ford算法、A*算法等。该书对算法的实现进行了详细的讲解，并提供了大量的代码示例和练习题，适合初学者学习。“Computer Science Distilled: Learn the Art of Solving Computational Problems” by Wladston Ferreira Filho and Raimondo Pictet
该书是一本介绍计算机科学的入门教材，其中包含了大量的图搜索算法内容，包括深度优先搜索、广度优先搜索、A*算法等。该书使用简单易懂的语言和示例，让读者轻松理解算法的核心思想和实现细节。“Introduction to Graph Theory” by Douglas B. West
该书是关于图论的入门教材，其中包含了大量的图搜索算法内容，包括深度优先搜索、广度优先搜索、Dijkstra算法等。该书不仅介绍了算法的基本原理和实现方法，还提供了大量的实例和练习题，帮助读者深入理解算法。“Algorithms in C++” by Robert Sedgewick
该书是一本使用C++语言实现算法的教材，其中包含了大量的图搜索算法内容，包括深度优先搜索、广度优先搜索、Dijkstra算法、Bellman-Ford算法、A*算法等。该书提供了详细的代码示例和练习题，帮助读者深入理解算法的实现和应用。