图

图的定义

图（Graph）是由顶点 (Vertex) 集合 V 和边 (Edge) 集合 E 组成的数据结构，记为 G=(V,E)，其中：

顶点是数据元素的抽象
边表示顶点之间的关系，分为有向边和无向边
边可以带权重，表示顶点间关系的强度或成本

术语

图的基本构成

顶点（Vertex/Node） 图中的基本元素，表示一个实体（如城市、用户、网页等），通常用圆圈或点表示。
边（Edge/Arc） 连接两个顶点的线，表示顶点之间的关系。边可以是有向或无向的：
- 无向边：顶点间的双向关系，用(u, v)表示，u和v可互相到达。
- 有向边：顶点间的单向关系，用<u, v>表示，仅能从u到达v（u称为起点，v称为终点）。
权重（Weight/Cost） 边的附加数值，表示顶点间关系的强度、距离、成本等（如路网中两点的距离）。带权重的图称为带权图，反之称为无权图。

图的分类

按边的方向
- 无向图：所有边均为无向边，边是双向的。
- 有向图（Digraph）：至少包含一条有向边，边是单向的。
按边的权重
- 无权图：所有边的权重默认为 1（或无意义）。
- 带权图（Weighted Graph）：边带有具体权重值。
按顶点间的连接性
- 完全图：任意两个顶点间都存在直接边（无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条边，n为顶点数）。
- 稀疏图：边数远小于完全图的图（通常e < n log n，e为边数）。
- 稠密图：边数接近完全图的图。
其他特殊图
- 空图：没有顶点或边的图。
- 平凡图：只有一个顶点且没有边的图。
- 多重图：允许两个顶点间存在多条边（如同一对城市间有不同路线）。
- 自环（Loop）：起点和终点为同一顶点的边（如(u, u)或<u, u>）。

顶点与边的关系

邻接（Adjacent） 若两个顶点间存在直接边，则称它们互为邻接点。例如：
- 无向图中，若(u, v)存在，则u与v邻接。
- 有向图中，若<u, v>存在，则u邻接到v，v邻接于u。
关联（Incident） 边与顶点的关系：若边e连接顶点u和v，则称e与u、v相关联。
度（Degree） 与顶点相关联的边的数量，分以下类型：
- 无向图：顶点u的度记为deg(u)，等于关联到u的边数（自环算 2 度）。
- 有向图
  ：
  - 入度（In-degree）：以顶点u为终点的边的数量，记为in_deg(u)。
  - 出度（Out-degree）：以顶点u为起点的边的数量，记为out_deg(u)。
  - 总度 = 入度 + 出度（自环算 2 度）。

路径与回路

路径（Path） 由顶点和边组成的序列v₀, e₁, v₁, e₂, ..., vₖ，其中每条边eᵢ连接vᵢ₋₁和vᵢ。
- 路径长度：路径中边的数量（带权图中为权重之和）。
- 简单路径：顶点不重复的路径（如v₀→v₁→v₂，顶点均唯一）。
回路（Cycle） 起点和终点相同的路径（如v₀→v₁→v₂→v₀）。
- 简单回路：除起点和终点外，其他顶点不重复的回路。

连通性

连通（Connected）
- 无向图中，若顶点u和v之间存在路径，则称u和v连通。
- 有向图中，若u到v和v到u均存在路径，则称u和v强连通。
连通图
- 无向图中，任意两个顶点都连通的图。
- 有向图中，任意两个顶点都强连通的图称为强连通图。
连通分量（Connected Component） 无向图中最大的连通子图（子图内顶点全连通，且无法再添加其他顶点保持连通）。
强连通分量（Strongly Connected Component, SCC） 有向图中最大的强连通子图（子图内任意两顶点互相可达）。

子图与生成树

子图（Subgraph） 由原图的部分顶点和边组成的图（顶点和边均为原图的子集）。
生成子图（Spanning Subgraph） 包含原图所有顶点的子图（边可以是原图的子集）。
生成树（Spanning Tree） 连通图的生成子图，且是一棵树（无回路、边数为n-1，n为顶点数）。
- 最小生成树（Minimum Spanning Tree, MST）：带权连通图中，总权重最小的生成树。

图的表示相关

邻接矩阵（Adjacency Matrix） 用n×n矩阵表示图，matrix[i][j]表示顶点i到j的边的权重（0 表示无边）。
邻接表（Adjacency List） 用链表（或数组）存储每个顶点的邻接顶点及边的权重，适合稀疏图。
边列表（Edge List） 用列表直接存储所有边的起点、终点和权重，适合需要频繁遍历所有边的场景。

图的抽象数据类型 (ADT)

import java.util.List;

public interface Graph<T> {
    // 添加顶点
    void addVertex(T vertex);
    
