图搜索算法是用于在图结构中寻找特定节点或路径的算法。图是由节点（或顶点）和边组成的集合，节点代表对象，边代表节点之间的连接。图搜索算法广泛应用于各种领域，比如网络路由、社交媒体分析、推荐系统等。 V哥最近总是在多个地方都看到关于图搜索算法的讨论，下面是一些常见的图搜索算法：
1. 深度优先搜索（DFS） 深度优先搜索是一种用于遍历或搜索树或图的算法。该算法会尽可能深地搜索图的分支。当节点v的所有边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这个过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
2. 广度优先搜索（BFS） 广度优先搜索是一种先遍历最近的节点，逐渐向外扩展的搜索算法。它从源节点开始，首先访问所有距离源节点为1的节点，然后访问所有距离源节点为2的节点，以此类推，直到访问到目标节点。广度优先搜索可以确保在找到最短路径时停止。
3. A搜索算法 A搜索算法是一种启发式搜索算法，它使用启发式函数来评估从源节点到目标节点的路径的成本。启发式函数是一种估计函数，它提供了从当前节点到目标节点的估计成本。A搜索算法在优先队列中根据f(n) = g(n) + h(n)的值来选择下一个要访问的节点，其中g(n)是从源节点到当前节点的实际成本，h(n)是当前节点到目标节点的估计成本。A搜索算法可以找到最短路径，但它的性能取决于启发式函数的选择。
4. Dijkstra算法 Dijkstra算法是一种用于在加权图中找到最短路径的算法。它从源节点开始，首先访问所有直接相邻的节点，然后访问所有距离源节点为2的节点，以此类推，直到访问到目标节点。与广度优先搜索不同，Dijkstra算法考虑了边的权重，因此它适用于加权图。
这些图搜索算法在计算机科学中非常重要，它们为解决各种问题提供了强大的工具。在实际应用中，选择合适的算法取决于具体问题的需求和图的结构特性。
以下是四种图搜索算法的详细介绍和Java代码实现案例。
1、深度优先搜索（DFS）
深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。DFS沿着一个分支遍历，直到这个分支的末端，然后进行回溯。
Java代码实现：
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Graph {
private int V; // 顶点的数量
private List<List<Integer>> adj; // 邻接表
public Graph(int v) {
V = v;
adj = new ArrayList<>(v);
for (int i = 0; i < v; ++i) {
adj.add(new ArrayList<>());
}
}
public void addEdge(int v, int w) {
adj.get(v).add(w); // 添加边
}
public void DFS(int v) {
boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<>();
stack.push(v);
visited[v] = true;
while (!stack.isEmpty()) {
int vertex = stack.pop();
System.out.print(vertex + " ");
List<Integer> neighbors = adj.get(vertex);
for (int neighbor : neighbors) {
if (!visited[neighbor]) {
stack.push(neighbor);
visited[neighbor] = true;
}
}
}
}
}
2、广度优先搜索（BFS）
广度优先搜索（BFS）是一种先遍历最近的节点，逐渐向外扩展的搜索算法。BFS从源节点开始，首先访问所有距离源节点为1的节点，然后访问所有距离源节点为2的节点，以此类推，直到访问到目标节点。
Java代码实现：
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Graph {
private int V; // 顶点的数量
private List<List<Integer>> adj; // 邻接表
public Graph(int v) {
V = v;
adj = new ArrayList<>(v);
for (int i = 0; i < v; ++i) {
adj.add(new ArrayList<>());
}
}
public void addEdge(int v, int w) {
adj.get(v).add(w); // 添加边
}
public void BFS(int v) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[v] = true;
queue.add(v);
while (!queue.isEmpty()) {
int vertex = queue.poll();
System.out.print(vertex + " ");
List<Integer> neighbors = adj.get(vertex);
for (int neighbor : neighbors) {
if (!visited[neighbor]) {
queue.add(neighbor);
visited[neighbor] = true;
}
}
}
}
}
3、A*搜索算法
A*搜索算法是一种启发式搜索算法，它使用启发式函数来评估从源节点到目标节点的路径的成本。A搜索算法在优先队列中根据f(n) = g(n) + h(n)的值来选择下一个要访问的节点，其中g(n)是从源节点到当前节点的实际成本，h(n)是当前节点到目标节点的估计成本。
Java代码实现：
import java.util.*;
public class AStarSearch {
class Node {
int id;
int g; // 从起始点到当前点的成本
int h; // 当前点到终点的估计成本
int f; // g + h
Node parent;
public Node(int id, int g, int h, Node parent) {
this.id = id;
this.g = g;
this.h = h;
this.f = g + h;
this.parent = parent;
}
}
public List<Integer> aStarSearch(int start, int goal, int[][] graph) {
PriorityQueue<Node> openList = new PriorityQueue<>(Comparator.comparingInt(node -> node.f));
HashSet<Integer> closedList = new HashSet<>();
Node startNode = new Node(start, 0, heuristic(start, goal), null);
openList.add(startNode);
while (!openList.isEmpty()) {
Node currentNode = openList.poll();
if (currentNode.id == goal) {
return getPath(currentNode);
}
closedList.add(currentNode.id);
for (int i = 0; i < graph[currentNode.id].length; i++) {
if (graph[currentNode.id][i] != 0) {
int neighborId = i;
if (closedList.contains(neighborId)) {
continue;
}
int tentativeG = currentNode.g + graph[currentNode.id][i];
if (!openList.contains(new Node(neighborId, 0,
if (!openList.contains(new Node(neighborId, 0, 0, null)) || tentativeG < openList.contains(new Node(neighborId, 0, 0, null)).g) {
openList.add(new Node(neighborId, tentativeG, heuristic(neighborId, goal), currentNode));
}
}
}
}
return null;
}
private List<Integer> getPath(Node node) {
List<Integer> path = new ArrayList<>();
while (node != null) {
path.add(0, node.id);
node = node.parent;
}
return path;
}
private int heuristic(int current, int goal) {
// 这里使用曼哈顿距离作为启发式函数
return Math.abs(current - goal);
}
}
4、Dijkstra算法
Dijkstra算法是一种用于在加权图中找到最短路径的算法。它从源节点开始，首先访问所有直接相邻的节点，然后访问所有距离源节点为2的节点，以此类推，直到访问到目标节点。与广度优先搜索不同，Dijkstra算法考虑了边的权重，因此它适用于加权图。
Java代码实现：
import java.util.*;
public class DijkstraAlgorithm {
public void dijkstra(int graph[][], int src) {
int V = graph.length;
int dist[] = new int[V]; // 存储最短路径的数组
Boolean sptSet[] = new Boolean[V]; // 标记节点是否被包括在最短路径树中
// 初始化所有距离为无穷大，sptSet全部为false
for (int i = 0; i < V; i++) {
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
}
// 源节点到自己的距离为0
dist[src] = 0;
// 找到最短路径树中的所有节点
for (int count = 0; count < V - 1; count++) {
// 从未处理的节点中选择最小距离节点
int u = minDistance(dist, sptSet);
// 标记选中的节点为处理过
sptSet[u] = true;
// 更新与选中节点相邻的节点的距离
for (int v = 0; v < V; v++) {
if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
// 打印最短路径数组
printSolution(dist, V);
}
// 一个用来找到最小距离节点的函数
private int minDistance(int dist[], Boolean sptSet[]) {
int min = Integer.MAX_VALUE, minIndex = -1;
for (int v = 0; v < dist.length; v++) {
if (!sptSet[v] && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
}
// 打印构造的最短路径树
private void printSolution(int dist[], int n) {
System.out.println("节点 \t\t 最短距离");
for (int i = 0; i < n; i++) {
System.out.println(i + " \t\t " + dist[i]);
}
}
public static void main(String[] args) {
DijkstraAlgorithm dijkstra = new DijkstraAlgorithm();
int graph[][] = new int[][] {
{
0, 4, 0, 0, 0, 0, 0, 8, 0},
{
4, 0, 8, 0, 0, 0, 0, 11, 0},
{
0, 8, 0, 7, 0, 4, 0, 0, 2},
{
0, 0, 7, 0, 9, 14, 0, 0, 0},
{
0, 0, 0, 9, 0, 10, 0, 0, 0},
{
0, 0, 4, 14, 10, 0, 2, 0, 0},
{
0, 0, 0, 0, 0, 2, 0, 1, 6},
{
8, 11, 0, 0, 0, 0, 1, 0, 7},
{
0, 0, 2, 0, 0, 0, 6, 7, 0}
};
dijkstra.dijkstra(graph, 0);
}
}
以上是四种图搜索算法的Java实现。每种算法都有其特定的应用场景：
- DFS适用于探索所有可能的分支，例如游戏中的棋盘搜索、编译器中的语法分析等。
- BFS适用于寻找最短路径，特别是在无权图中。
A*搜索算法适用于在有权图中寻找最短路径，特别是当图较大且目标节点较远时。- Dijkstra算法适用于在有权图中寻找最短路径，但不适用于有负权边的图。
在实际应用中，选择合适的算法取决于具体问题的需求和图的结构特性。这里 V哥必须要强调一下，如果图很大且目标节点很远，A*搜索算法可能是更好的选择，因为它使用启发式函数来指导搜索，从而减少搜索空间。如果图是无权的，或者权重相同，BFS将是一个简单且有效的选择。DFS则适用于需要探索所有可能性的情况。好了，以上就是 V哥关于图搜索算法的一些见解，分享给你，一起进步。
