[c++] 그래프 구조 (DFS, BFS 탐색)

선형 구조란 각 자료들이 일대일로 연결된 구조를 말합니다.

대표적으로 연결 리스트, 스택, 큐 등이 있습니다.

 

비선형 구조란 각 잘들이 일대다 혹은 다대다의 관계를 맺는 구조를 말합니다.

대표적으로 트리구조가 있습니다.

 

그래프는 선형 구조일까요 비선형 구조일까요?

 

답은 비선형 구조입니다. 그래프 또한 일대다 혹은 다대다 관계를 맺을 수 있기 때문입니다.

트리구조와 그래프 구조의 차이점은 트리는 계층적(부모, 자식)으로 이루어져있지만 그래프는 비계층적인 구조라는 점입니다.

 

그럼 이제 그래프에 대해서 알아보겠습니다.

 

[그래프 개념]

• 정점과 간선으로 이루어진 집합
• 정점(vertex) : 그래프에서 자료가 저장되어 있는 각 노드
• 간선(edge) : 정점을 연결하는 선
• n : n 관계를 연결하여 나타낼 수 있다.
• 통신망, 교통망, 소셜네트워크 관계도 등에서 활용된다.

 

 

[그래프의 종류]

 

 

[그래프의 구현]

그래프는 2가지의 방법으로 구현할 수 있습니다.

 

1. 연결 리스트로 구현

• 리스트 내의 노드들은 인접 정점에 대해서 오름차순으로 연결된다.
• 정점에 대한 인접 리스트의 헤드 포인터는 정점 개수만큼 필요하다.
• 그래프는 정점의 집합이므로 각 정점에 대한 헤드 포인터를 그룹으로 묶어서 포인터 배열로 구성한다.

 

2. 인접 행렬로 구현

• 그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장한다.
• 행렬 값 : 두 정점이 인접 되어있으면 1, 인접 되어 있지 않으면 0

위 사진에서 A를 예를들어 설명해보겠습니다.

 

A는 C, D와 간선으로 이어져 있기 때문에 A와 C, A와 D는 인접합니다.

따라서 A에 해당하는 행에 C, D에 해당하는 열의 값을 1로 표시해 줍니다.

 

 

 

[그래프의 탐색]

그래프에서 각 정점들을 중복 없이 한 번씩 방문하는 방법이 바로 그래프의 탐색입니다.

그래프의 탐색은 도로망, 전자 회로 등 많은 문제들을 해결하는 방법으로 사용됩니다.

 

가장 일반적인 탐색 방법은 2가지가 존재합니다.

 

1. 깊이 우선 탐색 (Depth First Search)

• 짧게 DFS라고 불리는 탐색 방법 입니다.
• 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이 곳으로 부터 다른 방향으로 다시 탐색을 진행합니다.
• 재귀 함수로 구현됩니다.

 

DFS 탐색 구현

bool visited[MAX_VTXS];
int adj[MAX_VTXS][MAX_VTXS];

void DFS(int n)
{
	cout << n << ' '; // 방문 했다고 알림 => ex) 출력
	visited[n] = true; // 중복 방문을 하면 안되므로 방문한 것을 bool 배열에 저장
	
	for (int i = 0; i < size; ++i)
	{
		// 두 정점이 연결 되어있고, 방문하지 않았을 때
		if (adj[n][i] == 1 && !visited[i])
			DFS(i); // 재귀
	}
}

 

 

 

2. 너비 우선 탐색 (Breadth First Search)

• 짧게 BFS라고 불리는 탐색 방법 입니다.
• 시작 정점으로 부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.
• DFS는 최초로 발견한 루트가 최단 경로라고 보장할 수 없지만, BFS는 보장할 수 있습니다.
• 큐를 사용하여 구현됩니다.

 

 

BFS 탐색 구현

bool visited[MAX_VTXS];
queue<int> q;

void BFS(int n)
{
	visited[n] = true;
	q.push(n);

	while (q.size() > 0)
	{
    	// 꺼낼 정점을 저장
 		int now = q.front();
		q.pop();
		cout << now << ' ';

		for (int i = 0; i < size; ++i)
		{
			// Q에서 꺼낸 정점과 i정점이 연결 되어있고, i정점을 방문하지 않았을 때
			if (isLinked(now, i) && !visited[i])
			{
            	// Q에 i 정점을 넣고 Q에 넣었다는 것을 visited를 통해 표시
				q.push(i);
				visited[i] = true;
			}
		}
	}
}

 

 

---

 

이렇게 그래프의 개념과 구현에 대해서 알아보았습니다.