    // 添加边
    void addEdge(T source, T destination);
    void addEdge(T source, T destination, int weight);  // 带权图
    
    // 删除顶点
    boolean removeVertex(T vertex);
    
    // 删除边
    void removeEdge(T source, T destination);
    
    // 获取顶点的邻接顶点
    List<T> getNeighbors(T vertex);
    
    // 获取边的权重
    int getWeight(T source, T destination);
    
    // 判断图是否为空
    boolean isEmpty();
    
    // 获取顶点数量
    int getVertexCount();
    
    // 获取边数量
    int getEdgeCount();
    
    // 获取所有顶点
    List<T> getVertices();
}

图的存储实现

1. 邻接矩阵实现

用二维数组表示图

用0表示无边，1表示有边

import java.util.*;

public class AdjacencyMatrixGraph<T> implements Graph<T> {
    private Map<T, Integer> vertexIndices;  // 顶点到索引的映射
    private int[][] adjacencyMatrix;        // 邻接矩阵
    private List<T> vertices;               // 顶点列表
    private int edgeCount;                  // 边数量
    private boolean isDirected;             // 是否为有向图

    public AdjacencyMatrixGraph(boolean isDirected) {
        this.isDirected = isDirected;
        this.vertexIndices = new HashMap<>();
        this.vertices = new ArrayList<>();
        this.adjacencyMatrix = new int[0][0];
        this.edgeCount = 0;
    }

    @Override
    public void addVertex(T vertex) {
        if (!vertexIndices.containsKey(vertex)) {
            vertexIndices.put(vertex, vertices.size());
            vertices.add(vertex);
            
            // 扩展邻接矩阵
            int newSize = vertices.size();
            int[][] newMatrix = new int[newSize][newSize];
            for (int i = 0; i < newSize - 1; i++) {
                System.arraycopy(adjacencyMatrix[i], 0, newMatrix[i], 0, newSize - 1);
            }
            adjacencyMatrix = newMatrix;
        }
    }

    @Override
    public void addEdge(T source, T destination) {
        addEdge(source, destination, 1);  // 默认权重为1
    }

    @Override
    public void addEdge(T source, T destination, int weight) {
        if (!vertexIndices.containsKey(source) || !vertexIndices.containsKey(destination)) {
            throw new IllegalArgumentException("顶点不存在");
        }

        int sourceIndex = vertexIndices.get(source);
        int destIndex = vertexIndices.get(destination);
        
        // 避免重复添加边
        if (adjacencyMatrix[sourceIndex][destIndex] == 0) {
            adjacencyMatrix[sourceIndex][destIndex] = weight;
            edgeCount++;
            
            // 无向图需要添加反向边
            if (!isDirected) {
                adjacencyMatrix[destIndex][sourceIndex] = weight;
            }
        }
    }

    @Override
    public boolean removeVertex(T vertex) {
        if (!vertexIndices.containsKey(vertex)) {
            return false;
        }

        int removeIndex = vertexIndices.get(vertex);
        int size = vertices.size();
        
        // 更新顶点列表和索引映射
        vertices.remove(removeIndex);
        vertexIndices.remove(vertex);
        vertexIndices.replaceAll((v, idx) -> idx > removeIndex ? idx - 1 : idx);
        
        // 更新邻接矩阵
        int[][] newMatrix = new int[size - 1][size - 1];
        for (int i = 0, row = 0; i < size; i++) {
            if (i == removeIndex) continue;
            for (int j = 0, col = 0; j < size; j++) {
                if (j == removeIndex) continue;
                newMatrix[row][col++] = adjacencyMatrix[i][j];
            }
            row++;
        }
        adjacencyMatrix = newMatrix;
        return true;
    }

    @Override
    public void removeEdge(T source, T destination) {
        if (!vertexIndices.containsKey(source) || !vertexIndices.containsKey(destination)) {
            return;
        }

        int sourceIndex = vertexIndices.get(source);
        int destIndex = vertexIndices.get(destination);
        
        if (adjacencyMatrix[sourceIndex][destIndex] != 0) {
            adjacencyMatrix[sourceIndex][destIndex] = 0;
            edgeCount--;
            
            if (!isDirected) {
                adjacencyMatrix[destIndex][sourceIndex] = 0;
            }
        }
    }

    @Override
    public List<T> getNeighbors(T vertex) {
        List<T> neighbors = new ArrayList<>();
        if (!vertexIndices.containsKey(vertex)) {
            return neighbors;
        }

        int index = vertexIndices.get(vertex);
        for (int i = 0; i < vertices.size(); i++) {
            if (adjacencyMatrix[index][i] != 0) {
                neighbors.add(vertices.get(i));
            }
        }
        return neighbors;
    }

