Advertisement
vencinachev

Graph

Sep 10th, 2019
405
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.76 KB | None | 0 0
  1. class Graph<T>
  2.     {
  3.         private Dictionary<Node<T>, List<Node<T>>> adj;
  4.  
  5.         public Graph()
  6.         {
  7.             adj = new Dictionary<Node<T>, List<Node<T>>>();
  8.         }
  9.  
  10.         public void AddNode(Node<T> node)
  11.         {
  12.             this.adj[node] = new List<Node<T>>();
  13.         }
  14.  
  15.         public void AddNode(T value)
  16.         {
  17.             this.adj[new Node<T>(value)] = new List<Node<T>>();
  18.         }
  19.  
  20.         public void AddEdge(Node<T> source, Node<T> dest)
  21.         {
  22.             if (!adj.ContainsKey(source) || !adj.ContainsKey(dest))
  23.             {
  24.                 throw new ArgumentException("Nodes not existing!");
  25.             }
  26.             if (adj[source].Contains(dest))
  27.             {
  28.                 throw new Exception("Edge already exist!");
  29.             }
  30.             adj[source].Add(dest);
  31.         }
  32.  
  33.         public void RemoveEdge(Node<T> source, Node<T> dest)
  34.         {
  35.             if (!adj.ContainsKey(source) || !adj.ContainsKey(dest))
  36.             {
  37.                 throw new ArgumentException("Invalid nodes!");
  38.             }
  39.             adj[source].Remove(dest);
  40.         }
  41.  
  42.         public void BFS(Node<T> start)
  43.         {
  44.             if (!adj.ContainsKey(start))
  45.             {
  46.                 throw new ArgumentException("Start node not exists!");
  47.             }
  48.             List<Node<T>> visited = new List<Node<T>>();
  49.             Queue<Node<T>> queue = new Queue<Node<T>>();
  50.             queue.Enqueue(start);
  51.             visited.Add(start);
  52.             while (queue.Count != 0)
  53.             {  
  54.                 Node<T> current = queue.Dequeue();
  55.                 foreach (Node<T> node in adj[current])
  56.                 {
  57.                     if (!visited.Contains(node))
  58.                     {
  59.                         visited.Add(node);
  60.                         queue.Enqueue(node);
  61.                     }
  62.                 }
  63.                 Console.Write("{0} ", current);
  64.             }
  65.         }
  66.  
  67.         public void DFS(Node<T> start)
  68.         {
  69.             if (!adj.ContainsKey(start))
  70.             {
  71.                 throw new ArgumentException("Start node not exists!");
  72.             }
  73.             List<Node<T>> visited = new List<Node<T>>();
  74.             Stack<Node<T>> queue = new Stack<Node<T>>();
  75.             queue.Push(start);
  76.             visited.Add(start);
  77.             while (queue.Count != 0)
  78.             {  
  79.                 Node<T> current = queue.Pop();
  80.                 foreach (Node<T> node in adj[current])
  81.                 {
  82.                     if (!visited.Contains(node))
  83.                     {
  84.                         visited.Add(node);
  85.                         queue.Push(node);
  86.                     }
  87.                 }
  88.                 Console.Write("{0} ", current);
  89.             }
  90.         }
  91.  
  92.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement