Advertisement
Guest User

Untitled

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