    @Override
    public int getWeight(T source, T destination) {
        if (!vertexIndices.containsKey(source) || !vertexIndices.containsKey(destination)) {
            return 0;
        }
        return adjacencyMatrix[vertexIndices.get(source)][vertexIndices.get(destination)];
    }

    @Override
    public boolean isEmpty() {
        return vertices.isEmpty();
    }

    @Override
    public int getVertexCount() {
        return vertices.size();
    }

    @Override
    public int getEdgeCount() {
        return edgeCount;
    }
    
    @Override
    public List<T> getVertices() {
        return new ArrayList<>(vertices);
    }
    
    // 打印邻接矩阵
    public void printMatrix() {
        System.out.print("   ");
        for (T vertex : vertices) {
            System.out.printf("%-4s", vertex);
        }
        System.out.println();
        
        for (int i = 0; i < vertices.size(); i++) {
            System.out.printf("%-3s", vertices.get(i));
            for (int j = 0; j < vertices.size(); j++) {
                System.out.printf("%-4d", adjacencyMatrix[i][j]);
            }
            System.out.println();
        }
    }
}

邻接矩阵优缺点与复杂度：

优点：查询边是否存在、获取边权重效率高 (O (1))
缺点：空间复杂度高 (O (n²))，不适合稀疏图
适用场景：稠密图、需要频繁查询边信息的场景

2. 邻接表实现

为了解决稀疏图问题

用邻接表，一定要够稀疏才合算

稀疏图（点很多，边很少）

稠密图或者完全图？

import java.util.*;

// 边的表示
class Edge<T> {
    private T destination;
    private int weight;

    public Edge(T destination, int weight) {
        this.destination = destination;
        this.weight = weight;
    }

    public T getDestination() {
        return destination;
    }

    public int getWeight() {
        return weight;
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Edge<?> edge = (Edge<?>) o;
        return Objects.equals(destination, edge.destination);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(destination);
    }
}

public class AdjacencyListGraph<T> implements Graph<T> {
    private Map<T, List<Edge<T>>> adjacencyList;  // 邻接表
    private boolean isDirected;                   // 是否为有向图
    private int edgeCount;                        // 边数量

    public AdjacencyListGraph(boolean isDirected) {
        this.isDirected = isDirected;
        this.adjacencyList = new HashMap<>();
        this.edgeCount = 0;
    }

    @Override
    public void addVertex(T vertex) {
        adjacencyList.putIfAbsent(vertex, new ArrayList<>());
    }

    @Override
    public void addEdge(T source, T destination) {
        addEdge(source, destination, 1);
    }

    @Override
    public void addEdge(T source, T destination, int weight) {
        addVertex(source);
        addVertex(destination);
        
        // 检查边是否已存在
        List<Edge<T>> edges = adjacencyList.get(source);
        if (!edges.contains(new Edge<>(destination, weight))) {
            edges.add(new Edge<>(destination, weight));
            edgeCount++;
            
            // 无向图添加反向边
            if (!isDirected) {
                adjacencyList.get(destination).add(new Edge<>(source, weight));
            }
        }
    }

    @Override
    public boolean removeVertex(T vertex) {
        if (!adjacencyList.containsKey(vertex)) {
            return false;
        }
        
        // 移除所有指向该顶点的边
        int removedEdges = adjacencyList.get(vertex).size();
        adjacencyList.remove(vertex);
        edgeCount -= removedEdges;
        
        // 移除其他顶点指向该顶点的边
        for (List<Edge<T>> edges : adjacencyList.values()) {
            Iterator<Edge<T>> iterator = edges.iterator();
            while (iterator.hasNext()) {
                if (iterator.next().getDestination().equals(vertex)) {
                    iterator.remove();
                    edgeCount--;
                    if (!isDirected) break;  // 无向图已双向删除
                }
            }
        }
        return true;
    }

    @Override
    public void removeEdge(T source, T destination) {
        if (!adjacencyList.containsKey(source)) {
            return;
        }
        
        // 移除源顶点到目标顶点的边
        List<Edge<T>> edges = adjacencyList.get(source);
        boolean removed = edges.remove(new Edge<>(destination, 0));
        if (removed) {
            edgeCount--;
            
            // 无向图需要移除反向边
            if (!isDirected && adjacencyList.containsKey(destination)) {
                adjacencyList.get(destination).remove(new Edge<>(source, 0));
            }
        }
    }

    @Override
    public List<T> getNeighbors(T vertex) {
        List<T> neighbors = new ArrayList<>();
        if (adjacencyList.containsKey(vertex)) {
            for (Edge<T> edge : adjacencyList.get(vertex)) {
                neighbors.add(edge.getDestination());
            }
        }
        return neighbors;
    }

    @Override
    public int getWeight(T source, T destination) {
        if (adjacencyList.containsKey(source)) {
            for (Edge<T> edge : adjacencyList.get(source)) {
                if (edge.getDestination().equals(destination)) {
                    return edge.getWeight();
                }
            }
        }
        return 0;
    }

