Java图论基础：有向图与无向图详解

图（Graph）是计算机科学中一种重要的非线性数据结构，广泛应用于社交网络、地图导航、任务调度等领域。本文将使用Java语言深入讲解图论中的两个基本概念：有向图和无向图。

什么是图？

图由两个基本元素组成：

• 顶点（Vertex/Node）：图中的节点，代表对象
• 边（Edge）：连接两个顶点，代表对象之间的关系

数学表示：G = (V, E)，其中V是顶点集合，E是边集合。

无向图（Undirected Graph）

概念与特点

无向图中的边没有方向，表示对称的双向关系。如果顶点A和顶点B之间存在一条边，那么可以从A到达B，也可以从B到达A。

实际应用

• 社交网络：微信好友关系（互为好友）
• 交通网络：城市间的双向道路
• 协作关系：项目团队成员之间的合作关系
• 网络拓扑：局域网中设备的连接关系

Java实现：邻接表方式

import java.util.*; ​ /** * 无向图的实现（使用邻接表） */ public class UndirectedGraph {    // 使用HashMap存储图，key为顶点，value为邻接顶点列表    private Map<String, List<String>> adjList;        public UndirectedGraph() {        this.adjList = new HashMap<>();   }        /**     * 添加顶点     */    public void addVertex(String vertex) {        adjList.putIfAbsent(vertex, new ArrayList<>());   }        /**     * 添加边（无向边，需要双向添加）     */    public void addEdge(String v1, String v2) {        // 确保两个顶点都存在        addVertex(v1);        addVertex(v2);                // 添加双向边        adjList.get(v1).add(v2);        adjList.get(v2).add(v1);   }        /**     * 移除边     */    public void removeEdge(String v1, String v2) {        List<String> v1Neighbors = adjList.get(v1);        List<String> v2Neighbors = adjList.get(v2);                if (v1Neighbors != null) {            v1Neighbors.remove(v2);       }        if (v2Neighbors != null) {            v2Neighbors.remove(v1);       }   }        /**     * 移除顶点     */    public void removeVertex(String vertex) {        // 移除所有与该顶点相连的边        List<String> neighbors = adjList.get(vertex);        if (neighbors != null) {            for (String neighbor : new ArrayList<>(neighbors)) {                removeEdge(vertex, neighbor);           }       }        // 移除顶点        adjList.remove(vertex);   }        /**     * 获取顶点的度（连接的边的数量）     */    public int getDegree(String vertex) {        List<String> neighbors = adjList.get(vertex);        return neighbors != null ? neighbors.size() : 0;   }        /**     * 获取邻接顶点     */    public List<String> getNeighbors(String vertex) {        return adjList.getOrDefault(vertex, new ArrayList<>());   }        /**     * 深度优先搜索（DFS）     */    public void dfs(String start) {        Set<String> visited = new HashSet<>();        dfsHelper(start, visited);   }        private void dfsHelper(String vertex, Set<String> visited) {        visited.add(vertex);        System.out.print(vertex + " ");                for (String neighbor : getNeighbors(vertex)) {            if (!visited.contains(neighbor)) {                dfsHelper(neighbor, visited);           }       }   }        /**     * 广度优先搜索（BFS）     */    public void bfs(String start) {        Set<String> visited = new HashSet<>();        Queue<String> queue = new LinkedList<>();                visited.add(start);        queue.offer(start);                while (!queue.isEmpty()) {            String vertex = queue.poll();            System.out.print(vertex + " ");                        for (String neighbor : getNeighbors(vertex)) {                if (!visited.contains(neighbor)) {                    visited.add(neighbor);                    queue.offer(neighbor);               }           }       }   }        /**     * 打印图结构     */    public void display() {        System.out.println("无向图结构：");        for (Map.Entry<String, List<String>> entry : adjList.entrySet()) {            System.out.println(entry.getKey() + " -> " + entry.getValue());       }   } }

无向图使用示例

public class UndirectedGraphDemo {    public static void main(String[] args) {        UndirectedGraph graph = new UndirectedGraph();                // 构建社交网络        graph.addEdge("Alice", "Bob");        graph.addEdge("Alice", "Charlie");        graph.addEdge("Bob", "David");        graph.addEdge("Charlie", "David");        graph.addEdge("David", "Eve");                // 显示图结构        graph.display();                System.out.println("\n各顶点的度：");        System.out.println("Alice的度: " + graph.getDegree("Alice"));        System.out.println("David的度: " + graph.getDegree("David"));                System.out.println("\n深度优先搜索（从Alice开始）：");        graph.dfs("Alice");                System.out.println("\n\n广度优先搜索（从Alice开始）：");        graph.bfs("Alice");   } }

有向图（Directed Graph）

概念与特点

有向图中的边具有方向性，从一个顶点指向另一个顶点。边<A, B>表示从A到B的单向关系，不代表可以从B到A。

实际应用

• 微博关注：用户A关注用户B，但B不一定关注A
• 网页链接：网页间的超链接关系
• 任务依赖：项目中任务的先后顺序
• 交通系统：单行道网络
• 课程prerequisite：课程的先修关系

Java实现：邻接表方式

import java.util.*; ​ /** * 有向图的实现（使用邻接表） */ public class DirectedGraph {    private Map<String, List<String>> adjList;        public DirectedGraph() {        this.adjList = new HashMap<>();   }        /**     * 添加顶点     */    public void addVertex(String vertex) {        adjList.putIfAbsent(vertex, new ArrayList<>());   }        /**     * 添加有向边（从v1指向v2）     */    public void addEdge(String from, String to) {        addVertex(from);        addVertex(to);                // 只添加单向边        adjList.get(from).add(to);   }        /**     * 移除边     */    public void removeEdge(String from, String to) {        List<String> neighbors = adjList.get(from);        if (neighbors != null) {            neighbors.remove(to);       }   }        /**     * 移除顶点     */    public void removeVertex(String vertex) {        // 移除从该顶点出发的所有边        adjList.remove(vertex);                // 移除指向该顶点的所有边        for (List<String> neighbors : adjList.values()) {            neighbors.remove(vertex);       }   }        /**     * 获取出度（从该顶点出发的边数）     */    public int getOutDegree(String vertex) {        List<String> neighbors = adjList.get(vertex);        return neighbors != null ? neighbors.size() : 0;   }        /**     * 获取入度（指向该顶点的边数）     */    public int getInDegree(String vertex) {        int count = 0;        for (List<String> neighbors : adjList.values()) {            if (neighbors.contains(vertex)) {                count++;           }       }        return count;   }        /**     * 获取邻接顶点（出边指向的顶点）     */    public List<String> getNeighbors(String vertex) {        return adjList.getOrDefault(vertex, new ArrayList<>());   }        /**     * 拓扑排序（Kahn算法）     * 适用于有向无环图（DAG）     */    public List<String> topologicalSort() {        List<String> result = new ArrayList<>();        Map<String, Integer> inDegree = new HashMap<>();        Queue<String> queue = new LinkedList<>();                // 计算所有顶点的入度        for (String vertex : adjList.keySet()) {            inDegree.put(vertex, getInDegree(vertex));       }                // 将入度为0的顶点加入队列        for (Map.Entry<String, Integer> entry : inDegree.entrySet()) {            if (entry.getValue() == 0) {                queue.offer(entry.getKey());           }       }                // BFS处理        while (!queue.isEmpty()) {            String vertex = queue.poll();            result.add(vertex);                        // 减少邻接顶点的入度            for (String neighbor : getNeighbors(vertex)) {                inDegree.put(neighbor, inDegree.get(neighbor) - 1);                if (inDegree.get(neighbor) == 0) {                    queue.offer(neighbor);               }           }       }                // 如果结果包含所有顶点，说明没有环        if (result.size() != adjList.size()) {            System.out.println("图中存在环，无法进行拓扑排序！");            return new ArrayList<>();       }                return result;   }        /**     * 检测是否存在环（使用DFS）     */    public boolean hasCycle() {        Set<String> visited = new HashSet<>();        Set<String> recStack = new HashSet<>();                for (String vertex : adjList.keySet()) {            if (hasCycleHelper(vertex, visited, recStack)) {                return true;           }       }        return false;   }        private boolean hasCycleHelper(String vertex, Set<String> visited,                                   Set<String> recStack) {        if (recStack.contains(vertex)) {            return true; // 发现环       }        if (visited.contains(vertex)) {            return false;       }                visited.add(vertex);        recStack.add(vertex);                for (String neighbor : getNeighbors(vertex)) {            if (hasCycleHelper(neighbor, visited, recStack)) {                return true;           }       }                recStack.remove(vertex);        return false;   }        /**     * 深度优先搜索     */    public void dfs(String start) {        Set<String> visited = new HashSet<>();        dfsHelper(start, visited);   }        private void dfsHelper(String vertex, Set<String> visited) {        visited.add(vertex);        System.out.print(vertex + " ");                for (String neighbor : getNeighbors(vertex)) {            if (!visited.contains(neighbor)) {                dfsHelper(neighbor, visited);           }       }   }        /**     * 打印图结构     */    public void display() {        System.out.println("有向图结构：");        for (Map.Entry<String, List<String>> entry : adjList.entrySet()) {            System.out.println(entry.getKey() + " -> " + entry.getValue());       }   } }

有向图使用示例

public class DirectedGraphDemo {    public static void main(String[] args) {        DirectedGraph graph = new DirectedGraph();                // 构建课程依赖关系图        graph.addEdge("数据结构", "算法");        graph.addEdge("离散数学", "数据结构");        graph.addEdge("离散数学", "算法");        graph.addEdge("程序设计", "数据结构");        graph.addEdge("算法", "人工智能");        graph.addEdge("数据结构", "数据库");                // 显示图结构        graph.display();                System.out.println("\n各顶点的入度和出度：");        System.out.println("数据结构 - 入度: " + graph.getInDegree("数据结构") +                         ", 出度: " + graph.getOutDegree("数据结构"));        System.out.println("算法 - 入度: " + graph.getInDegree("算法") +                         ", 出度: " + graph.getOutDegree("算法"));                System.out.println("\n检测环：");        System.out.println("是否存在环: " + graph.hasCycle());                System.out.println("\n拓扑排序（课程学习顺序）：");        List<String> order = graph.topologicalSort();        System.out.println(order);                System.out.println("\n深度优先搜索（从离散数学开始）：");        graph.dfs("离散数学");   } }

邻接矩阵实现

除了邻接表，图还可以用邻接矩阵表示，特别适合稠密图。

/** * 使用邻接矩阵实现的图（支持有向图和无向图） */ public class GraphMatrix {    private int[][] matrix;    private Map<String, Integer> vertexIndex;    private Map<Integer, String> indexVertex;    private int vertexCount;    private boolean isDirected;        public GraphMatrix(int maxVertices, boolean isDirected) {        this.matrix = new int[maxVertices][maxVertices];        this.vertexIndex = new HashMap<>();        this.indexVertex = new HashMap<>();        this.vertexCount = 0;        this.isDirected = isDirected;   }        /**     * 添加顶点     */    public void addVertex(String vertex) {        if (!vertexIndex.containsKey(vertex)) {            vertexIndex.put(vertex, vertexCount);            indexVertex.put(vertexCount, vertex);            vertexCount++;       }   }        /**     * 添加边     */    public void addEdge(String v1, String v2) {        addVertex(v1);        addVertex(v2);                int index1 = vertexIndex.get(v1);        int index2 = vertexIndex.get(v2);                matrix[index1][index2] = 1;                // 如果是无向图，需要添加反向边        if (!isDirected) {            matrix[index2][index1] = 1;       }   }        /**     * 检查是否存在边     */    public boolean hasEdge(String v1, String v2) {        Integer index1 = vertexIndex.get(v1);        Integer index2 = vertexIndex.get(v2);                if (index1 == null || index2 == null) {            return false;       }                return matrix[index1][index2] == 1;   }        /**     * 打印邻接矩阵     */    public void display() {        System.out.println("邻接矩阵：");        System.out.print("   ");        for (int i = 0; i < vertexCount; i++) {            System.out.printf("%-8s", indexVertex.get(i));       }        System.out.println();                for (int i = 0; i < vertexCount; i++) {            System.out.printf("%-4s", indexVertex.get(i));            for (int j = 0; j < vertexCount; j++) {                System.out.printf("%-8d", matrix[i][j]);           }            System.out.println();       }   } }

有向图 vs 无向图对比

图的表示方法选择

邻接表 vs 邻接矩阵

邻接表

• 空间复杂度：O(V + E)
• 适合稀疏图（边少）
• 遍历某个顶点的邻接点快
• 判断两点是否相邻较慢

邻接矩阵

• 空间复杂度：O(V²)
• 适合稠密图（边多）
• 判断两点是否相邻快O(1)
• 浪费空间存储不存在的边

常用图算法

遍历算法

• 深度优先搜索（DFS）：递归或栈实现
• 广度优先搜索（BFS）：队列实现

最短路径算法

• Dijkstra算法：单源最短路径（非负权重）
• Bellman-Ford算法：单源最短路径（可处理负权重）
• Floyd-Warshall算法：所有顶点对之间的最短路径

有向图特有算法

• 拓扑排序：有向无环图的线性排序
• 强连通分量：Kosaraju算法、Tarjan算法

无向图特有算法

• 最小生成树：Kruskal算法、Prim算法
• 连通性检测：并查集

性能优化建议

1. 使用泛型：让图结构更灵活，支持不同类型的顶点
2. 权重边：可以扩展边的数据结构，存储权重信息
3. 线程安全：多线程环境下使用ConcurrentHashMap
4. 内存优化：大规模图可以考虑使用位图或压缩存储

总结

有向图和无向图是图论的基础，掌握它们的Java实现对于解决复杂的网络问题至关重要。选择合适的图类型和数据结构，能够让算法更高效：

• 对称关系用无向图（社交、网络拓扑）
• 非对称关系用有向图（依赖、关注、链接）
• 稀疏图用邻接表
• 稠密图用邻接矩阵

希望本文能帮助你深入理解图的概念和Java实现，为学习更高级的图算法打下坚实基础！