在有向图中找到两个节点之间的所有路径 [英] finding all paths between two nodes in directed graph
本文介绍了在有向图中找到两个节点之间的所有路径的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
大家好,我试图找到有向图中两个节点之间的所有路径,这里是我的代码,但它没有正常工作..任何人都可以帮我解决它
谢谢提前。
hi all , i`m trying to find all paths between two nodes in directed graph here is my code BUT it didn`t work correctly .. could any one help me to fix it
thanks in advance.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
//using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Collections.Specialized;
using System.Collections;
namespace Direct_Graph
{
class Program
{
public class Digraph
{
private readonly int _v; //The number of vertices
private int _e; //The number of edges
private LinkedList<int>[] adj; //Use a LinkedList for the adjacency-list representation
//Create a new directed graph with V vertices
public Digraph(int V)
{
if (V < 0)
throw new Exception("Number of vertices in a Digraph must be nonnegative");
this._v = V;
this._e = 0;
//Create a new adjecency-list for each vertex
adj = new LinkedList<int>[V];
for (int v = 0; v < V; v++)
{
adj[v] = new LinkedList<int>();
}
}
//return the number of vertices
public int V()
{
return _v;
}
//return the number of edges
public int E()
{
return _e;
}
//Add an edge to the directed graph from v to w
public void AddEdge(int v, int w)
{
if (v < 0 || v >= _v)
throw new Exception("vertex " + v + " is not between 0 and " + (_v - 1));
if (w < 0 || w >= _v)
throw new Exception("vertex " + w + " is not between 0 and " + (_v - 1));
adj[v].AddFirst(w);
_e++;
}
/*
* Return the adjacency-list for vertex v, which
* are the vertices connected to v pointing from v
* */
public LinkedList<int> Adj(int v)
{
if (v < 0 || v >= _v)
throw new Exception();
return adj[v];
}
//Return the directed graph as a string
public String toString()
{
StringBuilder s = new StringBuilder();
String NEWLINE = Environment.NewLine;
//s.Append(_v + " vertices, " + _e + " edges " + NEWLINE);
for (int v = 0; v < _v; v++)
{
s.Append(String.Format("{0:d}: ", v));
foreach (int w in adj[v])
{
s.Append(String.Format("{0:d} ", w));
}
s.Append(NEWLINE);
}
return s.ToString();
}
}
public class Search
{
int START;
int END;
public void DepthFirstSearch(Digraph graph, LinkedList<int> visited)
{
// int v = visited.Last();
LinkedList<int> nodes = graph.Adj(visited.Last());
// examine adjacent nodes
foreach (int node in nodes)
{
if (visited.Contains(node))
continue;
if (node == END)
{
visited.AddFirst(node);
printPath(visited);
visited.RemoveLast();
break;
}
}
// in breadth-first, recursion needs to come after visiting adjacent nodes
foreach (int node in nodes)
{
if (visited.Contains(node) || node == END)
continue;
visited.AddLast(node);
DepthFirstSearch(graph, visited);
visited.RemoveLast();
}
}
public void printPath(LinkedList<int> visited)
{
foreach (int node in visited)
{
Console.Write(node);
Console.Write(" ");
}
Console.WriteLine();
}
}
static void Main(string[] args)
{
int START = 3;
int END = 8;
Digraph dg = new Digraph(30);
dg.AddEdge(3, 4);
dg.AddEdge(4, 8);
dg.AddEdge(4, 11);
dg.AddEdge(11, 14);
dg.AddEdge(11, 17);
dg.AddEdge(11, 8);
dg.AddEdge(14, 8);
dg.AddEdge(14, 17);
dg.AddEdge(14, 25);
dg.AddEdge(17, 22);
dg.AddEdge(17, 25);
dg.AddEdge(25, 8);
dg.AddEdge(22, 25);
LinkedList<int> visited = new LinkedList<int>();
visited.AddFirst(START);
Search s = new Search();
s.DepthFirstSearch(dg, visited);
s.printPath(visited);
}
}
}
推荐答案
Google:查找有向图中两个节点之间的所有路径 [ ^ ]
Google: finding all paths between two nodes in directed graph[^]
我已经修复了错误..谢谢大家试图帮助我。
i`ve fixed the error .. Thank you all for trying to help me .
这篇关于在有向图中找到两个节点之间的所有路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文