(C++)DFS stack을 이용해서 구현해보기

 

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

class Graph {
	int V; 
	vector<vector<int>> adj;

public:
	Graph(int V) : V(V) {}
	void addEdge(int v, int w);
	void DFS(int s);
};

void Graph::addEdge(int v, int w) {
	adj[v].push_back(w);
}

void Graph::DFS(int s) {
	vector<bool> visited(V, false);
	stack<int> st;
	st.push(s);
	while (!st.empty()) {
		int s = st.top();
		st.pop();
		if (!visited[s]) {
			visited[s] = true;
		}
		for (auto i = adj[s].begin(); i != adj[s].end(); ++i) {
			if (!visited[*i]) st.push(*i);
		}
	}
}

 

 

 

출처 : https://www.geeksforgeeks.org/iterative-depth-first-traversal/