如何使用Java实现图的深度优先搜索和拓扑排序？

用户1289394

发布于 2024-05-10 17:17:46

580

发布于 2024-05-10 17:17:46

实现图的深度优先搜索（Depth-First Search, DFS）和拓扑排序是图论中重要的算法。在Java中，我们可以使用邻接表或邻接矩阵表示图，并利用递归或栈来实现深度优先搜索算法。下面将详细介绍如何使用Java实现图的深度优先搜索和拓扑排序算法。

一、图的表示方法

在Java中，我们可以使用邻接表或邻接矩阵来表示图。邻接表更为常用，它使用一个数组存储顶点，并使用链表或ArrayList等数据结构存储每个顶点的邻接点信息。具体实现如下：

class Graph {
    private int vertexCount; // 图中顶点的数量
    private LinkedList<Integer>[] adjacencyList; // 邻接表

    public Graph(int vertexCount) {
        this.vertexCount = vertexCount;
        adjacencyList = new LinkedList[vertexCount];
        for (int i = 0; i < vertexCount; ++i) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int startVertex, int endVertex) {
        adjacencyList[startVertex].add(endVertex);
    }

    // ...
}

二、图的深度优先搜索（DFS）

深度优先搜索是一种常用的图遍历算法，其基本思想是从起始顶点开始，递归地访问与当前顶点相邻的未访问顶点，直到到达没有未访问邻接点的顶点。下面是使用递归实现的深度优先搜索算法：

class Graph {
    // ...

    private void dfsRecursiveUtil(int startVertex, boolean[] visited) {
        visited[startVertex] = true;
        System.out.print(startVertex + " ");

        for (Integer adjVertex : adjacencyList[startVertex]) {
            if (!visited[adjVertex]) {
                dfsRecursiveUtil(adjVertex, visited);
            }
        }
    }

    public void dfsRecursive(int startVertex) {
        boolean[] visited = new boolean[vertexCount];
        dfsRecursiveUtil(startVertex, visited);
    }

    // ...
}

使用以上代码，我们可以通过调用dfsRecursive(startVertex)方法实现深度优先搜索。其中，startVertex表示起始顶点的索引。

三、图的拓扑排序

拓扑排序是对有向无环图（DAG）中所有顶点进行线性排序的过程。在拓扑排序结果中，如果存在边(u, v)，则u在排序结果中出现在v之前。下面使用深度优先搜索实现图的拓扑排序：

class Graph {
    // ...

    private void topologicalSortUtil(int vertex, boolean[] visited, Stack<Integer> stack) {
        visited[vertex] = true;

        for (Integer adjVertex : adjacencyList[vertex]) {
            if (!visited[adjVertex]) {
                topologicalSortUtil(adjVertex, visited, stack);
            }
        }

        stack.push(vertex);
    }

    public void topologicalSort() {
        boolean[] visited = new boolean[vertexCount];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < vertexCount; ++i) {
            if (!visited[i]) {
                topologicalSortUtil(i, visited, stack);
            }
        }

        System.out.print("拓扑排序结果：");
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
        System.out.println();
    }

    // ...
}

使用以上代码，我们可以通过调用topologicalSort()方法实现图的拓扑排序。

四、完整示例

下面是一个完整的示例，演示了如何使用Java实现图的深度优先搜索和拓扑排序：

import java.util.LinkedList;
import java.util.Stack;

class Graph {
    private int vertexCount; // 图中顶点的数量
    private LinkedList<Integer>[] adjacencyList; // 邻接表

    public Graph(int vertexCount) {
        this.vertexCount = vertexCount;
        adjacencyList = new LinkedList[vertexCount];
        for (int i = 0; i < vertexCount; ++i) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int startVertex, int endVertex) {
        adjacencyList[startVertex].add(endVertex);
    }

    private void dfsRecursiveUtil(int startVertex, boolean[] visited) {
        visited[startVertex] = true;
        System.out.print(startVertex + " ");

        for (Integer adjVertex : adjacencyList[startVertex]) {
            if (!visited[adjVertex]) {
                dfsRecursiveUtil(adjVertex, visited);
            }
        }
    }

    public void dfsRecursive(int startVertex) {
        boolean[] visited = new boolean[vertexCount];
        dfsRecursiveUtil(startVertex, visited);
        System.out.println();
    }

    private void topologicalSortUtil(int vertex, boolean[] visited, Stack<Integer> stack) {
        visited[vertex] = true;

        for (Integer adjVertex : adjacencyList[vertex]) {
            if (!visited[adjVertex]) {
                topologicalSortUtil(adjVertex, visited, stack);
            }
        }

        stack.push(vertex);
    }

    public void topologicalSort() {
        boolean[] visited = new boolean[vertexCount];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < vertexCount; ++i) {
            if (!visited[i]) {
                topologicalSortUtil(i, visited, stack);
            }
        }

        System.out.print("拓扑排序结果：");
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(5, 2);
        graph.addEdge(5, 0);
        graph.addEdge(4, 0);
        graph.addEdge(4, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);

        System.out.print("深度优先搜索结果：");
        graph.dfsRecursive(5);

        graph.topologicalSort();
    }
}

以上示例创建了一个有向图，进行了深度优先搜索，并输出了拓扑排序结果。你可以根据需要修改图的结构和调用方法来测试不同的图。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2024-05-05，如有侵权请联系 cloudcommunity@tencent.com 删除

排序