testGraph
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace DepthFirstSearch { public class DepthFirstSearch { private bool[] marked; // marked[v] = is there an s-v path? private int count; // number of vertices connected to s /** * Computes the vertices in graph {@code G} that are * connected to the source vertex {@code s}. * @param G the graph * @param s the source vertex * @throws IllegalArgumentException unless {@code 0 <= s < V} */ public DepthFirstSearch(Graph G, int s) { marked = new bool[G.V]; G.validateVertex(s); dfs(G, s); } public DepthFirstSearch(Graph G) { marked = new bool[G.V]; } // depth first search from v public void dfs(Graph G, int v) { count++; marked[v] = true; Console.Write(v + " "); foreach (int w in G.adjVerticles(v)) { if (!marked[w]) { dfs(G, w); } } } public void unmarkAll() { for(int i=0; i<marked.Length;i++) { marked[i] = false; } } // is some Verticle is? public bool isVertex(Graph G, int v,int searchedVertex) { bool r = false; count++; marked[v] = true; if (searchedVertex == v) { r = true; return r; } else { foreach (int w in G.adjVerticles(v)) { if (!marked[w]) { r=isVertex(G, w, searchedVertex); return r; } } return r; } } } } |
Graph.cs
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace DepthFirstSearch { using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Collections; using System.IO; public class Graph { // private static final String NEWLINE = System.getProperty("line.separator"); public int V { get; set; } public int E { get; set; } public Bag<int>[] adj { get; set; } /** * Initializes an empty graph with {@code V} vertices and 0 edges. * param V the number of vertices * * @param V number of vertices * @throws IllegalArgumentException if {@code V < 0} */ public Graph(int V) { if (V < 0) throw new ArgumentException("Number of vertices must be nonnegative"); this.V = V; this.E = 0; adj = new Bag<int>[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<int>(); } } /** * Initializes a graph from the specified input stream. * The format is the number of vertices <em>V</em>, * followed by the number of edges <em>E</em>, * followed by <em>E</em> pairs of vertices, with each entry separated by whitespace. * * @param in the input stream * @throws IllegalArgumentException if the endpoints of any edge are not in prescribed range * @throws IllegalArgumentException if the number of vertices or edges is negative * @throws IllegalArgumentException if the input stream is in the wrong format */ public Graph(string filepath) { try { 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>(); } 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 { // for (int j = 0; j < E; j++) // { 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()); }; } // throw an IllegalArgumentException unless {@code 0 <= v < V} public void validateVertex(int v) { if (v < 0 || v >= V) throw new ArgumentException("vertex " + v + " is not between 0 and " + (V - 1)); } /** * Adds the undirected edge v-w to this graph. * * @param v one vertex in the edge * @param w the other vertex in the edge * @throws IllegalArgumentException unless both {@code 0 <= v < V} and {@code 0 <= w < V} */ public void addEdge(int v, int w) { validateVertex(v); validateVertex(w); E++; adj[v].push(w); adj[w].push(v); } /** * Returns the vertices adjacent to vertex {@code v}. * * @param v the vertex * @return the vertices adjacent to vertex {@code v}, as an iterable * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public IEnumerable<int> adjVerticles(int v) { validateVertex(v); return adj[v]; } /** * Returns the degree of vertex {@code v}. * * @param v the vertex * @return the degree of vertex {@code v} * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public int degree(int v) { validateVertex(v); return adj[v].size(); } /** * Returns a string representation of this graph. * * @return the number of vertices <em>V</em>, followed by the number of edges <em>E</em>, * followed by the <em>V</em> adjacency lists */ public String toString() { StringBuilder s = new StringBuilder(); s.Append(V + " vertices, " + E + " edges " + "\n"); for (int v = 0; v < V; v++) { s.Append(v + ": "); foreach (int w in adj[v]) { s.Append(w + " "); } s.Append("\n"); } return s.ToString(); } } } |
Bag.cs
|
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 DepthFirstSearch { 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; } } } } |
Test.cs
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace DepthFirstSearch { class Program { static void Main(string[] args) { Graph g = new Graph("tinyG.txt"); Console.WriteLine(g.toString()); Console.WriteLine("Which verticles are marked?"); DepthFirstSearch dfs = new DepthFirstSearch(g); dfs.dfs(g,0); Console.WriteLine(); dfs.dfs(g, 7); Console.WriteLine(); dfs.dfs(g, 9); Console.WriteLine(); dfs.unmarkAll(); Console.WriteLine("Is verticle 12 in graph?"); if (dfs.isVertex(g, 9, 12)) Console.WriteLine("Yes"); else Console.WriteLine("No"); Console.Read(); } } } |