Skip to content

Instantly share code, notes, and snippets.

@ryanwarsaw ryanwarsaw/dgraph_dfs.cc
Last active May 3, 2018

Embed
What would you like to do?
// TODO: Write a comment here.
void Dgraph::Dfs(int vertex) {
auto *has_been_visited = new bool[this->vertices_];
// set them all to unvisited.
for (int index = 0; index < this->vertices_; index++) {
has_been_visited[index] = false;
}
has_been_visited[vertex] = true;
stack<int> stack;
stack.push(vertex);
cout << vertex << " ";
while(!stack.empty()) {
int *index = nullptr;
list<int>::iterator iterator;
for (iterator = this->list_[stack.top()].begin();
iterator != this->list_[stack.top()].end();
iterator++) {
if (!has_been_visited[*iterator] && index == nullptr) {
index = &*iterator;
}
}
if (index == nullptr) {
stack.pop(); // No such vertex available.
} else {
has_been_visited[*index] = true;
cout << *index << " ";
stack.push(*index);
}
index = nullptr;
}
delete[] has_been_visited;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.