Существует ли ориентированный путь из s в указанную вершину v в орграфе? Для этого будем использовать поиск в глубину и напишем класс DirectedDFS.
Для примера будем использовать граф tinyDG.txt
|
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 |
DirectedDFS
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Digraph { class DirectedDFS { private Boolean[] marked; // marked[v] = true iff v is reachable from source(s) private int Count; // number of vertices reachable from source(s) // --- constructor, from 1 source public DirectedDFS(Digraph G, int s) { marked = new Boolean[G.GetVertices()]; ValidateVertex(s); Dfs(G, s); } //--- constructor 2, from many sources... public DirectedDFS(Digraph G, IEnumerable<int> s) { marked = new Boolean[G.GetVertices()]; ValidateVertices(s); foreach(int v in s) if(!marked[v])Dfs(G, v); } // --- Depth first search private void Dfs(Digraph G, int s) { Count++; marked[s] = true; foreach (int w in G.GetAdj(s)) { if (!marked[w]) Dfs(G,w); } } // --- isMarked? public Boolean IsMarked(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)"); } } // --- validation private void ValidateVertices(IEnumerable<int> vertices) { 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)"); } } } } |
В классе Digraph допишем метод IsReachible
|
1 2 3 4 5 |
public Boolean IsReachible(Digraph G, int s, int v) { DirectedDFS dfs = new DirectedDFS(G,s); return dfs.IsMarked(v); } |
Полный код класса будет такой
|
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 |
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); } } } |
Пример применения
|
1 2 3 |
// 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 |
Полностью
|
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 |
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 // toString() Console.WriteLine("ToString(): " + d.ToString()); Console.ReadLine(); } } } |
Класс 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; } } } } |