Возьмем за основу алгоритм DFS для орграфов. И напишем поиск путей из одной вершины в другую. Конечный вариант будет выглядеть примерно так…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Has path to ? Console.WriteLine("Has path from 0 to 11 vertex? " + d.HasPathToDFS(d, 0, 11)); // This is the path ? Console.WriteLine("This is the path...?"); Stack<int> path = new Stack<int>(); d.GetPathToDFS(d, 0, 11, ref path); if (path.Count != 0) { foreach (int i in path) Console.WriteLine(" > " + i.ToString()); } else Console.WriteLine("no path..."); |
Напишем небольшой класс для поиска путей, он будет выглядеть примерно так…
Самый главный метод тут Dfs. Что мы делаем? Отмечаем вершину, проходим по смежным вершинам и отмечаем ориентированные ребра в специальном массиве, который позже позволит построить нам путь в методе GetPathTo. Мы как бы разматываем клубок с конца. И складываем вершины пути в стэк, получая необходимый путь.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Digraph { class DepthFirstDirectedPathes { private Boolean[] marked; private int[] edgeTo; private int s; public DepthFirstDirectedPathes(Digraph G, int s) { marked = new Boolean[G.GetVertices()]; edgeTo = new int[G.GetVertices()]; ValidateVertex(s); this.s = s; Dfs(G,s); } // --- dfs and pathes private void Dfs(Digraph G, int v) { marked[v] = true; foreach (int w in G.GetAdj(v)) { if (!marked[w]) { edgeTo[w] = v; Dfs(G, w); } } } // ---GetPathTo public void GetPathTo(int v, ref Stack<int> path) { ValidateVertex(v); if (!marked[v]) return; // Stack<int> path = new Stack<int>(); for (int x = v; x != s; x = edgeTo[x]) path.Push(x); path.Push(s); // return path; } // --- HasPathTo public Boolean HasPathTo(int v) { ValidateVertex(v); return marked[v]; } // --- validation private void ValidateVertex(int v) { int V = marked.Length; if (v < 0 || v >= V) { throw new ArgumentException("vertex " + v + " is not between 0 and " + "(V - 1)"); } } } } |
Используя этот класс, допишем в классе Digraph следующие методы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// --- Has Path to public Boolean HasPathToDFS(Digraph G, int s, int v) { DepthFirstDirectedPathes d = new DepthFirstDirectedPathes(G, s); return d.HasPathTo(v); } // --- Get Path To public void GetPathToDFS(Digraph G, int s, int v, ref Stack<int> path) { if (!HasPathToDFS(G,s,v)) return; DepthFirstDirectedPathes d = new DepthFirstDirectedPathes(G, s); d.GetPathTo(v, ref path); //return } |
Класс Digraph полностью
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 |
using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Digraph { class Digraph { private int V; // vertices private int E; // edges private Bag<int>[] adj; // adjency list of vertex v private int[] indegree; // indegree of vertex v // Initializes an empty digraph with V vertices. public Digraph(int V) { if (V < 0) throw new ArgumentException("Number of vertices in a Digraph must be nonnegative"); this.V = 0; this.E = 0; indegree = new int[V]; adj = new Bag<int>[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<int>(); } } // --- read Graph from file public Digraph(string filepath) { try { if (!File.Exists(filepath)) { throw new Exception("no file with such filepath"); } using (StreamReader sr = new StreamReader(filepath)) { int i = 0; while (sr.Peek() >= 0) { // reading number of verticles if (i == 0) { V = Convert.ToInt32(sr.ReadLine()); adj = new Bag<int>[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<int>(); } indegree = new int[V]; i++; } // reading number of edges else if (i == 1) { E = Convert.ToInt32(sr.ReadLine()); if (E < 0) throw new ArgumentException("number of edges in a Graph must be nonnegative"); i++; } else { string s = sr.ReadLine(); Char delimiter = ' '; String[] substrings = s.Split(delimiter); int v = Convert.ToInt32(substrings[0]); int w = Convert.ToInt32(substrings[1]); ValidateVertex(v); ValidateVertex(w); AddEdge(v, w); } } } } catch (Exception e) { Console.WriteLine("The process failed: {0}", e.ToString()); }; } // --- vertices public int GetVertices() { return V; } // --- edges public int GetEdges() { return E; } // --- Validation... private void ValidateVertex(int v) { if (v < 0 || v >= V) { throw new ArgumentException("vertex " + v + " is not between 0 and " + "(V - 1)"); } } // --- Adds the directed edge v→w to this digraph. public void AddEdge(int v, int w) { ValidateVertex(v); ValidateVertex(w); adj[v].Push(w); indegree[w]++; E++; } // --- Adjacent public Bag<int> GetAdj(int v) { ValidateVertex(v); return adj[v]; } // --- outDegree public int GetOutDegree(int v) { ValidateVertex(v); return adj[v].Size(); } // --- inDegree public int GetInDegree(int v) { ValidateVertex(v); return indegree[v]; } // --- reverseGraph public Digraph Reverse() { Digraph reverseGraph = new Digraph(V); for (int v = 0; v < V; v++) { foreach (int w in adj[v]) { reverseGraph.AddEdge(w, v); } } return reverseGraph; } // --- to string (not tested...) public override string ToString() { StringBuilder s = new StringBuilder(); s.Append(V + " vertices," + E + " edges " + "\n"); for (int v = 0; v < V; v++) { s.Append(v.ToString() + " "); foreach (int w in adj[v]) { s.Append(w + " "); } s.Append("\n"); } return s.ToString(); } // --- public Boolean IsReachible(Digraph G, int s, int v) { DirectedDFS dfs = new DirectedDFS(G, s); return dfs.IsMarked(v); } // --- Has Path to public Boolean HasPathToDFS(Digraph G, int s, int v) { DepthFirstDirectedPathes d = new DepthFirstDirectedPathes(G, s); return d.HasPathTo(v); } // --- Get Path To public void GetPathToDFS(Digraph G, int s, int v, ref Stack<int> path) { if (!HasPathToDFS(G,s,v)) return; DepthFirstDirectedPathes d = new DepthFirstDirectedPathes(G, s); d.GetPathTo(v, ref path); //return } } } |
Класс Bag
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Digraph { public class Bag<T> : IEnumerable<T> { Node<T> first; private int N; class Node<T> { public T item; public Node<T> next; } public bool IsEmpty() { return (first == null) || (N == 0); } public int Size() { return N; } public void Push(T item) { // adding to the begining Node<T> oldfirst = first; first = new Node<T>(); first.item = item; first.next = oldfirst; N++; } /* // no pop in stack method public T pop() { T item = first.item; first = first.next; N--; return item; } */ System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); } public IEnumerator<T> GetEnumerator() { var node = first; while (node != null) { yield return node.item; node = node.next; } } } } |
Пример применения
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Digraph { class Program { static void Main(string[] args) { Digraph d = new Digraph("tinyDG.txt"); //how much vertices? Console.WriteLine("Vertices: " + d.GetVertices()); //how much edges? Console.WriteLine("Edges: " + d.GetEdges()); // indegree Console.WriteLine("InDegree for 0 vertice: " + d.GetInDegree(0)); // outdegree Console.WriteLine("OutDegree for 0 vertice: " + d.GetInDegree(0)); // is v reachible from s ? Console.WriteLine("is 1 reachible from 0: " + d.IsReachible(d, 0, 1)); // True Console.WriteLine("is 6 reachible from 0: " + d.IsReachible(d, 0, 1)); // False // Has path to ? Console.WriteLine("Has path from 0 to 11 vertex? " + d.HasPathToDFS(d, 0, 11)); // This is the path ? Console.WriteLine("This is the path...?"); Stack<int> path = new Stack<int>(); d.GetPathToDFS(d, 0, 11, ref path); if (path.Count != 0) { foreach (int i in path) Console.WriteLine(" > " + i.ToString()); } else Console.WriteLine("no path..."); // just describing the orGraph... toString() Console.WriteLine("ToString(): " + d.ToString()); Console.ReadLine(); } } } |