document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. using System.Collections.Generic;
  2. using System.Linq;
  3. using Microsoft.VisualStudio.TestTools.UnitTesting;
  4.  
  5. namespace MyCodeSnippets.CodingInterview.Chapter4_Trees
  6. {
  7.     [TestClass]
  8.     public class Task_4_2_CheckIfNodesConnected
  9.     {
  10.         [TestMethod]
  11.         public void IsNodesConnectedTest()
  12.         {
  13.             var node1 = new DirectedGraphNode<int>(1);
  14.             var node2 = new DirectedGraphNode<int>(2);
  15.             var node3 = new DirectedGraphNode<int>(3);
  16.             var node4 = new DirectedGraphNode<int>(4);
  17.             var node5 = new DirectedGraphNode<int>(5);
  18.             var node6 = new DirectedGraphNode<int>(6);
  19.             var node7 = new DirectedGraphNode<int>(7);
  20.             var node8 = new DirectedGraphNode<int>(8);
  21.             var node9 = new DirectedGraphNode<int>(9);
  22.  
  23.             var graph = new List<DirectedGraphNode<int>>()
  24.             {
  25.                 node1, node2, node3, node4, node5, node6, node7, node8, node9
  26.             };
  27.  
  28.             node1.ConnectedNodes.Add(node2);
  29.             node1.ConnectedNodes.Add(node3);
  30.             node3.ConnectedNodes.Add(node5);
  31.             node5.ConnectedNodes.Add(node7);
  32.             node7.ConnectedNodes.Add(node9);
  33.             node5.ConnectedNodes.Add(node1);
  34.             node5.ConnectedNodes.Add(node3);
  35.             node4.ConnectedNodes.Add(node1);
  36.  
  37.             Assert.IsTrue(IsNodesConnected(node1, node3));
  38.            
  39.             CleanUpGraph(graph);
  40.  
  41.             Assert.IsTrue(IsNodesConnectedClassicBreadthFirstSearch(node1, node3));
  42.  
  43.             CleanUpGraph(graph);
  44.  
  45.             Assert.IsFalse(IsNodesConnected(node1, node4));
  46.            
  47.             CleanUpGraph(graph);
  48.  
  49.             Assert.IsFalse(IsNodesConnectedClassicBreadthFirstSearch(node1, node4));
  50.  
  51.             CleanUpGraph(graph);
  52.  
  53.             Assert.IsTrue(IsNodesConnected(node1, node9));
  54.  
  55.             CleanUpGraph(graph);
  56.  
  57.             Assert.IsTrue(IsNodesConnectedClassicBreadthFirstSearch(node1, node9));
  58.         }
  59.  
  60.         private static void CleanUpGraph(List<DirectedGraphNode<int>> graph)
  61.         {
  62.             foreach (var node in graph)
  63.             {
  64.                 node.IsVisited = false;
  65.             }
  66.         }
  67.  
  68.         public static bool IsNodesConnected<T>(DirectedGraphNode<T> nodeFrom, DirectedGraphNode<T> to)
  69.         {
  70.             if (nodeFrom == null || to == null)
  71.             {
  72.                 return false;
  73.             }
  74.  
  75.             if (nodeFrom == to)
  76.             {
  77.                 return true;
  78.             }
  79.  
  80.             foreach (var graphNode in nodeFrom.ConnectedNodes)
  81.             {
  82.                 if (graphNode.IsVisited)
  83.                 {
  84.                     continue;
  85.                 }
  86.  
  87.                 if (graphNode == to)
  88.                 {
  89.                     return true;
  90.                 }
  91.             }
  92.  
  93.             foreach (var graphNode in nodeFrom.ConnectedNodes)
  94.             {
  95.                 if (graphNode.IsVisited)
  96.                 {
  97.                     continue;
  98.                 }
  99.  
  100.                 graphNode.IsVisited = true;
  101.                 var result = IsNodesConnected<T>(graphNode, to);
  102.                 if (result)
  103.                 {
  104.                     return true;
  105.                     ;
  106.                 }
  107.             }
  108.  
  109.             return false;
  110.         }
  111.  
  112.         public static bool IsNodesConnectedClassicBreadthFirstSearch<T>(DirectedGraphNode<T> nodeFrom, DirectedGraphNode<T> to)
  113.         {
  114.             if (nodeFrom == null || to == null)
  115.             {
  116.                 return false;
  117.             }
  118.  
  119.             if (nodeFrom == to)
  120.             {
  121.                 return true;
  122.             }
  123.             var queue = new Queue<DirectedGraphNode<T>>();
  124.             queue.Enqueue(nodeFrom);
  125.  
  126.             while (queue.Any())
  127.             {
  128.                 var item = queue.Dequeue();
  129.                 if (item == to)
  130.                 {
  131.                     return true;
  132.                 }
  133.                 item.IsVisited = true;
  134.  
  135.                 foreach (var node in item.ConnectedNodes)
  136.                 {
  137.                     if (node.IsVisited)
  138.                     {
  139.                         continue;
  140.                     }
  141.  
  142.                     if (node == to)
  143.                     {
  144.                         return true;
  145.                     }
  146.                     queue.Enqueue(node);
  147.                 }
  148.             }
  149.  
  150.             return false;
  151.         }
  152.     }
  153.  
  154.     public class DirectedGraphNode<T>
  155.     {
  156.         public List<DirectedGraphNode<T>>  ConnectedNodes = new List<DirectedGraphNode<T>>();
  157.  
  158.         public T Data;
  159.  
  160.         public bool IsVisited = false;
  161.        
  162.         public DirectedGraphNode(T data)
  163.         {
  164.             Data = data;
  165.         }
  166.     }
  167. }
');