找出有向图中长度为 K 的路径数
给定一个有向且无权重的图 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"。否则,如果存在从顶点到邻居的路径并且邻居未被访问,则递归调用该函数。
访问完所有邻居后,该顶点被标记为未访问并从当前路径访问列表中删除。这也称为回溯。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/

