Java Program to Count All Possible Paths Between Two Vertices

2025年3月29日 | 阅读 4 分钟

图论中的一个重要问题是确定有向图中从一个顶点到另一个顶点的所有可能路径。它在路由、网络最优路径决策以及软件中的多种用途方面尤其有用。在本节中，我们将学习如何开发一个 Java 程序来计算有向图中两个节点之间的路径数量。

理解问题

现在，参考给定的有向图，我们必须计算两个特定顶点之间的路径数量。图最显著的特征是路径，它是顶点的一系列连接方式，其中每对连续顶点共享一条边。因此，在有向图中，每条边的方向都很重要，也就是说，如果不存在从顶点 A 到顶点 B 的有向边，您就不能移动。

方法

我们可以使用深度优先搜索 (DFS) 来解决这个问题，DFS 是一种用于遍历或搜索图数据结构的常用算法。DFS 很实用，因为它会探索一个顶点并继续探索其相邻顶点，然后再回溯以探索其他可能性。这使得 DFS 非常适合计算两个顶点之间的路径数量。

实现解决方案的步骤

图表示：关于图的表示，我们使用邻接表。在邻接表中，创建一个链表数组，其中链表的列表代表一个顶点，而该列表包含所有连接到链表所代表的顶点的顶点的地址。
深度优先搜索 (DFS)：在此方法 DFS 中，我们将从源顶点开始探索所有顶点，并在搜索目标顶点时继续探索相邻顶点。每次到达目的地时，我们都会将路径计数器加一，以指示所采取的路径数量。
基本情况和递归情况
- 基本情况：如果我们到达目的地顶点，这意味着我们已经找到了一条有效路径，因此我们将路径计数器加一。
- 递归情况：如果我们尚未到达目的地，我们将递归地访问所有相邻的顶点。
回溯：作为 DFS 的一部分，我们需要确保一旦一条路径被探索，我们就回溯以探索其他潜在路径。这确保了我们计算了两个顶点之间的所有可能路径。

Java Program to Count All Possible Paths Between Two Vertices

这是使用 DFS 计算两个顶点之间所有可能路径的完整 Java 实现

文件名：Graph.java

import java.util.*;
public class Graph {
    private int vertices; // Number of vertices in the graph
    private List<Integer>[] adjList; // Adjacency list to store the graph
    // Constructor to initialize the graph
    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjList[i] = new ArrayList<>();
        }
    }
    // Method to add an edge from vertex u to vertex v
    public void addEdge(int u, int v) {
        adjList[u].add(v); // Directed graph: Edge from u to v
    }
    // Method to count all possible paths from 'source' to 'destination'
    public int countAllPaths(int source, int destination) {
        boolean[] visited = new boolean[vertices]; // To keep track of visited vertices
        return dfs(source, destination, visited);
    }
    // Depth First Search (DFS) to count all paths from current to destination
    private int dfs(int current, int destination, boolean[] visited) {
        // Base case: If current vertex is the destination, we found a path
        if (current == destination) {
            return 1;
        }
        // Mark the current vertex as visited
        visited[current] = true;
        int pathCount = 0;
        // Explore all the adjacent vertices (neighbors) of the current vertex
        for (int neighbor : adjList[current]) {
            // If the neighbor has not been visited, explore further
            if (!visited[neighbor]) {
                pathCount += dfs(neighbor, destination, visited);
            }
        }
        // Backtrack: Unmark the current vertex to explore other paths
        visited[current] = false;
        return pathCount; // Return the number of paths from current to destination
    }
    public static void main(String[] args) {
        // Example usage
        Graph graph = new Graph(5); // Create a graph with 5 vertices
        // Add edges to the graph
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        // Count all possible paths from vertex 0 to vertex 4
        int source = 0;
        int destination = 4;
        int totalPaths = graph.countAllPaths(source, destination);
        System.out.println("Total number of paths from " + source + " to " + destination + ": " + totalPaths);
    }
}   

输出

 
Total number of paths from 0 to 4: 3

下一个主题JavaCC

Java Program to Count All Possible Paths Between Two Vertices

理解问题

方法

实现解决方案的步骤

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java Program to Count All Possible Paths Between Two Vertices

理解问题

方法

实现解决方案的步骤

相关帖子

What is Diamond Problem in Java

Types of Garbage Collector in Java

理解 Java 中的静态同步

Java Keystore

Binary to Gray Code Using Recursion in Java

在 Java 中反转二叉树

Java 中 ToIntFunction 接口及示例

Windows Programming Using Java

Java vs Kotlin

Java TreeMap 按值排序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器