图的遍历是指访问图中的所有顶点，确保每个顶点被访问且仅被访问一次。常见的遍历方法有深度优先搜索（DFS）和广度优先搜索（BFS）。
DFS 通过递归或栈实现，沿着一条路径尽可能深入地访问顶点，直到无法继续为止，然后回溯并访问其他路径。
import java.util.*;
public class Graph {
private int V; // 顶点数
private LinkedList<Integer> adj[]; // 邻接表
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList<>();
}
void addEdge(int v, int w) {
adj[v].add(w); // 添加边
}
void DFSUtil(int v, boolean visited[]) {
visited[v] = true; // 标记当前顶点为已访问
System.out.print(v + " ");
// 递归访问所有邻接顶点
for (Integer n : adj[v]) {
if (!visited[n])
DFSUtil(n, visited);
}
}
void DFS(int v) {
boolean visited[] = new boolean[V]; // 初始化访问标记数组
DFSUtil(v, visited); // 从顶点 v 开始 DFS
}
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("DFS starting from vertex 2:");
g.DFS(2);
}
}BFS 使用队列实现，从起始顶点开始，逐层访问其邻接顶点。
void BFS(int v) {
boolean visited[] = new boolean[V]; // 初始化访问标记数组
LinkedList<Integer> queue = new LinkedList<>(); // 使用队列实现 BFS
visited[v] = true;
queue.add(v);
while (!queue.isEmpty()) {
v = queue.poll(); // 取出队首顶点
System.out.print(v + " ");
// 将所有未访问的邻接顶点加入队列
for (Integer n : adj[v]) {
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("BFS starting from vertex 2:");
g.BFS(2);
}最短路径算法用于找到图中两个顶点之间的最短路径。常见算法有 Dijkstra 算法和 Floyd-Warshall 算法。
Dijkstra 算法适用于带权图（权值为非负数），从单源顶点出发，找到到其他所有顶点的最短路径。
import java.util.*;
public class Dijkstra {
private static final int INF = Integer.MAX_VALUE;
void dijkstra(int graph[][], int src) {
int V = graph.length;
int dist[] = new int[V]; // 存储最短距离
boolean visited[] = new boolean[V]; // 标记顶点是否已处理
Arrays.fill(dist, INF);
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, visited); // 选择未处理的最小距离顶点
visited[u] = true;
// 更新邻接顶点的距离
for (int v = 0; v < V; v++) {
if (!visited[v] && graph[u][v] != 0 && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
printSolution(dist);
}
int minDistance(int dist[], boolean visited[]) {
int min = INF, minIndex = -1;
for (int v = 0; v < dist.length; v++) {
if (!visited[v] && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
}
void printSolution(int dist[]) {
System.out.println("Vertex \t Distance from Source");
for (int i = 0; i < dist.length; i++)
System.out.println(i + " \t\t " + dist[i]);
}
public static void main(String args[]) {
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 t = new Dijkstra();
t.dijkstra(graph, 0);
}
}最小生成树（MST）是连接图中所有顶点的边权值最小的树。常用算法有 Prim 算法和 Kruskal 算法。
Prim 算法从一个顶点开始，逐步扩展生成树，每次选择权值最小的边。
import java.util.*;
public class Prim {
private static final int INF = Integer.MAX_VALUE;
void primMST(int graph[][]) {
int V = graph.length;
int parent[] = new int[V]; // 存储 MST
int key[] = new int[V]; // 存储顶点的键值
boolean mstSet[] = new boolean[V]; // 标记顶点是否在 MST 中
Arrays.fill(key, INF);
key[0] = 0; // 从第一个顶点开始
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet); // 选择最小键值顶点
mstSet[u] = true;
// 更新邻接顶点的键值
for (int v = 0; v < V; v++) {
if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
printMST(parent, graph);
}
int minKey(int key[], boolean mstSet[]) {
int min = INF, minIndex = -1;
for (int v = 0; v < key.length; v++) {
if (!mstSet[v] && key[v] < min) {
min = key[v];
minIndex = v;
}
}
return minIndex;
}
void printMST(int parent[], int graph[][]) {
System.out.println("Edge \t Weight");
for (int i = 1; i < graph.length; i++)
System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
}
public static void main(String args[]) {
int graph[][] = new int[][] {
{ 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 }
};
Prim t = new Prim();
t.primMST(graph);
}
}图匹配是指在图中的边集中选择一些边，使得这些边没有共同的顶点。常见算法有匈牙利算法（用于二分图匹配）。
强连通分支（SCC）是指有向图中的极大强连通子图。常用算法有 Kosaraju 算法和 Tarjan 算法。
Kosaraju 算法通过两次 DFS 找到所有强连通分支。
import java.util.*;
public class Kosaraju {
private int V;
private LinkedList<Integer> adj[];
Kosaraju(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList<>();
}
void addEdge(int v, int w) {
adj[v].add(w);
}
void DFSUtil(int v, boolean visited[], List<Integer> component) {
visited[v] = true;
component.add(v);
for (Integer n : adj[v]) {
if (!visited[n])
DFSUtil(n, visited, component);
}
}
Kosaraju getTranspose() {
Kosaraju g = new Kosaraju(V);
for (int v = 0; v < V; v++) {
for (Integer n : adj[v]) {
g.adj[n].add(v);
}
}
return g;
}
void fillOrder(int v, boolean visited[], Stack<Integer> stack) {
visited[v] = true;
for (Integer n : adj[v]) {
if (!visited[n])
fillOrder(n, visited, stack);
}
stack.push(v);
}
void printSCCs() {
Stack<Integer> stack = new Stack<>();
boolean visited[] = new boolean[V];
Arrays.fill(visited, false);
for (int i = 0; i < V; i++) {
if (!visited[i])
fillOrder(i, visited, stack);
}
Kosaraju gr = getTranspose();
Arrays.fill(visited, false);
while (!stack.isEmpty()) {
int v = stack.pop();
if (!visited[v]) {
List<Integer> component = new ArrayList<>();
gr.DFSUtil(v, visited, component);
System.out.println(component);
}
}
}
public static void main(String args[]) {
Kosaraju g = new Kosaraju(5);
g.addEdge(1, 0);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.addEdge(0, 3);
g.addEdge(3, 4);
System.out.println("Strongly Connected Components:");
g.printSCCs();
}
}以上是Java中图的遍历、最短路径算法、最小生成树、图匹配和强连通分支算法的基本实现。这些算法是图论中的基础，掌握它们对于解决实际问题非常有帮助。