Advertisement
sirjordan

Find and print shortest path by BFS in graph

Sep 30th, 2014
241
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.47 KB | None | 0 0
  1.     /// <summary>
  2.         /// 7. Find and print shortest path by BFS in graph
  3.         /// </summary>
  4.         /// <param name="g">Graph represented by matrix of succesors.</param>
  5.         /// <param name="startEdge">Edge to start BFS</param>
  6.         /// <param name="endEdge">Edge to be searched.</param>
  7.         private static void FindPathBFS(Graph g, int startEdge, int endEdge)
  8.         {
  9.             Queue<int> edges = new Queue<int>();
  10.             List<int> visitedEdges = new List<int>(startEdge);
  11.             edges.Enqueue(startEdge);
  12.             bool founded = false;
  13.  
  14.             while (edges.Count > 0 && !founded)
  15.             {
  16.                 int currentEdge = edges.Dequeue();
  17.                 visitedEdges.Add(currentEdge);
  18.                 if (endEdge == currentEdge)
  19.                 {
  20.                     Console.Write("Found: ");
  21.                     founded = true;
  22.                 }
  23.  
  24.                 IList<int> sucsesorsOfCurrentEdge = g.GetSuccessors(currentEdge);
  25.                 foreach (int sucsesor in sucsesorsOfCurrentEdge)
  26.                 {
  27.                     // Avoid the infite loop in oriented cycle graph
  28.                     if (!visitedEdges.Contains(sucsesor))
  29.                     {
  30.                         edges.Enqueue(sucsesor);
  31.                     }
  32.                 }
  33.             }
  34.  
  35.             if (founded)
  36.             {
  37.                 // Remove the last and mark it as the last one
  38.                 int lastElement = visitedEdges[visitedEdges.Count - 1];
  39.                 visitedEdges.RemoveAt(visitedEdges.Count - 1);
  40.  
  41.                 // Delete that nodes that has not direct connection to the last in the order of visit.
  42.                 for (int i = visitedEdges.Count - 1; i > 0; i--)
  43.                 {
  44.                     // If no relation to last
  45.                     if (!(g.GetSuccessors(visitedEdges[i]).Contains(lastElement)))
  46.                     {
  47.                         visitedEdges.RemoveAt(i);
  48.                     }
  49.                     else
  50.                     {
  51.                         lastElement = visitedEdges[i];
  52.                     }
  53.                 }
  54.  
  55.                 // Put back the founded just to show on the console;
  56.                 visitedEdges.Add(endEdge);
  57.                 foreach (var el in visitedEdges)
  58.                 {
  59.                     Console.Write(el + " ");
  60.                 }
  61.             }
  62.             else
  63.             {
  64.                 Console.WriteLine("Not founded!");
  65.             }
  66.         }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement