使用深度优先搜索查找指定节点的唯一路由数量 [英] Find number of unique routes to specific node using Depth First Search
本文介绍了使用深度优先搜索查找指定节点的唯一路由数量的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我有一个顶点为123456的有向图。使用深度优先搜索，如果我希望能够从1-4找到唯一路线的数量（例如），我该如何去做呢？这是我目前的DFS。
private final Map< Character，Node> mNodes;
private final List< Edge> mEdges;
私人列表< Node> mVisited = new ArrayList<>（）;
int重量;
int numberOfPaths;
public DepthFirstSearch（图形图表）{
mNodes = graph.getNodes（）;
mEdges = new ArrayList<>（graph.getEdges（））;
for（Node node：mNodes.values（））{
node.setVisited（false）;
}
}
public void depthFirstSearch（Node source）{
source.setVisited（true）;
列表< Edge> neighbours = source.getNeighbouringEdges（mEdges）;
for（Edge edge：neighbors）{
System.out.println（edge.getFrom（）。getName（）+ - + edge.getTo（）。getName（））;
if（！edge.getTo（）。isVisited（））{
mVisited.add（edge.getTo（））;
weight + = edge.getWeight（）;
depthFirstSearch（edge.getTo（））;
DAG （
以下是一些与此主题相关的问题：
基本上，这个想法是得到一个拓扑排序，然后将从目标节点开始的节点向后迭代到源节点，计算该节点有多少路径。
由于数组没有循环和节点s是拓扑排序的，当您访问一个节点时，可以从该节点到达的所有节点都会在排序中出现，并且已经被访问。因此，从一个节点到目标的路径数量是与它相邻的节点数量的总和。
模型：
class Graph
{
private List< Node>节点;
私人列表< Edge>边缘;
public Graph（）{
nodes = new ArrayList<>（）;
edges = new ArrayList<>（）;
}
public List< Node> getNodes（）{return nodes; }
public List< Edge> getEdges（）{返回边; }
public void addNode（Node node）{nodes.add（node）; }
public void addEdge（Edge edge）{
edges.add（edge）;
edge.getFrom（）。addEdge（edge）;
edge.getTo（）。addEdge（edge）;
}
}
class Node
{
private List< Edge>支出，收入;
public Node（）{
outgoings = new ArrayList<>（）;
incomings = new ArrayList<>（）;
}
public List< Edge> getOutgoings（）{return outgoings; }
public List< Edge> getIncomings（）{return incomings; }
$ b public void addEdge（Edge edge）{
if（edge.getFrom（）== this）outgoings.add（edge）;
if（edge.getTo（）== this）incomings.add（edge）;
}
}
类边缘
{
私人节点从，到;
public Edge（Node from，Node to）{
this.from = from;
this.to = to;
}
public Node getFrom（）{return from; }
public Node getTo（）{return to;算法：
$ b pre> static int countPaths（图形图形，节点源，节点目标）
{
List< Node> nodes = topologicalSort（graph）;
int [] counts = new int [nodes.size（）];
int srcIndex = nodes.indexOf（source）;
int tgtIndex = nodes.indexOf（target）;
counts [tgtIndex] = 1;
$ b $ for（int i = tgtIndex; i> = srcIndex; i--）{
for（Edge edge：nodes.get（i）.getOutgoings（））
counts [i] + = counts [nodes.indexOf（edge.getTo（））];
}
返回计数[srcIndex];
}
static List< Node> topologicalSort（图g）
{
List< Node> result = new ArrayList<>（）;
Set< Node> visited = new HashSet<>（）;
Set< Node> expanded = new HashSet<>（）; （节点node：g.getNodes（））
explore（node，g，result，visited，expanded）;
返回结果;
$ b static void explore（节点node，graph g，List< Node>排序，Set< Node> visited，Set< Node>展开）{
if（visited）包含（节点））{
if（expanded.contains（node））return;
抛出新的IllegalArgumentException（图包含一个循环。）;
}
visited.add（node）;
（Edge edge：node.getIncomings（））
explore（edge.getFrom（），g，ordered，visited，expanded）;
ordering.add（node）;
expanded.add（node）;
}
用法：
图g = new Graph（）;
节点a =新节点（）;
节点b =新节点（）;
节点c =新节点（）;
Node d = new Node（）;
Node e = new Node（）;
边缘ab =新边缘（a，b）;
边缘bc =新边缘（b，c）;
边缘cd =新边缘（c，d）;
边缘广告=新边缘（a，d）;
Edge ae =新边（a，e）;
Edge ed =新Edge（e，d）;
Edge be =新Edge（b，e）;
Edge ec =新Edge（e，c）;
g.addNode（a）;
g.addNode（b）;
g.addNode（c）;
g.addNode（d）;
g.addNode（e）;
g.addEdge（ab）;
g.addEdge（bc）;
g.addEdge（cd）;
g.addEdge（ad）;
g.addEdge（ae）;
g.addEdge（ed）;
g.addEdge（be）;
g.addEdge（ec）;
int count = countPaths（g，a，d）;
//计数：6
//路径：
// 1。 A-> B-> C-> D
// 2。 A> D
// 3。 A> E-> D
// 4。 A-> B-> E-> C-> D
// 5。 A→B→E→D
// 6。 A-> E-> C-> D
但是，如果您想使用 BFS 来执行此操作，则可以尝试执行重设已访问节点的回溯：
static int countPaths（Graph graph，Node source，Node target）
{
Set< Node> visiteds = new HashSet<>（）;
返回BFS（来源，目标，受访者）;
}
static int BFS（Node current，Node target，Set< Node> visiteds）{
if（current == target）return 1;
else
{
int count = 0;
visiteds.add（current）; （边缘：current.getOutgoings（））
if（！visiteds.contains（edge.getTo（）））
count + = BFS（edge.getTo（））
），目标，访问）;
visiteds.remove（current）;
返回计数;
$ b然而，为了提高性能，你可以实现一些一种记忆法：
static int countPaths（Graph graph，Node source，Node target）
{
Set< Node> visiteds = new HashSet<>（）;
Map< Node，Integer> memoize = new HashMap<>（）;
for（节点node：graph.getNodes（））
memoize.put（node，-1）;
memoize.put（target，1）;
返回BFS（来源，受访者，记忆）;
}
static int BFS（Node current，Set< Node> visiteds，Map< Node，Integer> memoize）{
if（memoize.get（current）！= 1）返回memoize.get（current）;
else
{
int count = 0;
visiteds.add（current）; （边缘：current.getOutgoings（））
if（！visiteds.contains（edge.getTo（）））
count + = BFS（edge.getTo（））
），访问，记忆）;
visiteds.remove（current）;
memoize.put（current，count）;
返回计数;
}
}
I have a directed graph with vertexes 123456. Using a depth first search, if I wanted to be able to find the number of unique routes from 1-4 (for example), how would I go about doing it? Here is my current DFS.
private final Map<Character, Node> mNodes;
private final List<Edge> mEdges;
private List<Node> mVisited = new ArrayList<>();
int weight;
int numberOfPaths;
public DepthFirstSearch(Graph graph){
mNodes = graph.getNodes();
mEdges = new ArrayList<>(graph.getEdges());
for(Node node : mNodes.values()){
node.setVisited(false);
}
}
public void depthFirstSearch(Node source){
source.setVisited(true);
List<Edge> neighbours = source.getNeighbouringEdges(mEdges);
for(Edge edge : neighbours){
System.out.println(edge.getFrom().getName()+"-"+edge.getTo().getName());
if(!edge.getTo().isVisited()){
mVisited.add(edge.getTo());
weight += edge.getWeight();
depthFirstSearch(edge.getTo());
}
}
}
解决方案 Since cycles aren't allowed, you have actually a DAG (directed acyclid graph).
These are some questions related to this topic:
Basically, the idea is get a topological sort of the DAG, then iterate the nodes starting from the destination node backwards to the source node, calculating how many paths are from that node.
Since the array haven't cycles and the nodes are topological sorted, when you visit a node, all nodes that can be reached from that node appears latter in the sort and are already visited. So, the count of paths from an node to the target is the sum of the counts of the nodes that are adjacent to it.
Models:
class Graph
{
private List<Node> nodes;
private List<Edge> edges;
public Graph() {
nodes = new ArrayList<>();
edges = new ArrayList<>();
}
public List<Node> getNodes() { return nodes; }
public List<Edge> getEdges() { return edges; }
public void addNode(Node node) { nodes.add(node); }
public void addEdge(Edge edge) {
edges.add(edge);
edge.getFrom().addEdge(edge);
edge.getTo().addEdge(edge);
}
}
class Node
{
private List<Edge> outgoings, incomings;
public Node() {
outgoings = new ArrayList<>();
incomings = new ArrayList<>();
}
public List<Edge> getOutgoings() { return outgoings; }
public List<Edge> getIncomings() { return incomings; }
public void addEdge(Edge edge) {
if (edge.getFrom() == this) outgoings.add(edge);
if (edge.getTo() == this) incomings.add(edge);
}
}
class Edge
{
private Node from, to;
public Edge(Node from, Node to) {
this.from = from;
this.to = to;
}
public Node getFrom() { return from; }
public Node getTo() { return to; }
}
Algorithm:
static int countPaths(Graph graph, Node source, Node target)
{
List<Node> nodes = topologicalSort(graph);
int[] counts = new int[nodes.size()];
int srcIndex = nodes.indexOf(source);
int tgtIndex = nodes.indexOf(target);
counts[tgtIndex] = 1;
for (int i = tgtIndex; i >= srcIndex; i--) {
for (Edge edge : nodes.get(i).getOutgoings())
counts[i] += counts[nodes.indexOf(edge.getTo())];
}
return counts[srcIndex];
}
static List<Node> topologicalSort(Graph g)
{
List<Node> result = new ArrayList<>();
Set<Node> visited = new HashSet<>();
Set<Node> expanded = new HashSet<>();
for (Node node: g.getNodes())
explore(node, g, result, visited, expanded);
return result;
}
static void explore(Node node, Graph g, List<Node> ordering, Set<Node> visited, Set<Node> expanded) {
if (visited.contains(node)) {
if (expanded.contains(node)) return;
throw new IllegalArgumentException("Graph contains a cycle.");
}
visited.add(node);
for (Edge edge: node.getIncomings())
explore(edge.getFrom(), g, ordering, visited, expanded);
ordering.add(node);
expanded.add(node);
}
Usage:
Graph g = new Graph();
Node a = new Node();
Node b = new Node();
Node c = new Node();
Node d = new Node();
Node e = new Node();
Edge ab = new Edge(a, b);
Edge bc = new Edge(b, c);
Edge cd = new Edge(c, d);
Edge ad = new Edge(a, d);
Edge ae = new Edge(a, e);
Edge ed = new Edge(e, d);
Edge be = new Edge(b, e);
Edge ec = new Edge(e, c);
g.addNode(a);
g.addNode(b);
g.addNode(c);
g.addNode(d);
g.addNode(e);
g.addEdge(ab);
g.addEdge(bc);
g.addEdge(cd);
g.addEdge(ad);
g.addEdge(ae);
g.addEdge(ed);
g.addEdge(be);
g.addEdge(ec);
int count = countPaths(g, a, d);
//count: 6
// Paths:
//1. A->B->C->D
//2. A->D
//3. A->E->D
//4. A->B->E->C->D
//5. A->B->E->D
//6. A->E->C->D
But, if you want to do it using a BFS, you can try doing a backtrack resetting the visited nodes:
static int countPaths(Graph graph, Node source, Node target)
{
Set<Node> visiteds = new HashSet<>();
return BFS(source, target, visiteds);
}
static int BFS(Node current, Node target, Set<Node> visiteds) {
if (current == target) return 1;
else
{
int count = 0;
visiteds.add(current);
for (Edge edge : current.getOutgoings())
if (!visiteds.contains(edge.getTo()))
count += BFS(edge.getTo(), target, visiteds);
visiteds.remove(current);
return count;
}
}
However, to increase the performance, you can implement some kind of memoization:
static int countPaths(Graph graph, Node source, Node target)
{
Set<Node> visiteds = new HashSet<>();
Map<Node, Integer> memoize = new HashMap<>();
for (Node node : graph.getNodes())
memoize.put(node, -1);
memoize.put(target, 1);
return BFS(source, visiteds, memoize);
}
static int BFS(Node current, Set<Node> visiteds, Map<Node, Integer> memoize) {
if (memoize.get(current) != -1) return memoize.get(current);
else
{
int count = 0;
visiteds.add(current);
for (Edge edge : current.getOutgoings())
if (!visiteds.contains(edge.getTo()))
count += BFS(edge.getTo(), visiteds, memoize);
visiteds.remove(current);
memoize.put(current, count);
return count;
}
}
这篇关于使用深度优先搜索查找指定节点的唯一路由数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
