[C++] 4월 23일 코딩 테스트 수업

그래프 너비 우선 검색

 

너비 우선 검색

#pragma once

#include <stdio.h>

class C_GRAPH
{
private:
	int m_arNode[9][9];
	bool m_arVisit[9];
public:
	C_GRAPH() = default;
	void addNode(int nDst, int nSrc);
	void BFS(int nIndex);
	void print();
};

 

#include "graph.h"
#include <list>

void C_GRAPH::addNode(int nDst, int nSrc)
{
	m_arNode[nDst][nSrc] = 1;
	m_arNode[nSrc][nDst] = 1;
}

void C_GRAPH::BFS(int nIndex)
{
	std::list<int> que{};

	m_arVisit[nIndex] = true;
	que.push_back(nIndex);

	while (!que.empty())
	{
		int nNodeCount = (int)que.size();

		for (int j = 0; j < nNodeCount; j++) // 이게 킥임 ( 반드시 존재 해야함 )
		{
			int nPopupIndex = *que.begin(); // 이터래이터라서 포인터 붙힌거
			que.pop_front();
			printf("%d ", nPopupIndex);

			for (int i = 0; i < 9; i++)
			{
				if (!m_arVisit[i] && m_arNode[nPopupIndex][i] == 1)
				{
					m_arVisit[i] = true;
					que.push_back(i);
				}
			}
		}

		printf(","); // 깊이 체크 
	}
	printf("\n");
}

void C_GRAPH::print()
{
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			printf("%d ", m_arNode[i][j]);
		}
		printf("\n");
	}
}

 

#include <iostream>

#include "graph.h"

int main()
{
    C_GRAPH cGraph{};

    cGraph.addNode(0, 1);
    cGraph.addNode(1, 2);
    cGraph.addNode(1, 3);
    cGraph.addNode(2, 3);
    cGraph.addNode(2, 4);
    cGraph.addNode(3, 4);
    cGraph.addNode(3, 5);
    cGraph.addNode(5, 6);
    cGraph.addNode(5, 7);
    cGraph.addNode(6, 8);

    cGraph.BFS(3);
}

 

 

 

노드 구성

#pragma once

#include <list>
#include <stdio.h>

class C_GRAPH
{
private:
	struct S_NODE
	{
		int nIndex;
		bool bVisit;
		std::list<int> listChild;
	};

private:
	S_NODE m_arNode[9];

public:
	C_GRAPH();
	void BFS(int nIndex);

};

 

#include "graph.h"

C_GRAPH::C_GRAPH():
	m_arNode{}
{
	m_arNode[0].listChild.push_back(1);

	m_arNode[1].listChild.push_back(0);
	m_arNode[1].listChild.push_back(2);
	m_arNode[1].listChild.push_back(3);

	m_arNode[2].listChild.push_back(1);
	m_arNode[2].listChild.push_back(3);
	m_arNode[2].listChild.push_back(4);

	m_arNode[3].listChild.push_back(1);
	m_arNode[3].listChild.push_back(2);
	m_arNode[3].listChild.push_back(4);
	m_arNode[3].listChild.push_back(5);

	m_arNode[4].listChild.push_back(2);
	m_arNode[4].listChild.push_back(3);

	m_arNode[5].listChild.push_back(3);
	m_arNode[5].listChild.push_back(6);
	m_arNode[5].listChild.push_back(7);

	m_arNode[6].listChild.push_back(5);
	m_arNode[6].listChild.push_back(8);

	m_arNode[7].listChild.push_back(5);
	
	m_arNode[8].listChild.push_back(6);

	for (int i = 0; i < 9; i++)
	{
		m_arNode[i].nIndex = i;
	}
}

void C_GRAPH::BFS(int nIndex)
{
	std::list<S_NODE*> que{};

	que.push_back(&m_arNode[nIndex]);
	m_arNode[nIndex].bVisit = true;

	while (!que.empty())
	{
		int nNodeCount = (int)que.size();

		for (int i = 0; i < nNodeCount; i++)
		{
			S_NODE* pNode = *que.begin();
			que.pop_front();
			printf("%d ", pNode->nIndex);

			for (int nChild : pNode->listChild)
			{
				if (!m_arNode[nChild].bVisit)
				{
					que.push_back(&m_arNode[nChild]);
					m_arNode[nChild].bVisit = true;
				}
			}
		}
	}
	printf("\n");
}

 

#include <iostream>
#include "graph.h"

int main()
{
    C_GRAPH cGraph{};

    cGraph.BFS(0);
}