Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- bool DepthFirstSearch(int startIndex, int endIndex)
- {
- //Assert whether the adjacency matrix exists and is not NULL
- assert(m_adjMatrix != NULL);
- //Assert whether the vertices visited exists and is not NULL
- assert(m_vertVisits != NULL);
- //Begin the traversal at the starting index
- m_vertVisits[startIndex] = 1;
- //Print the value at the start index
- cout << m_vertices[startIndex].GetNode();
- //Declare a stack for searching
- queue<int> searchQueue;
- //Declare and initialize a starting vertex point to 0
- int vert1 = 0;
- //Push start index into stack
- searchQueue.push(startIndex);
- //Loop while stack is not empty
- while (searchQueue.empty() != true)
- {
- //Assign end point vertex to the next unvisited vertex - use getNextUnvisitedVertex method
- int vert2 = getNextUnvisitedVertex(vert1);
- //If vertex is -1 pop from stack
- if (vert1 == endIndex)
- {
- getNextUnvisitedVertex(vert1);
- }
- //If vertex is not -1
- if ((vert1) != -1)
- {
- //Set visited vertex to 1
- m_vertVisits[vert1] = 1;
- //Print the value of the current node visited
- cout << m_vertices[vert1].GetNode();
- //Push vertex index into stack
- searchQueue.push(vert1);
- }
- //If vertex reach end point
- if (vert1 == endIndex)
- {
- //Use memset to reset vertices visited to NULL
- memset(m_vertVisits, 0, m_maxVerts);
- //Return true
- return true;
- }
- else
- {
- //Use memset to reset vertices visited to NULL
- memset(m_vertVisits, 0, m_maxVerts);
- //Return false
- return false;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement