그래프와 탐색

그래프란 현실세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화하여 표현한 것을 말한다.

그래프는 정점(Vertex)과 그 사이를 잇는 간선(Edge)으로 이루어진다. G = (V, E)

 

그래프와 관련된 용어

1. 정점, 노드 (Vertex, Node) : 데이터가 저장 된다.
2. 간선 (Edge)
   • 무향 간선 (Undirected Edge) : 방향이 존재하지 않는 간선, 양방향
   • 유향 간선 (Directed Edge) : 방향이 존재하는 간선
3. 인접 (Adjacent) : (정점 관점) 두 정점 A, B 사이에 간선이 존재한다면 A, B는 인접한다.
4. 부속 (Incident) : (간선 관점) 두 정점 A, B 사이에 간선 e가 존재한다면 간선 e는 정점 A, B에 부속한다.
5. 차수 (Degree) : 한 정점에 연결된 간선의 수
   • (방향 그래프) in-degree : 정점에 들어오는 간선의 수, out-degree : 나가는 간선의 수
6. 자기 간선과 다중 간선
   • 자기 간선 (Self-loop) : 자신으로 다시 돌아오는 간선
   • 다중 간선 (Multiple / Parallel edges) : 두 개 이상의 간선이 똑같은 두 정점에 부속할 때
7. 경로 (Path) : 정점 + 간선이 교대로 구성된 sequence
   • 단순 경로 (Simple Path) : 같은 정점을 두 번 이상 가지 않는 경로
8. 회로 (Cycle) : A 정점에서 출발했을 때 다시 A 정점으로 돌아오는 경로
9. 연결됨 (Connected) : 정점 A에서 정점 B로의 경로가 존재할 때 A와 B는 연결되어 있다.

 

그래프의 종류

1. 무향 그래프 (Undirected Graph) : 무방향 간선으로 이루어진 그래프
2. 유향 그래프 (Directed Graph) : 방향 간선으로 이루어진 그래프
3. 가중치 그래프 (Weighted Graph) : 가중치(비용)를 갖는 간선들로 이루어진 그래프
4. 정규 그래프 (Regular Graph) : 모든 정점이 동일한 차수를 가지는 그래프
5. 완전 그래프 (Complete Graph) : 모든 정점이 서로 인접해있는 그래프, 완전 그래프는 정규 그래프
6. 연결 그래프 (Connected Graph) : 모든 정점이 연결되어 있어서 모든 정점끼리 경로가 존재하는 그래프
7. 부분 그래프 : 어떤 그래프의 부분 부분
8. 트리 그래프 : 싸이클을 가지지 않는 연결 그래프, 모든 정점에 대해서 경로가 정확히 1개 존재한다.

 

그래프의 표현

그래프의 표현 방식에는 인접 행렬, 인접 리스트 2가지 방식이 있다.

 

인접 행렬 (Adjacency Matrix)

• V x V 이차원 배열 A에 정보를 저장한다.
• Vi, Vj를 연결하는 간선이 존재한다면 A[i][j] = 1, 존재하지 않는다면 A[i][j] = 0
• 가중치 그래프의 경우 1 대신 가중치 정보를 저장한다.

인접 리스트 (Adjacent List)

• V 개의 Linked List로 그래프 정보를 저장한다.
• 가중치 그래프의 경우 (정점 정보, 가중치 정보)를 함께 저장한다. (C++ : pair, Java : class)

 

그래프의 탐색

그래프를 탐색하는 방법에는 깊이우선탐색(DFS)와 너비우선탐색(BFS)가 있다.

그래프를 "탐색한다"는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

 

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

 

깊이우선탐색법이란 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동하는 것이다.

 

DFS는 다음과 같은 코드를 통해 구현된다.

void go(int idx){
    cout << idx << '\n';
    visited[idx] = 1;
    for(int there : adj[idx]){
        if(visited[there]) continue;
        go(there);
    } 
    return;
}

 

DFS는 경로의  특징을 저장해둬야 하는 문제에서 유리하다. 

예를 들어 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제와 같이 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 가지지 못하기 때문)

 

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

너비우선탐색이란 루트 노드(혹은 다른 임의의 노드)에서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 떨어져있는 정점을 나중에 방문한다. 즉 최대한 넓게 이동한 다음, 더 이상 갈 수가 없을 때 아래로 이동하는 것이다.

 

BFS는 아래와 같은 코드를 통해 구현된다.

queue<int> q;
q.push(i);
visited[i] = 1;
while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int j = 0; j < graph[x].size(); j++) {
			int num = graph[x][j];
			if (!visited[num]) {
				q.push(num);
				visited[num] = 1;
				cnt++;
			}
		}
}

 

BFS는 주로 최단 경로를 찾고 싶을 때 많이 선택되는 방식이다.

예를 들어 지구 상에 존재하는 모든 친구관계를 그래프로 표현한 후 Sam과 Eddie 사이에 존재하는 경로를 찾는 경우,

DFS는 모든 친구 관계를 다 살펴야 할 지 모르지만, BFS는 Sam과 가까운 관계부터 탐색할 수 있기 때문이다.

 

최종적으로 BFS와 DFS를 비교하면 다음과 같다.

 

 

출처

https://devuna.tistory.com/32

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

https://github.com/Seogeurim/CS-study/blob/main/contents/data-structure/basic.md#binary-tree-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC