Graph

4 minute read

그래프

그래프는 객체와 객체의 관계를 수학적으로 표현한 모델이다.
Vertex 와 Edge 의 집합으로 표현된다.
1:1 관계 밖에 표현하지 못하고
트리나 스택 구조와 다르게 해석의 여지가 여러가지 일 수도 있다는 단점이 있다.

그래프의 유형

그래프는 가중치와 방향을 가지며
그 유무에 따라서 네 종류로 나뉜다.

Graph : 방향도 가중치도 없다.
Weighted Graph : 방향은 없으나 가중치가 있다.
Directed Graph : 가중치는 없으나 방향이 있다.
Weighted Directed Graph : 방향과 가중치가 둘 다 있다.

그래프의 표현 방식

그래프는 한 버텍스와 그에 인접한 버텍스들의 리스트인
인접 리스트들의 집합으로 표현될 수도 있고
연결 됐는지 안 됐는지, 혹은 가중치가 얼마인지를 표현하는
행렬로 표현할 수도 있다.

이때 그래프를 이용한 알고리즘에서
인접 리스트를 활용하는 것이 더 시간이 덜 든다.

그래프의 모양으로는
희소 그래프 (Sparse Graph) 와
완전 그래프 (Complete Graph) 가 있다.

완전 그래프는 모든 버텍스가 연결이 된 것으로
이때는 인접 리스트로 구현하든 행렬로 구현하든 차이가 없다. 어차피 다 연결이 됐으니까.

단 희소 그래프일 때 인접 리스트로 구현하면 연결이 안 된 곳은 계산 자체를 안 하므로
시간, 공간도 O(n) 이 나오지만 (n은 버텍스의 개수)
행렬로 구현한다면 뭘 하든 O(n^2) 가 나온다.

그래프의 탐색

그래프의 탐색에는
깊이 우선 탐색과 (Depth First Search, 이하 DFS)
넓이 우선 탐색이 있다. (Breadth First Search, 이하 BFS)

방향도 가중치도 없는 일반 그래프이고
버텍스 넘버는 0부터 시작한다고 가정하자.

입력은 버텍스 수, 엣지 수
그리고 그 다음 줄부터 엣지의 수만큼
시작 노드와 도착 노드가 ‘유일하게’ 주어진다고 가정한다.

먼저 시작하기에 앞서 헤더 인클루드와 변수 선언을 해야한다.

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

using namespace std;

int V, E; // 버텍스, 엣지의 개수
vector<int>* graph; // 그래프
bool* visited; // 방문 여부

void input(); // 그래프를 입력받는 함수
void search(string name, void(*method)(int), int start);  // 탐색하는 함수
void dfs(int v);
void bfs(int v);

입출력을 위해 iostream 을,
그래프 저장을 위해 vector 를,
bfs 에서 쓰일 큐를 위해 queue 를
string 을 쓰기 위해 string 을 인클루드 하였다.

namespace 는 이 코드에선 std 밖에 안 쓰므로 전역에 선언해준다.

버텍스와 엣지의 개수는 어차피 예시 프로그램이고 그래프 하나만 다루므로 전역변수로 선언했다.
그래프는 벡터들의 배열로 구현하였다.
탐색 시 중복 방문을 방지하기 위하여 visited 라는 bool 배열을 선언한다.

다음은 입력받는 함수이다.

void input() {
  int from, to; // 출발, 도착 버텍스 
  cin >> V >> E; // 버텍스, 엣지의 수 입력
  graph = new vector<int>[V];  // 그래프를 버텍스 수만큼
  visited = new bool[V]; // 방문 배열을 버텍스 수만큼
  for (int i = 0; i < E; i++) {  // 엣지 수만큼 그래프 입력
    cin >> from >> to;
    graph[from].push_back(to); // 방향 없는 그래프이므로 둘 다 넣어준다
    graph[to].push_back(from);
  }
}

