Advertisement
Guest User

Untitled

a guest
Mar 30th, 2015
242
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.64 KB | None | 0 0
  1. bool DepthFirstSearch(int startIndex, int endIndex)
  2. {
  3. //Assert whether the adjacency matrix exists and is not NULL
  4. assert(m_adjMatrix != NULL);
  5. //Assert whether the vertices visited exists and is not NULL
  6. assert(m_vertVisits != NULL);
  7. //Begin the traversal at the starting index
  8. m_vertVisits[startIndex] = 1;
  9. //Print the value at the start index
  10. cout << m_vertices[startIndex].GetNode();
  11. //Declare a stack for searching
  12. queue<int> searchQueue;
  13. //Declare and initialize a starting vertex point to 0
  14. int vert1 = 0;
  15.  
  16. //Push start index into stack
  17. searchQueue.push(startIndex);
  18.  
  19. //Loop while stack is not empty
  20. while (searchQueue.empty() != true)
  21. {
  22. //Assign end point vertex to the next unvisited vertex - use getNextUnvisitedVertex method
  23. int vert2 = getNextUnvisitedVertex(vert1);
  24. //If vertex is -1 pop from stack
  25. if (vert1 == endIndex)
  26. {
  27. getNextUnvisitedVertex(vert1);
  28. }
  29. //If vertex is not -1
  30. if ((vert1) != -1)
  31. {
  32. //Set visited vertex to 1
  33. m_vertVisits[vert1] = 1;
  34.  
  35. //Print the value of the current node visited
  36. cout << m_vertices[vert1].GetNode();
  37.  
  38. //Push vertex index into stack
  39. searchQueue.push(vert1);
  40.  
  41. }
  42.  
  43.  
  44. //If vertex reach end point
  45. if (vert1 == endIndex)
  46. {
  47. //Use memset to reset vertices visited to NULL
  48. memset(m_vertVisits, 0, m_maxVerts);
  49. //Return true
  50. return true;
  51. }
  52. else
  53. {
  54. //Use memset to reset vertices visited to NULL
  55. memset(m_vertVisits, 0, m_maxVerts);
  56. //Return false
  57. return false;
  58. }
  59.  
  60.  
  61. }
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement