如何在间接图中列出从一个节点到另一个节点的所有路径?
How to list all paths from a node to another in a indirect graph?
我有一个图表,其节点结构如下:
Class Node:
int source;
int next;
所以,我有以下节点:[(1,2), (2,3), (3,4), (1,4)]
我想列出从 1 到 3 的所有可能路径,它将列出:[[(1,2),(2,3)],[(1,4),(4,3)].
我正在尝试使用这段代码,但我遗漏了一些东西:
public List<Node> getNodeNeighbors(Node n) {
List<Node> filteredNodes = new ArrayList<Node>();
List<Node> allNodes = (List<Node>) nodesRepository.findAll();
for (Node node: allNodes) {
if (node.source == n.next) {
filteredNodes.add(node);
}
}
return filteredNodes;
}
public List<Node> bfs(Node n, String destinationNodeNumber, List<Node> path) {
visitedX.add(n); //visitedX is a global List to control visited nodes
path.add(n); //local path to be listed
List<Node> neighbors = getNodeNeighbors(n); //function to get node neighbors
if (n.next.equals(destinationNodeNumber)) {
allPaths.add(paths); //all paths to be listed
path.remove(n);
}
for (Node nNode: neighbors) {
if(!visitedX.contains(nNode)) {
bfs(nNode, destinationNodeNumber, path);
}
}
return null;
}
你的代码有很多缺陷:
- 您的 class
Node
的名称具有误导性:Edge
会是一个更好的名称,
- 方法
getNodeNeighbors
只考虑每条边的一个方向
- 字段
aCompany
和 anotherCompany
是什么?我假设你的意思是 source
和 next
?
- 什么是 class
Contract
?
destinationNodeNumber
是一个String
;它应该是 int
.
visitedX
设置防止两条路径使用同一条边;您只需要确保边缘不会出现超过一次 在单个路径中 .
- 你实际上实现了 DFS,而不是 BFS
- 你总是将相同的
path
添加到 allPaths
;你应该复印一份。
这是一个class Edge
:
public class Edge {
final int source;
final int next;
Edge(int source, int next) {
this.source = source;
this.next = next;
}
@Override
public String toString() {
return "(" + source + "," + next + ')';
}
}
然后class Graph
包含搜索算法:
public class Graph {
private final Iterable<Edge> allNodes;
public Graph(Iterable<Edge> allNodes) {
this.allNodes = allNodes;
}
public List<Edge> edgesFrom(int vertex) {
List<Edge> filteredNodes = new ArrayList<Edge>();
for (Edge node : allNodes) {
if (node.source == vertex || node.next == vertex) {
filteredNodes.add(node);
}
}
return filteredNodes;
}
public List<List<Edge>> allPaths(int source, int dest) {
List<Edge> path = new ArrayList<>();
List<List<Edge>> allPaths = new ArrayList<>();
for (Edge n: edgesFrom(source)) {
searchPaths(n, source, dest, path, allPaths);
}
return allPaths;
}
private void searchPaths(Edge n, int source, int dest, List<Edge> path,
List<List<Edge>> allPaths) {
path.add(n); //local path to be listed
int next = n.source == source ? n.next : n.source;
List<Edge> neighbors = edgesFrom(next); //function to get node neighbors
if (next == dest) {
allPaths.add(new ArrayList<>(path)); //all paths to be listed
}
for (Edge nNode : neighbors) {
if (!path.contains(nNode)) {
searchPaths(nNode, next, dest, path, allPaths);
}
}
path.remove(n);
}
}
下面是使用这些 classes 的示例:
Graph graph = new Graph(Arrays.asList(
new Edge(1,2), new Edge(2,3), new Edge(3,4), new Edge(1,4)));
List<List<Edge>> allPaths = graph.allPaths(1,3);
for (List<Edge> path: allPaths) {
System.out.println(path);
}
我有一个图表,其节点结构如下:
Class Node:
int source;
int next;
所以,我有以下节点:[(1,2), (2,3), (3,4), (1,4)]
我想列出从 1 到 3 的所有可能路径,它将列出:[[(1,2),(2,3)],[(1,4),(4,3)].
我正在尝试使用这段代码,但我遗漏了一些东西:
public List<Node> getNodeNeighbors(Node n) {
List<Node> filteredNodes = new ArrayList<Node>();
List<Node> allNodes = (List<Node>) nodesRepository.findAll();
for (Node node: allNodes) {
if (node.source == n.next) {
filteredNodes.add(node);
}
}
return filteredNodes;
}
public List<Node> bfs(Node n, String destinationNodeNumber, List<Node> path) {
visitedX.add(n); //visitedX is a global List to control visited nodes
path.add(n); //local path to be listed
List<Node> neighbors = getNodeNeighbors(n); //function to get node neighbors
if (n.next.equals(destinationNodeNumber)) {
allPaths.add(paths); //all paths to be listed
path.remove(n);
}
for (Node nNode: neighbors) {
if(!visitedX.contains(nNode)) {
bfs(nNode, destinationNodeNumber, path);
}
}
return null;
}
你的代码有很多缺陷:
- 您的 class
Node
的名称具有误导性:Edge
会是一个更好的名称, - 方法
getNodeNeighbors
只考虑每条边的一个方向 - 字段
aCompany
和anotherCompany
是什么?我假设你的意思是source
和next
? - 什么是 class
Contract
? destinationNodeNumber
是一个String
;它应该是int
.visitedX
设置防止两条路径使用同一条边;您只需要确保边缘不会出现超过一次 在单个路径中 .- 你实际上实现了 DFS,而不是 BFS
- 你总是将相同的
path
添加到allPaths
;你应该复印一份。
这是一个class Edge
:
public class Edge {
final int source;
final int next;
Edge(int source, int next) {
this.source = source;
this.next = next;
}
@Override
public String toString() {
return "(" + source + "," + next + ')';
}
}
然后class Graph
包含搜索算法:
public class Graph {
private final Iterable<Edge> allNodes;
public Graph(Iterable<Edge> allNodes) {
this.allNodes = allNodes;
}
public List<Edge> edgesFrom(int vertex) {
List<Edge> filteredNodes = new ArrayList<Edge>();
for (Edge node : allNodes) {
if (node.source == vertex || node.next == vertex) {
filteredNodes.add(node);
}
}
return filteredNodes;
}
public List<List<Edge>> allPaths(int source, int dest) {
List<Edge> path = new ArrayList<>();
List<List<Edge>> allPaths = new ArrayList<>();
for (Edge n: edgesFrom(source)) {
searchPaths(n, source, dest, path, allPaths);
}
return allPaths;
}
private void searchPaths(Edge n, int source, int dest, List<Edge> path,
List<List<Edge>> allPaths) {
path.add(n); //local path to be listed
int next = n.source == source ? n.next : n.source;
List<Edge> neighbors = edgesFrom(next); //function to get node neighbors
if (next == dest) {
allPaths.add(new ArrayList<>(path)); //all paths to be listed
}
for (Edge nNode : neighbors) {
if (!path.contains(nNode)) {
searchPaths(nNode, next, dest, path, allPaths);
}
}
path.remove(n);
}
}
下面是使用这些 classes 的示例:
Graph graph = new Graph(Arrays.asList(
new Edge(1,2), new Edge(2,3), new Edge(3,4), new Edge(1,4)));
List<List<Edge>> allPaths = graph.allPaths(1,3);
for (List<Edge> path: allPaths) {
System.out.println(path);
}