Конечный клиент тестирования будет выглядеть так… Для примера будем искать путь из 0 во 2 вершину.
Представление графа в текстовом файле
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
13 22 4 2 2 3 3 2 6 0 0 1 2 0 11 12 12 9 9 10 9 11 8 9 10 12 11 4 4 3 3 5 7 8 8 7 5 4 0 5 6 4 6 9 7 6 |
Обратите внимание, мы ищем путь из 0 в 2 в ориентированном графе. Метод DFS дает нам более длинный путь, а метод BFS кратчайший.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// --- BFS Console.WriteLine("--- BFS..."); // Haspath to Console.WriteLine("Has path from "+s+" to "+f+" vertex, DFS? " + d.IsPathToBFS(d, s, f)); // --- shortest distance path.Clear(); if (d.IsPathToBFS(d, s, f)) Console.WriteLine("Shortest distance: "+ d.GetShortestDistToBFS(d,s,f)); // --- Console.WriteLine("This is the path, DFS?"); d.GetShortestPathToBFS(d, s, f, ref path); if (path.Count != 0) { foreach (int i in path) Console.WriteLine(" > " + i.ToString()); } else Console.WriteLine("no path..."); |
Класс для поиска путей методом BreathFirstSearch
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Digraph { class BreadthFirstDirectedPaths { private bool[] marked; private int[] edgeTo; private int[] distTo; private static int INFINITY = int.MaxValue; // BFS from single source private void Bfs(Digraph G, int s) { Queue<int> q = new Queue<int>(); marked[s] = true; distTo[s] = 0; q.Enqueue(s); while (q.Count != 0) { int v = q.Dequeue(); foreach (int w in G.GetAdj(v)) { if (!marked[w]) { edgeTo[w] = v; distTo[w] = distTo[v] + 1; marked[w] = true; q.Enqueue(w); } } } } // BFS from multiple sources private void Bfs(Digraph G, IEnumerable<int> sources) { Queue<int> q = new Queue<int>(); foreach (int s in sources) { marked[s] = true; distTo[s] = 0; q.Enqueue(s); } while (q.Count != 0) { int v = q.Dequeue(); foreach (int w in G.GetAdj(v)) { if (!marked[w]) { edgeTo[w] = v; distTo[w] = distTo[v] + 1; marked[w] = true; q.Enqueue(w); } } } } // Is there a directed path from the source, IsPathTo public bool IsPathTo(int v) { ValidateVertex(v); return marked[v]; } // Returns the number of edges in a shortest path from the source public int GetShortestDistTo(int v) { ValidateVertex(v); return distTo[v]; } // Returns the shortest path public void GetShortestPathTo(int v, ref Stack<int> path) { if (!IsPathTo(v)) return; int x; for (x = v; distTo[x] != 0; x = edgeTo[x]) path.Push(x); path.Push(x); } // --- Computes the shortest path from {s} public BreadthFirstDirectedPaths(Digraph G, int s) { marked = new bool[G.GetVertices()]; distTo = new int[G.GetVertices()]; edgeTo = new int[G.GetVertices()]; ValidateVertex(s); Bfs(G, s); } // --- Computes the shortest path from any one of the source vertices in {@code sources} public BreadthFirstDirectedPaths(Digraph G, IEnumerable<int> sources) { marked = new bool[G.GetVertices()]; distTo = new int[G.GetVertices()]; edgeTo = new int[G.GetVertices()]; for (int v = 0; v < G.GetVertices(); v++) distTo[v] = INFINITY; ValidateVertices(sources); Bfs(G, sources); } // --- 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)"); } } // --- validation, many vertices private void ValidateVertices(IEnumerable<int> vertices) { if (vertices == null) { throw new ArgumentException("argument is null"); } int V = marked.Length; foreach (int v in vertices) { if (v < 0 || v >= V) throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1)); } } } } |
Класс ориентированного графа
|
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 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 |
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); } // --- HasPathToDFS public Boolean IsPathToDFS(Digraph G, int s, int v) { DepthFirstDirectedPathes d = new DepthFirstDirectedPathes(G, s); return d.IsPathTo(v); } // --- GetPathToDFS public void GetPathToDFS(Digraph G, int s, int v, ref Stack<int> path) { if (!IsPathToDFS(G,s,v)) return; DepthFirstDirectedPathes d = new DepthFirstDirectedPathes(G, s); d.GetPathTo(v, ref path); } // --- HasPathToBFS public Boolean IsPathToBFS(Digraph G, int s, int v) { BreadthFirstDirectedPaths d = new BreadthFirstDirectedPaths(G, s); return d.IsPathTo(v); } // --- GetShortestDistTo public int GetShortestDistToBFS(Digraph G, int s, int v) { if (!IsPathToBFS(G, s, v)) return -1; BreadthFirstDirectedPaths d = new BreadthFirstDirectedPaths(G, s); return d.GetShortestDistTo(v); } // --- GetShortestPathTo public void GetShortestPathToBFS(Digraph G, int s, int v, ref Stack<int> path) { if (!IsPathToBFS(G, s, v)) return; BreadthFirstDirectedPaths d = new BreadthFirstDirectedPaths(G, s); d.GetShortestPathTo(v, ref path); } } } |
Класс 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; } } } } |