깊이탐색, 넓이탐색

깊이 탐색 DFS (Deep First Search)

한쪽 노드를따라 마지막 노드까지 탐색후 다음 노드로 이동하여 탐색

 

넓이 탐색 BFS (Breadth First Search)

가까운 순서를 먼저 검색

DFS와 BFS의 차이

	DFS	BFS
탐색 과정	현재 정점에서 갈 수 있는 끝까지 방문하며 탐색	현재 정점에 연결된 가까운 점들부터 탐색
구현 방법	스택 또는 재귀 함수로 구현	큐 자료구조 이용

전체 코드

#include <iostream>
#include <vector>
#include <queue>


class Node
{
public:
    Node(int n_, int m_, int v_)
    {
        N = n_;
        M = m_;
        V = v_;

    }

    // 깊
    void DFS(int x)
    {
        visited[x] = true;
        std::cout << x << std::endl;

        for (int i = 0; i < graph[x].size(); i++)
        {
            int y = graph[x][i];
            if (!visited[y])
                DFS(y);
        }

    };

    // 넓
    void BFS(int x)
    {
        memset(visited, 0, sizeof(visited));

        visited[x] = true;
        que.push(x);
        
        while (!que.empty())
        {
            std::cout << que.front() << std::endl;
            que.pop();
            for (int i = 0; i < graph[x].size(); i++)
            {
                int y = graph[x][i];
                if (!visited[y])
                {
                    visited[y] = true;
                    que.push(y);
                }
            }
        }

    }

    void SetGraph(int a, int b)
    {
        graph[a].push_back(b);
    }

    void GetGraph()
    {
        for (int i = 0; i < 10; i++)
        {
            for (std::vector<int>::iterator it = graph[i].begin(); it < graph[i].end(); it++)
            {
                std::cout << *it;
            }
            std::cout << "" << std::endl;
        }
    }

private:
    int N, M, V = { 0, };

    bool visited[9];        // 방문한 위치 
    std::vector<int> graph[10];      // 그래프
    std::queue<int> que;

};

int main()
{
	Node* node = new Node(4, 5, 1);
    
	node->SetGraph(1, 2);
	node->SetGraph(1, 3);
	node->SetGraph(1, 4);
	node->SetGraph(2, 3);
	node->SetGraph(4, 5);
    
	node->DFS(1);
	node->BFS(1);
}