    @Override
    public boolean isEmpty() {
        return adjacencyList.isEmpty();
    }

    @Override
    public int getVertexCount() {
        return adjacencyList.size();
    }

    @Override
    public int getEdgeCount() {
        return edgeCount;
    }
    
    @Override
    public List<T> getVertices() {
        return new ArrayList<>(adjacencyList.keySet());
    }
    
    // 打印邻接表
    public void printList() {
        for (Map.Entry<T, List<Edge<T>>> entry : adjacencyList.entrySet()) {
            System.out.print(entry.getKey() + " -> ");
            for (Edge<T> edge : entry.getValue()) {
                System.out.print(edge.getDestination() + "(" + edge.getWeight() + ") ");
            }
            System.out.println();
        }
    }
}

邻接表优缺点与复杂度：

优点：空间效率高 (O (n+e))，适合稀疏图
缺点：查询边是否存在效率低 (O (degree (v)))
适用场景：稀疏图、需要频繁遍历邻接顶点的场景

图的遍历算法

1. 深度优先搜索 (DFS)

import java.util.*;

public class GraphDFS {
    // 递归实现深度优先搜索
    public static <T> List<T> dfsRecursive(Graph<T> graph, T start) {
        List<T> result = new ArrayList<>();
        if (graph.isEmpty() || !graph.getVertices().contains(start)) {
            return result;
        }
        
        Set<T> visited = new HashSet<>();
        dfsHelper(graph, start, visited, result);
        return result;
    }
    
    private static <T> void dfsHelper(Graph<T> graph, T current, 
                                     Set<T> visited, List<T> result) {
        // 标记当前顶点为已访问
        visited.add(current);
        result.add(current);
        
        // 递归访问所有未访问的邻接顶点
        for (T neighbor : graph.getNeighbors(current)) {
            if (!visited.contains(neighbor)) {
                dfsHelper(graph, neighbor, visited, result);
            }
        }
    }
    
    // 非递归实现深度优先搜索（使用栈）
    public static <T> List<T> dfsIterative(Graph<T> graph, T start) {
        List<T> result = new ArrayList<>();
        if (graph.isEmpty() || !graph.getVertices().contains(start)) {
            return result;
        }
        
        Set<T> visited = new HashSet<>();
        Stack<T> stack = new Stack<>();
        
        stack.push(start);
        visited.add(start);
        
        while (!stack.isEmpty()) {
            T current = stack.pop();
            result.add(current);
            
            // 将邻接顶点入栈（逆序入栈以保持遍历顺序）
            List<T> neighbors = graph.getNeighbors(current);
            Collections.reverse(neighbors);
            for (T neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    stack.push(neighbor);
                }
            }
        }
        return result;
    }
}

2. 广度优先搜索 (BFS)

import java.util.*;

