图论算法
# 图论算法
# 📋 学习目标
- 掌握图的基本概念和表示方法
- 理解图的遍历算法（DFS、BFS）
- 学会最短路径算法
- 掌握最小生成树算法
- 了解拓扑排序和强连通分量
# 🏗️ 图的基础
# 图的表示
# 邻接矩阵
class GraphMatrix {
private int[][] matrix;
private int vertices;
public GraphMatrix(int vertices) {
this.vertices = vertices;
this.matrix = new int[vertices][vertices];
}
public void addEdge(int src, int dest, int weight) {
matrix[src][dest] = weight;
matrix[dest][src] = weight; // 无向图
}
}
# 邻接表
class GraphList {
private List<List<Integer>> adjList;
private int vertices;
public GraphList(int vertices) {
this.vertices = vertices;
this.adjList = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
adjList.add(new ArrayList<>());
}
}
public void addEdge(int src, int dest) {
adjList.get(src).add(dest);
adjList.get(dest).add(src); // 无向图
}
}
# 🔍 图的遍历
# 深度优先搜索 (DFS)
public void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
visited[node] = true;
System.out.print(node + " ");
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
dfs(graph, neighbor, visited);
}
}
}
# 广度优先搜索 (BFS)
public void bfs(List<List<Integer>> graph, int start) {
boolean[] visited = new boolean[graph.size()];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
}
# 🛣️ 最短路径算法
# Dijkstra算法
public int[] dijkstra(int[][] graph, int src) {
int n = graph.length;
int[] dist = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 0; i < n - 1; i++) {
int u = minDistance(dist, visited);
visited[u] = true;
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != 0 &&
dist[u] != Integer.MAX_VALUE &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
return dist;
}
# Floyd-Warshall算法
public int[][] floydWarshall(int[][] graph) {
int n = graph.length;
int[][] dist = new int[n][n];
// 初始化距离矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = graph[i][j];
}
}
// 通过所有顶点更新最短路径
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}
# 🌳 最小生成树
# Kruskal算法
class Edge implements Comparable<Edge> {
int src, dest, weight;
public int compareTo(Edge other) {
return this.weight - other.weight;
}
}
public List<Edge> kruskal(List<Edge> edges, int vertices) {
Collections.sort(edges);
UnionFind uf = new UnionFind(vertices);
List<Edge> result = new ArrayList<>();
for (Edge edge : edges) {
if (uf.find(edge.src) != uf.find(edge.dest)) {
uf.union(edge.src, edge.dest);
result.add(edge);
}
}
return result;
}