버텍스 수가 입력되면 그만큼 그래프와 visited 의 공간을 할당해준다.
(백준 같이 최대 입력 수가 주어지면 위에서 미리 그만큼 할당해도 된다.)

이후 엣지의 수만큼 입력을 받아 그래프에 저장한다.

이 그래프를 dfs 한 후, bfs 할 것이다.

dfs 의 코드이다.

void dfs(int v) {
  visited[v] = true; // 방문했다 체크
  
  // 해당 버텍스의 인접 리스트를 살피며
  for (vector<int>::iterator itor = graph[v].begin(); itor != graph[v].end(); ++itor) {
    if (!visited[*itor]) { // 아직 방문 안 한 버텍스라면 
        cout << v << " goes to " << *itor << endl; // 방문함을 출력하고
        dfs(*itor); // 그 버텍스에서 위의 과정 반복 (재귀)
    }
  }
}

bfs 의 코드이다.

void bfs(int v) {
  queue<int> willVisit; // 앞으로 방문할 버텍스들을 나타내는 큐
  int nowVisit; // 큐의 순서에 맞게 나와 지금 방문하고 있는 버텍스
  visited[v] = true;
  willVisit.push(v);
  while(!willVisit.empty()) { // 큐가 비지 않았을 동안 (방문할 버텍스 남아있을 동안)
    nowVisit = willVisit.front(); // 큐의 첫번째에 저장된 버텍스를 방문하자
    willVisit.pop();
    
    // 그리고 그 버텍스의 인접 리스트의 버텍스들을 모두 방문한다 (단, 방문하지 않은 버텍스만)
    for (vector<int>::iterator itor = graph[nowVisit].begin(); itor != graph[nowVisit].end(); ++itor) {  
      if(!visited[*itor]) {
      	  // 방문하지 않은 버텍스라면 방문함을 출력하고 큐에 삽입 후 방문함을 체크
          cout << nowVisit << " goes to " << *itor << endl;
          willVisit.push(*itor);
          visited[*itor] = true;
      }
    }
  }
}

이 함수들은 그래프의 dfs 와 bfs 과정을 확인하는 일종의 스켈레톤 코드로
방문하는 것을 출력하는 부분에 다른 코드를 입력하면
각각 dfs, bfs 를 활용한 알고리즘을 구현할 수 있다.

탐색을 할 때 탐색 방법도 출력하고 visited 배열을 초기화 하고
출력 사이에 공백도 만들어 주어야 하므로
search 라는 함수를 임시로 만들었다.

void search(string name, void(*method)(int), int start) {
	fill_n(visited, V, false); // 방문 배열 초기화
	cout << name << " : " << endl; // 탐색 방법 이름에 맞는 출력
	method(start); // 탐색 후
	cout << endl;  // 한 칸 띄워준다
}

위 네 함수를 사용한 메인 함수이다.

int main() {
	input();
	search("DFS", dfs, 0);
	search("BFS", bfs, 0);
	delete[] graph;
	delete[] visited;
	return 0;
}

의 입력값으로 그려진

graph

그래프에서 DFS와 BFS를 했을 때

DFS :
goes to 1
goes to 2
goes to 4
goes to 3
goes to 5
goes to 7
goes to 6
goes to 8
goes to 9

BFS :
goes to 1
goes to 2
goes to 3
goes to 4
goes to 5
goes to 7
goes to 6
goes to 8
goes to 9

라는 출력값을 확인할 수 있었다.

우리는 이 dfs 와 bfs 로 많은 것을 할 수 있다.
dfs 로는 강한 연결 요소와 이중 연결 요소를,
bfs 로는 버텍스간의 최단 거리를 찾을 수 있다.

Twitter Facebook LinkedIn

Kyojun Jin

Graph

그래프

그래프의 유형

그래프의 표현 방식

그래프의 탐색

You May Also Enjoy

Process Synchronization

19 Threads

Interprocess Communication

Operations on Process