public class GraphBFS {
    // 广度优先搜索（使用队列）
    public static <T> List<T> bfs(Graph<T> graph, T start) {
        List<T> result = new ArrayList<>();
        if (graph.isEmpty() || !graph.getVertices().contains(start)) {
            return result;
        }
        
        Set<T> visited = new HashSet<>();
        Queue<T> queue = new LinkedList<>();
        
        queue.add(start);
        visited.add(start);
        
        while (!queue.isEmpty()) {
            T current = queue.poll();
            result.add(current);
            
            // 将邻接顶点入队
            for (T neighbor : graph.getNeighbors(current)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
        return result;
    }
    
    // BFS扩展：计算从起点到各顶点的最短路径（无权图）
    public static <T> Map<T, Integer> bfsShortestPath(Graph<T> graph, T start) {
        Map<T, Integer> distances = new HashMap<>();
        if (graph.isEmpty() || !graph.getVertices().contains(start)) {
            return distances;
        }
        
        // 初始化距离为-1（不可达）
        for (T vertex : graph.getVertices()) {
            distances.put(vertex, -1);
        }
        
        Queue<T> queue = new LinkedList<>();
        queue.add(start);
        distances.put(start, 0);
        
        while (!queue.isEmpty()) {
            T current = queue.poll();
            
            for (T neighbor : graph.getNeighbors(current)) {
                if (distances.get(neighbor) == -1) {
                    distances.put(neighbor, distances.get(current) + 1);
                    queue.add(neighbor);
                }
            }
        }
        return distances;
    }
}

遍历算法复杂度对比：

算法	时间复杂度	空间复杂度	优点	缺点	应用场景
DFS	O(V+E)	O(V)	内存占用相对较小，适合探索所有可能路径	可能陷入深层路径，不保证最短路径	拓扑排序、连通性分析、迷宫求解
BFS	O(V+E)	O(V)	能找到最短路径（无权图），适合层序遍历	空间占用可能较大	最短路径（无权图）、社交网络好友推荐

图的连通

无向图

连通分量：无向图的极大连通子图

极大顶点数：再加1个顶点就不连通了

极大边数：包含子图中所有顶点相连的所有边

有向图

强连通：有向图中顶点v和w之间存在双向路径，则称v和w是强连通的

强连通图：有向图中任意两顶点均强连通

强连通分量：有向图的极大强连通子图

弱连通：不是强连通，但是把图中所有边的方向抹掉，变成无向图就是连通的了，就是若连通

连通性分析

import java.util.*;

public class GraphConnectivity {
    // 查找无向图的所有连通分量
    public static <T> List<List<T>> findConnectedComponents(Graph<T> graph) {
        List<List<T>> components = new ArrayList<>();
        if (graph.isEmpty()) {
            return components;
        }
        
        Set<T> visited = new HashSet<>();
        
        for (T vertex : graph.getVertices()) {
            if (!visited.contains(vertex)) {
                List<T> component = new ArrayList<>();
                dfsComponent(graph, vertex, visited, component);
                components.add(component);
            }
        }
        return components;
    }
    
    private static <T> void dfsComponent(Graph<T> graph, T current, 
                                        Set<T> visited, List<T> component) {
        visited.add(current);
        component.add(current);
        
        for (T neighbor : graph.getNeighbors(current)) {
            if (!visited.contains(neighbor)) {
                dfsComponent(graph, neighbor, visited, component);
            }
        }
    }
    
    // 判断两个顶点是否连通
    public static <T> boolean isConnected(Graph<T> graph, T start, T end) {
        if (graph.isEmpty() || !graph.getVertices().contains(start) || 
            !graph.getVertices().contains(end)) {
            return false;
        }
        
        Set<T> visited = new HashSet<>();
        Queue<T> queue = new LinkedList<>();
        queue.add(start);
        visited.add(start);
        
        while (!queue.isEmpty()) {
            T current = queue.poll();
            if (current.equals(end)) {
                return true;
            }
            
            for (T neighbor : graph.getNeighbors(current)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
        return false;
    }
    
    // 查找有向图的强连通分量（Kosaraju算法）
    public static <T> List<List<T>> findStronglyConnectedComponents(Graph<T> graph) {
        List<List<T>> components = new ArrayList<>();
        if (graph.isEmpty()) {
            return components;
        }
        
        // 步骤1：对原图进行DFS，记录顶点完成顺序
        Set<T> visited = new HashSet<>();
        Stack<T> stack = new Stack<>();
        
        for (T vertex : graph.getVertices()) {
            if (!visited.contains(vertex)) {
                dfsOrder(graph, vertex, visited, stack);
            }
        }
        
        // 步骤2：构建逆图
        Graph<T> reversedGraph = reverseGraph(graph);
        
        // 步骤3：按栈的顺序对逆图进行DFS
        visited.clear();
        while (!stack.isEmpty()) {
            T vertex = stack.pop();
            if (!visited.contains(vertex)) {
                List<T> component = new ArrayList<>();
                dfsComponent(reversedGraph, vertex, visited, component);
                components.add(component);
            }
        }
        
        return components;
    }
    
    private static <T> void dfsOrder(Graph<T> graph, T current, 
                                    Set<T> visited, Stack<T> stack) {
        visited.add(current);
        for (T neighbor : graph.getNeighbors(current)) {
            if (!visited.contains(neighbor)) {
                dfsOrder(graph, neighbor, visited, stack);
            }
        }
        stack.push(current);
    }
    
    private static <T> Graph<T> reverseGraph(Graph<T> graph) {
        Graph<T> reversed = new AdjacencyListGraph<>(true);
        for (T vertex : graph.getVertices()) {
            reversed.addVertex(vertex);
        }
        
        for (T source : graph.getVertices()) {
            for (T dest : graph.getNeighbors(source)) {
                reversed.addEdge(dest, source, graph.getWeight(source, dest));
            }
        }
        return reversed;
    }
}

最短路径算法

单源最短路

多源最短路

1. Dijkstra 算法（单源最短路径，适用于非负权图）

有权图的单源最短路算法

不能解决有负边的情况

import java.util.*;

public class DijkstraAlgorithm {
    // Dijkstra算法：返回从起点到所有其他顶点的最短路径
    public static <T> Map<T, Integer> dijkstra(Graph<T> graph, T start) {
        // 存储从起点到各顶点的最短距离
        Map<T, Integer> distances = new HashMap<>();
        // 存储最短路径的前驱顶点
        Map<T, T> predecessors = new HashMap<>();
        // 优先队列：按距离排序的顶点
        PriorityQueue<Map.Entry<T, Integer>> pq = new PriorityQueue<>(
            Comparator.comparingInt(Map.Entry::getValue)
        );
        
        // 初始化
        for (T vertex : graph.getVertices()) {
            distances.put(vertex, Integer.MAX_VALUE);
        }
        distances.put(start, 0);
        pq.add(new AbstractMap.SimpleEntry<>(start, 0));
        
        while (!pq.isEmpty()) {
            T current = pq.poll().getKey();
            
            for (T neighbor : graph.getNeighbors(current)) {
                int weight = graph.getWeight(current, neighbor);
                int newDistance = distances.get(current) + weight;
                
                //  relaxation操作
                if (newDistance < distances.get(neighbor)) {
                    distances.put(neighbor, newDistance);
                    predecessors.put(neighbor, current);
                    pq.add(new AbstractMap.SimpleEntry<>(neighbor, newDistance));
                }
            }
        }
        return distances;
    }
    
    // 获取从起点到终点的最短路径
    public static <T> List<T> getShortestPath(Graph<T> graph, T start, T end) {
        Map<T, Integer> distances = dijkstra(graph, start);
        Map<T, T> predecessors = new HashMap<>();
        
        // 重新运行以获取前驱节点
        PriorityQueue<Map.Entry<T, Integer>> pq = new PriorityQueue<>(
            Comparator.comparingInt(Map.Entry::getValue)
        );
        
        for (T vertex : graph.getVertices()) {
            pq.add(new AbstractMap.SimpleEntry<>(vertex, distances.get(vertex)));
        }
        
        while (!pq.isEmpty()) {
            T current = pq.poll().getKey();
            
            for (T neighbor : graph.getNeighbors(current)) {
                int weight = graph.getWeight(current, neighbor);
                if (distances.get(neighbor) == distances.get(current) + weight) {
                    predecessors.put(neighbor, current);
                }
            }
        }
        
        // 重建路径
        List<T> path = new ArrayList<>();
        T current = end;
        
        while (current != null) {
            path.add(current);
            current = predecessors.get(current);
        }
        
        Collections.reverse(path);
        
        // 检查路径是否有效
        if (path.size() == 1 && !path.get(0).equals(start)) {
            return new ArrayList<>(); // 无路径
        }
        
        return path;
    }
}

2. Bellman-Ford 算法（单源最短路径，可处理负权图）

import java.util.*;

public class BellmanFordAlgorithm {
    // Bellman-Ford算法：返回从起点到所有其他顶点的最短路径
    // 若存在负权回路，返回null
    public static <T> Map<T, Integer> bellmanFord(Graph<T> graph, T start) {
        // 存储从起点到各顶点的最短距离
        Map<T, Integer> distances = new HashMap<>();
        // 存储最短路径的前驱顶点
        Map<T, T> predecessors = new HashMap<>();
        
        // 初始化
        for (T vertex : graph.getVertices()) {
            distances.put(vertex, Integer.MAX_VALUE);
        }
        distances.put(start, 0);
        
        // 松弛所有边V-1次
        int vertexCount = graph.getVertexCount();
        for (int i = 0; i < vertexCount - 1; i++) {
            // 遍历所有边
            for (T u : graph.getVertices()) {
                for (T v : graph.getNeighbors(u)) {
                    int weight = graph.getWeight(u, v);
                    
                    if (distances.get(u) != Integer.MAX_VALUE && 
                        distances.get(u) + weight < distances.get(v)) {
                        distances.put(v, distances.get(u) + weight);
                        predecessors.put(v, u);
                    }
                }
            }
        }
        
        // 检查是否存在负权回路
        for (T u : graph.getVertices()) {
            for (T v : graph.getNeighbors(u)) {
                int weight = graph.getWeight(u, v);
                
                if (distances.get(u) != Integer.MAX_VALUE && 
                    distances.get(u) + weight < distances.get(v)) {
                    // 存在负权回路
                    return null;
                }
            }
        }
        
        return distances;
    }
}

3. Floyd-Warshall 算法（多源最短路径）

1. 直接将单源最短路算法调用|V|遍

T=O(|V|^3+|E|*|V|) 对稀疏图效果好

Floyd算法

T=O(|V|^3) 对稠密图效果好

import java.util.*;

public class FloydWarshallAlgorithm {
    // Floyd-Warshall算法：返回所有顶点对之间的最短路径
    public static <T> Map<T, Map<T, Integer>> floydWarshall(Graph<T> graph) {
        List<T> vertices = graph.getVertices();
        int n = vertices.size();
        
        // 创建顶点到索引的映射
        Map<T, Integer> vertexToIndex = new HashMap<>();
        for (int i = 0; i < n; i++) {
            vertexToIndex.put(vertices.get(i), i);
        }
        
        // 初始化距离矩阵
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE / 2); // 避免溢出
            dist[i][i] = 0;
        }
        
        // 填充初始边的权重
        for (T u : vertices) {
            int uIdx = vertexToIndex.get(u);
            for (T v : graph.getNeighbors(u)) {
                int vIdx = vertexToIndex.get(v);
                dist[uIdx][vIdx] = graph.getWeight(u, v);
            }
        }
        
        // Floyd-Warshall核心算法
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        // 转换回Map结构
        Map<T, Map<T, Integer>> result = new HashMap<>();
        for (int i = 0; i < n; i++) {
            T u = vertices.get(i);
            Map<T, Integer> row = new HashMap<>();
            for (int j = 0; j < n; j++) {
                T v = vertices.get(j);
                row.put(v, dist[i][j]);
            }
            result.put(u, row);
        }
        
        return result;
    }
}

最短路径算法对比：

算法	时间复杂度	空间复杂度	优点	缺点	应用场景
Dijkstra	O(E log V)	O(V)	高效，适用于非负权图	不能处理负权边	路由算法、地图导航
Bellman-Ford	O(VE)	O(V)	能处理负权边，检测负权回路	效率较低	存在负权边的网络
Floyd-Warshall	O(V³)	O(V²)	多源最短路径，实现简单	时间复杂度高	稠密图，顶点数量少的情况

最小生成树算法

无回路

|V|个顶点一定有|V|-1条边

生成树

包含全部顶点

|V| - 1 条边都在图里

最小

边的权重和最小

最小生成树存在<=>图连通

可以用贪心算法解决最小生成树

1. Kruskal 算法

加边算法

稀疏图

最小堆取最小边

并查集判断有无回路

从不构成回路的边中每次选择权重最小的

import java.util.*;

// 用于表示带权边的辅助类
class WeightedEdge<T> implements Comparable<WeightedEdge<T>> {
    private T source;
    private T destination;
    private int weight;
    
    public WeightedEdge(T source, T destination, int weight) {
        this.source = source;
        this.destination = destination;
        this.weight = weight;
    }
    
    public T getSource() { return source; }
    public T getDestination() { return destination; }
    public int getWeight() { return weight; }
    
    @Override
    public int compareTo(WeightedEdge<T> other) {
        return Integer.compare(this.weight, other.weight);
    }
}

// 并查集（Union-Find）数据结构，用于检测环
class UnionFind<T> {
    private Map<T, T> parent;
    private Map<T, Integer> rank;
    
    public UnionFind(Collection<T> elements) {
        parent = new HashMap<>();
        rank = new HashMap<>();
        
        for (T element : elements) {
            parent.put(element, element);
            rank.put(element, 0);
        }
    }
    
    // 查找元素的根节点
    public T find(T x) {
        if (!parent.get(x).equals(x)) {
            parent.put(x, find(parent.get(x))); // 路径压缩
        }
        return parent.get(x);
    }
    
    // 合并两个集合
    public void union(T x, T y) {
        T xRoot = find(x);
        T yRoot = find(y);
        
        if (xRoot.equals(yRoot)) return;
        
        // 按秩合并
        if (rank.get(xRoot) < rank.get(yRoot)) {
            parent.put(xRoot, yRoot);
        } else if (rank.get(xRoot) > rank.get(yRoot)) {
            parent.put(yRoot, xRoot);
        } else {
            parent.put(yRoot, xRoot);
            rank.put(xRoot, rank.get(xRoot) + 1);
        }
    }
    
    // 检查两个元素是否在同一个集合中
    public boolean isConnected(T x, T y) {
        return find(x).equals(find(y));
    }
}

public class KruskalAlgorithm {
    // Kruskal算法：返回最小生成树的边集合
    public static <T> List<WeightedEdge<T>> kruskal(Graph<T> graph) {
        List<WeightedEdge<T>> mst = new ArrayList<>();
        
        // 如果图的顶点数小于2，没有生成树
        if (graph.getVertexCount() < 2) {
            return mst;
        }
        
        // 1. 收集所有边并按权重排序
        List<WeightedEdge<T>> edges = new ArrayList<>();
        Set<String> addedEdges = new HashSet<>(); // 避免重复添加边
        
        for (T source : graph.getVertices()) {
            for (T dest : graph.getNeighbors(source)) {
                // 对于无向图，避免重复添加边
                String edgeKey1 = source.toString() + "-" + dest.toString();
                String edgeKey2 = dest.toString() + "-" + source.toString();
                
                if (!addedEdges.contains(edgeKey1) && !addedEdges.contains(edgeKey2)) {
                    edges.add(new WeightedEdge<>(source, dest, graph.getWeight(source, dest)));
                    addedEdges.add(edgeKey1);
                }
            }
        }
        
        // 按权重升序排序
        Collections.sort(edges);
        
        // 2. 初始化并查集
        UnionFind<T> uf = new UnionFind<>(graph.getVertices());
        
        // 3. 依次添加边，避免形成环
        for (WeightedEdge<T> edge : edges) {
            T u = edge.getSource();
            T v = edge.getDestination();
            
            if (!uf.isConnected(u, v)) {
                mst.add(edge);
                uf.union(u, v);
                
                // 当添加了V-1条边时，生成树已完成
                if (mst.size() == graph.getVertexCount() - 1) {
                    break;
                }
            }
        }
        
        // 检查是否形成了最小生成树（所有顶点是否连通）
        if (mst.size() != graph.getVertexCount() - 1) {
            return new ArrayList<>(); // 图不连通，没有生成树
        }
        
        return mst;
    }
}

2. Prim 算法

加点算法

T=O(|V|^2)

稠密图

import java.util.*;

public class PrimAlgorithm {
    // Prim算法：返回最小生成树的边集合
    public static <T> List<WeightedEdge<T>> prim(Graph<T> graph, T start) {
        List<WeightedEdge<T>> mst = new ArrayList<>();
        
        // 如果图的顶点数小于2，没有生成树
        if (graph.getVertexCount() < 2 || !graph.getVertices().contains(start)) {
            return mst;
        }
        
        // 已加入生成树的顶点
        Set<T> inMST = new HashSet<>();
        inMST.add(start);
        
        // 优先队列：存储候选边，按权重排序
        PriorityQueue<WeightedEdge<T>> pq = new PriorityQueue<>();
        
        // 初始加入起点的所有边
        for (T neighbor : graph.getNeighbors(start)) {
            pq.add(new WeightedEdge<>(start, neighbor, graph.getWeight(start, neighbor)));
        }
        
        // 直到所有顶点都加入生成树
        while (inMST.size() < graph.getVertexCount() && !pq.isEmpty()) {
            // 选择权重最小的边
            WeightedEdge<T> edge = pq.poll();
            T u = edge.getSource();
            T v = edge.getDestination();
            
            // 检查是否会形成环
            if (inMST.contains(u) && !inMST.contains(v)) {
                mst.add(edge);
                inMST.add(v);
                
                // 将新顶点的边加入优先队列
                for (T neighbor : graph.getNeighbors(v)) {
                    if (!inMST.contains(neighbor)) {
                        pq.add(new WeightedEdge<>(v, neighbor, graph.getWeight(v, neighbor)));
                    }
                }
            } else if (inMST.contains(v) && !inMST.contains(u)) {
                mst.add(edge);
                inMST.add(u);
                
                // 将新顶点的边加入优先队列
                for (T neighbor : graph.getNeighbors(u)) {
                    if (!inMST.contains(neighbor)) {
                        pq.add(new WeightedEdge<>(u, neighbor, graph.getWeight(u, neighbor)));
                    }
                }
            }
        }
        
        // 检查是否形成了最小生成树（所有顶点是否都已加入）
        if (inMST.size() != graph.getVertexCount()) {
            return new ArrayList<>(); // 图不连通，没有生成树
        }
        
        return mst;
    }
}

最小生成树算法对比：

算法	时间复杂度	空间复杂度	优点	缺点	应用场景
Kruskal	O(E log E)	O(V + E)	适合稀疏图，实现简单	对稠密图效率较低	网络设计、电路设计
Prim	O(E log V)	O(V)	适合稠密图，内存占用小	对稀疏图效率不如 Kruskal	通信网络设计、城市规划

关键路径

AOE(Activity On Edge)网络

一般用于安排项目的工序

## 可解决的常见问题

连通分量 Connected Component Tarjan算法

Flood Fill

寻路

走迷宫

迷宫生成

无权图的最短路径

环的判断

总结

图是一种强大的数据结构，能够建模各种复杂关系。本文介绍了图的基本概念、两种主要存储方式（邻接矩阵和邻接表）、遍历算法（DFS 和 BFS）、连通性分析、三种最短路径算法（Dijkstra、Bellman-Ford、Floyd-Warshall）以及两种最小生成树算法（Kruskal 和 Prim）。

选择合适的图算法和存储结构取决于具体问题：

稀疏图优先选择邻接表，稠密图可考虑邻接矩阵
非负权图的单源最短路径用 Dijkstra 算法
存在负权边时使用 Bellman-Ford 算法
多源最短路径可使用 Floyd-Warshall 算法
稀疏图的最小生成树优先考虑 Kruskal 算法
稠密图的最小生成树优先考虑 Prim 算法

这些算法在网络路由、社交网络分析、电路设计、地图导航等领域有广泛应用。

资料

全网最!详!细!Tarjan算法讲解 https://blog.csdn.net/hurmishine/article/details/75248876

最短路径问题---SPFA算法详解