그래프 자료구조

📄 Graph

• 데이터 간의 연결 관계를 표현하는 자료구조
  • ex : 지하철 노선도, SNS 친구 관계
• 정점(Vertex) : 위치 개념. 노드(Node)라고도 부름.
• 간선(Edge) : 위치 간의 관계. 즉, 노드를 연결하는 선.
• 탐색(Search) : 시작점에서 간선(Edge)을 타고 이동할 수 있는 정점(Vertex)들을 찾는 문제

📄 DFS (Depth First Search, 깊이 우선 탐색)

• 막힐 때까지 깊게 탐색하고, 그 다음 다른 루트를 탐색하는 방식
  • ex : 미로 생성
• 재귀함수나 Stack으로 구현한다.

✏️ 코드 구현

#include <vector>
using namespace std;

const int MAX = 100;	// 그래프의 최대 크기
vector<int> adj[MAX];	// 인접 리스트
bool visited[MAX];		// 방문 여부

void dfs(int cur) 
{
    visited[cur] = true;		// 현재 노드를 방문 처리
    for (int next : adj[cur])	// 현재 노드를 깊게 탐색
    {
        if (!visited[next])		// 방문한 적이 없으면
        {
            dfs(next);			// 재귀호출
        }
    }
}

📄 BFS (Breadth First Search, 너비 우선 탐색)

• 가까이 인접한 곳들부터 넓게 탐색하고, 그 다음 거리에 있는 것들을 탐색하는 방식
  • ex : 최단 경로 탐색
• Queue로 구현한다.

✏️ 코드 구현

#include <vector>
#include <queue>
using namespace std;

const int MAX = 100;	// 그래프의 최대 크기
vector<int> adj[MAX];	// 인접 리스트
bool visited[MAX];		// 방문 여부

void bfs(int start)
{
	queue<int> q;
	visited[start] = true;				// 시작 노드를 방문 처리
	q.push(start);						// 시작 노드를 큐에 넣음

	while (!q.empty())					// 큐가 빌 때까지 반복
	{
		int cur = q.front();			// 이번에 방문할 노드를 꺼냄
		q.pop();
		for (int next : adj[cur])		// 인접한 노드들을 탐색하고 다음 노드를 설정
		{
			if (!visited[next])			// 방문한 적이 없으면
			{
				visited[next] = true;	// 현재 노드를 방문 처리
				q.push(next);			// 현재 노드를 큐에 넣음
			}
		}
	}
}

---

📄 참고 자료

• https://jin1ib.tistory.com/entry/BFS-DFS-1