Java图论算法竞赛应用详解

一、图的基本概念

1.1 什么是图

图（Graph）是一种非线性数据结构，由顶点（Vertex）的集合和边（Edge）的集合组成。在计算机科学中，图被广泛应用于表示各种实际问题，如社交网络、地图导航、网络拓扑等。

1.2 图的基本术语

顶点（Vertex）：图中的节点
边（Edge）：连接两个顶点的线段
有向图：边有方向
无向图：边无方向
权重：边上的数值
度：与顶点相连的边的数量

1.3 图的存储方式

1.3.1 邻接矩阵

public class AdjacencyMatrix {
    private int V; // 顶点数
    private int[][] matrix; // 邻接矩阵
    
    public AdjacencyMatrix(int v) {
        V = v;
        matrix = new int[v][v];
    }
    
    // 添加边
    public void addEdge(int source, int dest) {
        matrix[source][dest] = 1;
        matrix[dest][source] = 1; // 无向图需要这行
    }
}

1.3.2 邻接表

public class AdjacencyList {
    private int V;
    private ArrayList<ArrayList<Integer>> adj;
    
    public AdjacencyList(int v) {
        V = v;
        adj = new ArrayList<>(v);
        for (int i = 0; i < v; i++) {
            adj.add(new ArrayList<>());
        }
    }
    
    public void addEdge(int source, int dest) {
        adj.get(source).add(dest);
        adj.get(dest).add(source); // 无向图需要这行
    }
}

二、图的基本算法

2.1 深度优先搜索（DFS）

public class DFS {
    private boolean[] visited;
    private ArrayList<ArrayList<Integer>> adj;
    
    public DFS(ArrayList<ArrayList<Integer>> adj) {
        this.adj = adj;
        visited = new boolean[adj.size()];
    }
    
    public void dfs(int v) {
        visited[v] = true;
        System.out.print(v + " ");
        
        for (int n : adj.get(v)) {
            if (!visited[n]) {
                dfs(n);
            }
        }
    }
}

2.2 广度优先搜索（BFS）

public class BFS {
    private boolean[] visited;
    private ArrayList<ArrayList<Integer>> adj;
    
    public BFS(ArrayList<ArrayList<Integer>> adj) {
        this.adj = adj;
        visited = new boolean[adj.size()];
    }
    
    public void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.add(start);
        
        while (!queue.isEmpty()) {
            int v = queue.poll();
            System.out.print(v + " ");
            
            for (int n : adj.get(v)) {
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

2.3 最短路径算法

2.3.1 Dijkstra算法

public class Dijkstra {
    private static final int INF = Integer.MAX_VALUE;
    
    public static int[] shortestPath(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];
                }
            }
        }
        return dist;
    }
    
    private static 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;
    }
}

2.4 最小生成树

2.4.1 Kruskal算法

public class Kruskal {
    class Edge implements Comparable<Edge> {
        int src, dest, weight;
        
        public int compareTo(Edge other) {
            return this.weight - other.weight;
        }
    }
    
    class DisjointSet {
        int[] parent, rank;
        
        DisjointSet(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        
        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        void union(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            
            if (rank[xRoot] < rank[yRoot]) {
                parent[xRoot] = yRoot;
            } else if (rank[xRoot] > rank[yRoot]) {
                parent[yRoot] = xRoot;
            } else {
                parent[yRoot] = xRoot;
                rank[xRoot]++;
            }
        }
    }
    
    public Edge[] kruskalMST(Edge[] edges, int V) {
        Arrays.sort(edges);
        Edge[] result = new Edge[V-1];
        DisjointSet ds = new DisjointSet(V);
        
        int e = 0, i = 0;
        while (e < V-1) {
            Edge nextEdge = edges[i++];
            int x = ds.find(nextEdge.src);
            int y = ds.find(nextEdge.dest);
            
            if (x != y) {
                result[e++] = nextEdge;
                ds.union(x, y);
            }
        }
        return result;
    }
}

三、实际应用案例

3.1 图的连通性判断

public class ConnectivityCheck {
    private int V;
    private ArrayList<ArrayList<Integer>> adj;
    
    public ConnectivityCheck(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);
        adj.get(w).add(v);
    }
    
    private void DFSUtil(int v, boolean[] visited) {
        visited[v] = true;
        for (int n : adj.get(v)) {
            if (!visited[n]) {
                DFSUtil(n, visited);
            }
        }
    }
    
    public boolean isConnected() {
        boolean[] visited = new boolean[V];
        DFSUtil(0, visited);
        
        for (boolean v : visited) {
            if (!v) return false;
        }
        return true;
    }
}

3.2 拓扑排序

public class TopologicalSort {
    private int V;
    private ArrayList<ArrayList<Integer>> adj;
    
    public TopologicalSort(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);
    }
    
    private void topologicalSortUtil(int v, boolean[] visited, 
                                    Stack<Integer> stack) {
        visited[v] = true;
        
        for (int n : adj.get(v)) {
            if (!visited[n]) {
                topologicalSortUtil(n, visited, stack);
            }
        }
        
        stack.push(v);
    }
    
    public int[] topologicalSort() {
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[V];
        
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                topologicalSortUtil(i, visited, stack);
            }
        }
        
        int[] result = new int[V];
        for (int i = 0; i < V; i++) {
            result[i] = stack.pop();
        }
        return result;
    }
}