找出有向图中长度为 K 的路径数

javaobject oriented programmingprogramming更新于 2024/10/9 5:00:17

给定一个有向且无权重的图 G 和一个整数 K。您必须找出长度为 K 的图中路径数。此处的图采用邻接矩阵的形式。从顶点 i 到 j,如果存在一条边,则用 G[i][j]=1 表示,否则用 G[i][j]=0 表示。

输入

  • 由邻接矩阵表示的有向无权图

  • 整数 K,表示要找到的路径的长度

输出

长度为 K 的路径总数

情况 I K=3

输出

路径总数= 2

解释

在上图中,有 2 条长度为 3 的路径。它们是-

  • 0->1->2->3

  • 0->2->3->1

案例 II K=2

输出

总路径 = 6

解释

在上图中,有 2 条路径的长度为 3。它们是-

  • 0->1->2

  • 0->2->3

  • 1->2->3

  • 2->3->4

  • 3->4->1

  • 4->1->2

示例

import java.util.*;

public class Main {
   public static void main(String[] args) {
      int[][] G = {
         {0, 1, 1, 0},
         {0, 0, 1, 0},
         {0, 0, 0, 1},
         {0, 1, 0, 0}
      };
      int K = 3;
      List<List<Integer>> paths = fpath(G, K);
      
      System.out.println("Paths of length are");
      int count=0;
      for (List<Integer> path : paths) {
         count++;
         System.out.println(path);
      }
      System.out.println("Total number of paths "+count);
   }
   
   public static List<List<Integer>> fpath(int[][] G, int K) {
      List<List<Integer>> paths = new ArrayList<>();
      List<Integer> path = new ArrayList<>();
      boolean[] visited = new boolean[G.length];
      
      // 从每个顶点开始搜索
      for (int i = 0; i < G.length; i++) {
         dfs(G, i, K, path, visited, paths);
      }
      
      return paths;
   }
   
   private static void dfs(int[][] G, int vertex, int K, 
List<Integer> path, boolean[] visited, 
List<List<Integer>> paths) {
      visited[vertex] = true;
      path.add(vertex);
      
      if (K == 0) {
         paths.add(new ArrayList<>(path));
      } else {
         for (int n = 0; n < G.length; n++) {
            if (G[vertex][n] == 1 && !visited[n]) {
               dfs(G, n, K - 1, path, visited, paths);
            }
         }
      }
      
      visited[vertex] = false;
      path.remove(path.size() - 1);
   }
}

输出

Paths of length are
[0, 1, 2, 3]
[0, 2, 3, 1]
Total number of paths 2

解释

要查找长度等于 K 的路径,我们将使用 DFS(深度优先搜索)方法。有两个辅助函数 - fpath() 和 dfs()。

fpath() 函数

  • 在 fpath() 函数中,邻接矩阵 G 和 K 作为参数传递。它返回一个包含列表作为路径的列表。此外,还会打印长度为 K 的路径总数。

  • 初始化包含路径的列表列表,并初始化当前路径列表。创建一个布尔数组来标记访问过的顶点。为每个顶点调用 dfs() 方法并检查它是否包含长度为 K 的路径。

dfs() 函数

  • dfs() 函数用于执行深度优先搜索操作。它是一个递归函数。我们将传递图形、当前顶点、剩余长度 K、已访问路径、跟踪已访问顶点的已访问布尔数组以及"paths",后者是包含用于存储路径的路径列表的列表。

  • 在给定的 dfs() 函数中,我们将顶点标记为已访问并添加到已访问路径。现在访问了相邻顶点。如果未访问相邻顶点,则使用新顶点和剩余长度 K-1 递归调用 dfs() 函数。

  • 如果 K 的值 = 0(这是我们的基本情况),则将当前访问的路径添加到"paths"。否则,如果存在从顶点到邻居的路径并且邻居未被访问,则递归调用该函数。

  • 访问完所有邻居后,该顶点被标记为未访问并从当前路径访问列表中删除。这也称为回溯。


相关文章


有用资源