在有向图中找到两个节点之间的所有路径

本文介绍了在有向图中找到两个节点之间的所有路径的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

大家好，我试图找到有向图中两个节点之间的所有路径，这里是我的代码，但它没有正常工作..任何人都可以帮我解决它 谢谢提前。

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 .