C++) DFS 기본형

#include <iostream>
#include <cstring>
#include <stack>

using namespace std;

#define MAX_COUNT 10
int _nodeNum, _edgeNum;
int _arrGraph[MAX_COUNT][MAX_COUNT];
bool _arrVisited[MAX_COUNT];

// 선언부
void DFS_Recursion(int firstNodeNum);
void DFS_Stack(int firstNodeNum);

int main() 
{
	cin >> _nodeNum >> _edgeNum;

	memset(_arrVisited, 0, sizeof(_arrVisited));
	memset(_arrGraph, 0, sizeof(_arrGraph));

	for (int i = 0; i < _edgeNum; i++) 
	{
		int u, v;
		cin >> u >> v;

		// 방향성이 없으므로 대칭되는 배열의 값을 전부 1로 마킹
		_arrGraph[u][v] = _arrGraph[v][u] = 1;
	}

	DFS_Recursion(0);
    DFS_Stack(0);
	return 0;
}

// 정의부
void DFS_Recursion(int firstNodeNum)
{
	// 방문 기록 마킹
	_arrVisited[firstNodeNum] = true;
	cout << firstNodeNum << ' ';

	for (int nextNodeNum = 1; nextNodeNum < _nodeNum; nextNodeNum++)
	{
		if (!_arrVisited[nextNodeNum] && // 해당 노드를 방문한 적있는가?
			_arrGraph[firstNodeNum][nextNodeNum]) // 해당 노드가 연결되어 있는가?
		{
			DFS_Recursion(nextNodeNum);
		}
	}
}

void DFS_Stack(int firstNodeNum) 
{
	bool arrVisited[MAX_COUNT] = { false };

	stack<int> stackDFS;
	stackDFS.push(firstNodeNum);

	while (!stackDFS.empty()) 
	{
		int curNodeNum = stackDFS.top();
		stackDFS.pop();

		if (arrVisited[curNodeNum]) 
		{
			continue;
		}

		arrVisited[curNodeNum] = true;
		cout << curNodeNum << ' ';

		for (int nextNodeNum = 1; nextNodeNum < _nodeNum; nextNodeNum++) 
		{
			if (!arrVisited[nextNodeNum] && _arrGraph[curNodeNum][nextNodeNum]) 
			{
				stackDFS.push(nextNodeNum);
			}
		}
	}
}

memset: 

 

void *memset(void *ptr, int value, size_t num);
cstring 헤더파일에 정의되어  ptr로 지정된 주소에서 시작하는 num 바이트의 메모리를 value로 변환된 값으로 채운다.  

 

int arr[100];
memset(arr, 0, sizeof(arr));

int 배열을 0으로 초기화하고 싶을 때 memset을 사용할 수 있다.