그래프, BFS, DFS

msung99·2022년 3월 18일
알고리즘
0
post-thumbnail

그래프 = 정점(vertex/node) + 간선(edge)로 이루어진 자료구조

  • 차수(degree) : 각 정점에 대해서 간선으로 연결된 이웃한 정점의 개수

그래프 종류

  1. 방향성

  • 무방향 그래프(undirected graph)

  • 방향 그래프(directed graph) : 간선에 방향성이 있는 그래프

    • 방향 그래프 차수 종류 : outdegree 진출차수 - 자기에게서 나가는 간선의 개수)
      indegree 진입차수 - 자기에게 들어오는 간선의 개수
  1. 사이클 - 임의의 한 점에서 출발해 자기 자신으로 돌아올 수 있는 경로
  • 순환 그래프(Cyclic graph) : 그래프 안에 사이클이 하나라도 있는 경우
  • 비순환 그래프(Acyclic graph) : 그래프 안에 사이클이 없는 경우
  1. 간선의 경우의 수

  • 완전 그래프(Complete graph) : 두 정점 쌍이 간선으로 연결된 그래프( = 모든 정점이 완전히 모든 경우의 간선으로 연결된 그래프)

  • 연결 그래프(Connected graph) : 임의의 두 정점 사이에 경로가 항상 존재하는 그래프 ( = 모든 정점이 연결은 되있되, 모든 경우의 간선으로 연결된 그래프는 아니다.)

  • 단순 그래프(Simple graph) : 두 정점 사이의 간선이 1개 이하이고, 루프가 존재하지 않는 그래프
    • 루프(loop) : 자기 자신으로 다시 돌아오는 간선을 갖는 정점

그래프 표현법(1) - 인접행렬

인접행렬(adjacency matrix) : 행렬에다 0과 1을 표시함으로써 두 정점 사이의 인접 여부를 표현하는 방법

  • 정점이 V개, 간선이 E개일때 어떤 두 점의 연결여부를 O(1)로 알 수 있다.
  • 가로와 새로가 각각 V인 2차원 배열이 필요하므로 O(V^2) 의 공간이 필요
  • 어떤 점에 연결되어 있는 모든 정점의 목록을 알아내고 싶은 경우
    => 개수와 무관하게 O(V)

인접행렬 적용 시키기

  • 단순 무방향 그래프
    => 연결된 두 정점에는 1을 , 연결되지 않은 두 정점에는 0을 준다
    정점 2와 3이 연결되어 있다면 (2,3) 과 (3,2) 에다 1을 할당해준다

  • 단순 방향 그래프
    => (2,3)이 1이라는 의미 : 2에서 3으로 가는 간선이 있다는 의미

  • 단순 그래프가 아닌 경우

    • 단순 그래프가 아닌경우 1혹은 0으로만 나타내지 말고, 간선이 3개면 3을 쓰고, 4개면 4를 쓰는 식으로 변형을 시키면 쉽게 해결됨

그래프 문제 유형 - 인접행렬 활용

  • 이런 그래프가 있을때 방향 그래프, 무방향 그래프로 나타내보자.
  1. 방향 그래프
int adj_matirx[10][10] = {};
int v, e; // 정점 개수, 간선 개수
cin >> v >> e; // 5,7 입력받음
for(int i = 0; i < e; i++){
  int u, v;
  cin >> u >> v;  // 3,1 이 입력되면 3->1 로 가는 간선이 있다는 뜻
  adj_matrix[u][v] = 1;
}

2.무방향 그래프

int adj_matrix[10][10] = {};
int v, e;
cin >> v >> e;
for(int i=0; i<e; i++){
  int u, v;
  cin >> u >> v; // 3,1 이 입력되면 3과 1이 이어져있다는 뜻
  adj_matrix[u][v] = 1;
  adj_matrix[v][u] = 1;
}

그래프 표현법(2) - 인접 리스트

  • V개의 리스트를 만들어 각 리스트에 자신과 연결된 정점을 넣는 방식

  • 정점이 많고 간선은 상대적으로 적은 상황에서 공간을 절약할 수 있는 방식

  • 인접 행렬에서는 V by V 크기의 배열을 선언했어야 하니 O(V^2)의 공간이 필요했는데, 인접 리스트에서는 O(V+E) 의 공간이 필요.

    • 리스트가 V개 필요하고, 간선이 1개 있을 때 마다 방향 그래프에서는 특정 리스트 1개의 원소가 추가되고, 무방향 그래프에서는 특정 리스트 2개의 원소가 1개씩 추가된다.
    • 따라서 모든 리스트에서 원소의 개수의 총합은 방향 그래프일때 E개, 무방향 그래프일때 2E개 이므로 최종적으로 O(V+E) 가 된다.
  • 방향 그래프
    • 양쪽에 다 넣는게 아니라, 한쪽에만 넣으면 된다.
  • 무방향 그래프

그래프 문제 유형 - 인접 리스트 활용

  • 이런 그래프가 있을때 방향 그래프, 무방향 그래프로 나타내보자.

  • adj[i] : 정점 i와 연결된 정점들의 목록을 가지고 있는 벡터

  • 방향 그래프인지, 무방향 그래프인지에 따라서 adj[u] 에만 값을 넣으지, 아니면 adj[u] 와 adj[v] 에 모두 넣을지 결정

  1. 방향 그래프
vector<int> adj[10]; 
int v, e;
cin >> v >> e;
for(int i=0; i < e; i++){
  int u, v;
  cin >> u >> v;
  adj[u].push_back(v);
}
  1. 무방향 그래프
vector<int> adj[10];
int v, e;
cin >> v >> e;
for(int i=0; i < e; i++){
  int u, v;
  cin >> u >> v;
  adj[u].push_back(v);
  adj[v].push_back(u);
}
  1. STL 사용 안하는 방향 그래프
int edge[10][2];
int deg[10]; // 각 정점의 outdegree
int* adj[10];
int idx[10]; // adj[i]에서 새로운 정점을 추가할 때의 위치
int main(){
  int v, e;
  for(int i=0; i<e; i++){
    cin >> edge[i][0] >> edge[i][1];
    deg[edge[i][0]]++;
  }
  for(int i=1; i <= v; i++)
    adj[i] = new int[deg[i]];
  for(int i=0; i<e; i++){
    int u = edge[i][0];
    int v = edge[i][1];
    adj[u][idx[u]] =v;
    idx[u]++;
  }
}

정리

인접행렬

  • 공간 복잡도 : O(V^2)
  • 정점 u,v가 연결되어있는지 확인하는 시간 : O(1)
    • 그냥 adj_matrix[u][v]를 확인하면 끝
  • 정점 v와 연결된 모든 정점을 확인하는 시간 : O(V)
    • 1번부터 V번까지 연결관계를 모두 확인해야함
  • 효율적인 상황 : 두 점의 연결여부를 자주 확인할 때 / E가 V^2에 가까울 때

인접 리스트

  • 공간 복잡도 : O(V+E)

  • 정점 u,v가 연결되어있는지 확인하는 시간 : O(min(deg(u), deg(v))

    • 한 정점에 자신과 연결된 모든 정점을 확인해야함. 둘 중 차수가 작은걸 확인하는게 이득

  • 정점 v와 연결된 모든 정점을 확인하는 시간 : O(deg(v))

  • 효율적인 상황 : 특정 정점에 연결된 모든 정점을 자주 확인할 때 / E가 V^2보다 훨씬 작을 때

인접 행렬 vs 인접 리스트

  • 일반적인 문제에서 정점 u,v 가 연결되어 있는지를 반복적으로 확인해야야 하는 경우는 잘 없다.

  • BFS, DFS 등 여러 경로 알고리즘 => 특정 정점에 연결된 모든 정점을 확인하는 작업이 반복적으로 등장함.

    • 인접 리스트로 그래프를 나타낼 것!

(입력이 인접 행렬 느낌으로 주어지거나, V가 많이 작아서 구현의 편의를 챙기고자 하거나, 플로이드 알고리즘 등은 인접 행렬로 구현)

BFS

  • 너비 우선 탐색

  • 모든 노드를 방문하기 위한 알고리즘

  • 구현 방법 : 1. 그래프(인접 행렬, 인접 리스트) // 2. 다차원 배열

    • 그래프에서 너비를 우선으로 방문하는 알고리즘
    • 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

BFS 알고리즘

다차원 배열에서는 상하좌우로 인접한 칸을 확인했던 반면에, 그래프에서는 간선으로 연결된 정점을 본다는 차이만 있다.

1.시작하는 정점을 큐에 넣고 방문했다는 표시를 남김

2.큐에서 정점을 꺼내어 그 정점과 연결된 모든 정점들에 대해 3번을 진행

  • 다차원 배열의 경우 상하좌우로 인접한 칸을 방문

3.해당 정점을 이전에 방문했다면 아무것도 하지않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입

4.큐가 빌 때까지 2번을 반복

BFS 알고리즘을 그래프로 구현하는 방법에 따른 시간 복잡도

  • 모든 정점이 큐에 최대 1번씩 들어가므로 인접 리스트에서 O(V+E),
    인접 행렬에서 O(V^2) 의 시간이 걸림

1.인접 행렬 : O(V^2)

  • 특정 정점과 연결된 모든 정점을 확인하는 2번 과정이 O(V)를 필요로 함
    = >2번 과정 자체가 V개의 모든 정점에 대해 실행될 수 있으니, O(V^2) 이다.

2.인접 리스트 : O(V+E)

  • 2번 과정에서 모든 정점들에 대해 그 정점과 연결된 모든 정점을 살펴보는 과정의 총 합이 방향 그래프에서 E, 무방향 그래프에서 2E 여서 O(V+E) 가 걸린다.

인접 리스트 : O(V+E) 인 이유

  • 각 간선은 2번씩 등장한다.

    • 논리적으로 생각해봐도 당연한게, u와 v를 연결하는 간선은 u와 연결된 모든 정점을 살펴볼 때, 그리고 v와 연결된 간선을 살펴볼 때 한번씩 등장한다.
    • 연결 그래프의 경우, u에서 v로 가는 간선은 u와 연결된 모든 정점을 살펴볼 때만 등장한다.

    => 따라서 모든 정점들에 대해 그 정점과 연결된 모든 정점을 살펴보는 과정은 2E번 혹은 E번의 탐색 과정이 필요하게 되서 O(V+E) 가 걸린다.

  • 다차원 배열에서의 BFS는 그냥 간선이 각 칸마다 최대 4개가 있는 상황이였다 보니 그냥 시간복잡도가 칸 수에 비례한다고 쉽게 생각했었다.

    • 그런데 그래프에서는 시간복잡도에 E가 포함된다는 것을 유념하자.

BFS 예시코드1 - 연결 그래프에서의 순회

  • 인접 리스트로 방식으로 저장된 그래프에서 BFS를 진행하는 코드
vector<int> adj[10]; // 인접 리스트
bool vis[10]; // 이전에 방문했는지 여부를 체크하는 리스트

void BFS(){
  queue<int> q;
  q.push(1); // 정점 1을 먼저 최초로 방문
  vis[1] = true; // 1을 방문했다고 체크해줌
  // 정점 1에서부터 시작해서 이와 인접한 정점으로 범위를 점점 뻗어가며 탐색
  while(!q.empty()){
    int cur = q.front(); // 큐의 맨앞 데이터값 출력 후 삭제
    q.pop();
    cout << cur << ' ';
    for(auto nxt : adj[cur]){ // 큐 맨앞에서 추출한 정점 cur에 대해 인접 리스트를 탐색 
    // 인접 리스트를 탐색하면서 정점 cur와 인접해 있는 정점들에 대해 방문 여부를 체크한다.
      if(vis[nxt]) // 이전에 방문한 정점이면 건너뜀
        continue;
      q.push(nxt); // 처음 방문하는 정점이면 큐에 push
      vis[nxt] = true; // 방문 처리함
    }

BFS 예시코드2 - 연결 그래프에서 1번 정점과의 거리

시작점에서 다른 모든 점으로의 최단 경로를 찾을 때 BFS 를 이용할 수 있다.

  • BFS 과정중에서 현재 보는 정점으로부터 추가되는 인접한 정점은 시작점으로부터 1만큼 더 떨어져있다.
  • 즉, 모든 간선의 길이가 동일한 상황에서 두 지점 사이의 거리를 찾는 문제는 BFS 로 해결 가능
    • 하지만 모든 간선의 길이가 다르다면 플로이드나 다익스트라와 같은 다른 알고리즘을 사용해야 한다.
  • 1번 정점과의 거리를 구하는 경우
    • 1번 정점과의 거리가 필요하다면 dist배열을 선언해서 잘 채우면 된다.
    • dist 의 원소를 모두 -1로 초기화후, dist 배열이 -1인지 아닌지를 가지고 방문 여부를 판단하면 visited 배열을 별도로 선언할 필요 x
vector<int> adj[10]; // 인접 리스트
int dist[10]; // 방문여부체크 => -1 : 아직 방문x , 0 이상의 값 : 시작점으로 부터의 거리 값

void BFS(){
  fill(dist, dist+10, -1); // 배열 dist를 -1로 초기화
  // 이후에 dist 배열이 -1인지 아닌지를 가지고 방문 여부를 판단
  queue<int> q;
  q.push(1);
  dist[1] = 0; // 방문 했다고 체크
  while(!q.empty()){
    int cur = q.front(); 
    q.pop();
    for(auto nxt : adj[i]){ 
      if(dist[nxt] != -1)  // 이미 방문한 정점이라면 pass
        continue;
      q.push(nxt);
      dist[nxt] = dist[cur] + 1; // 시작점으로부터의 거리값 1 증가
    }
  }
}

BFS 예시코드3 - 연결 그래프가 아닐 때 순회

  • 연결 그래프가 아닌 곳에서 순회를 하면 모든 정점을 다 순회하지 못한다.

  • for문을 돌려서 아직 방문하지 않은 정점을 찾아서 그 정점을 시작 정점으로 잡게끔 코드를 구성할 것!

vector<int> adj[10];
bool vis[10];
int v = 9; // 정점의 수

void BFS(){ // 아직 방문안한 정점을 찾아서 시작 정점으로 설정
  queue<int> q;
  for(int i=1; i <= v; i++){
    if(vis[i])  // while 문에서 본격적인 BFS 탐색을 진행하기 전에, 다차원 배열에서 새로운 구역을 찾았듯이 끊어진 새로운 그래프 구역을 찾아낸다.
      continue;
    q.push(i); 
    vis[i] = true; 
    while(!q.empty()){
      int cur = q.front(); // 큐 맨앞 정점 삭제후 출력
      q.pop();
      cout << cur << ' ';
      for(auto next : adj[cur]){
        if(vis[nxt])  // 이전에 방문한 정점이면 건너뜀
          continue;
        q.push(nxt); // 처음 방문하는 정점이면 큐에 push
        vis[nxt] = true; // 방문 처리함
      }
    }
  }
}

DFS

  • 구현 방법 : 1. 재귀 2. 스택

스택으로 구현

  • BFS의 과정에서 큐만 스택으로 바꾸면 DFS 과정이 된다.
  • BFS와 같이 모든 정점이 스택에 최대 1번씩 들어가므로 인접 리스트에서 O(V+E), 인접 행렬에서 O(V^2) 의 시간이 걸림

DFS 알고리즘 - 스택으로 구현

  1. 시작하는 정점을 스택에 넣고 방문했다는 표시를 남김

  2. 스택에서 정점을 꺼내어 그 정점과 연결된 모든 정점들에 대해 3번을 진행

  3. 해당 정점을 이전에 방문했다면 아무것도 하지 않고,
    처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입

  4. 스택이 빌 때 까지 2번을 반복

DFS 예시코드1 - 연결 그래프에서의 순회, 비재귀(스택활용)

vector<int> adj[10];
bool vis[10];

boid DFS(){
  stack<int> s;
  s.push(1);
  vis[1] = true;
  while(!s.empty()){
    int cur = s.top();
    s.pop();
    cout << cur << ' ';
    for(auto nxt : adj[cur]){
      if(vis[nxt]) 
        continue;
      s.push(nxt);
      vis[nxt] = true;
    }
  }
}

재귀를 이용한 DFS 구현

  • 재귀를 사용해 DFS를 구현할 수 있다.

    => 재귀적으로 함수를 호출하는 상황 자체가 가장 늦게 호출된 함수를 먼저 처리하는 LIFO, 즉 자연스럽게 스택을 이용하는 모양새가 되어서 그렇다고 생각할 수 있다.

  • 스택 메모리에 제한이 작은 경우에는 재귀 구현에 문제가 발생함.
    (백준,프로그래머스 에서는 스택 메모리 제한 없어서 맘대로 구현해도됨
    SW Expert Academy 에서는 스택 메모리가 1MB로 제한)

DFS 예시코드2 - 연결 그래프에서의 순회, 재귀 (재귀로 구현)

vector<int> adj[10];
bool vis[10];

void DFS(int cur){
  vis[cur] = true;
  cout << cur << ' ';
  for(auto nxt : adj[cur]){
    if(vis[nxt])
      continue;
    DFS(nxt);
  }
}

재귀 DFS 와 비재귀(스택 구현) DFS의 동작 차이

    1. 재귀

재귀적인 방식으로 DFS를 돌면 1,2,4,3 순으로 방문한다.

갈 수 있는 곳이 여러 개라면 번호가 작은 것 부터 방문한다고 할 때

DFS(1) 은 DFS(2) 를 부르고, DFS(2) 는 DFS(4) 를 부르고, DFS(4) 는 DFS(3) 을 부른다.

    1. 스택 활용

맨 처음 1번 정점을 스택에서 뽑았을 때 이웃한 2,3,4번 정점에 모두 방문했다는 기록을 남겨놓고 다음 정점으로 넘어감.

이 떄문에 1 2 3 4 순으로 방문을 한다.

정리 - 동작 방식의 차이 이유

재귀적인 방식은 실제 방문을 할때 방문 표시를 남기는 반면에,

비재귀적인 방식(스택 활용방식)은 방문하기 전에 아직 방문하지 않는 곳을 발견하면 그때 방문 표시를 남기기 때문에 동작 방식의 차이가 있다.

  • 우리가 통상적으로 생각하는 DFS는 재귀 DFS가 동작하는 방식과 일치한다.

    => 즉, 비재귀(스택) DFS는 순회를 잘 수행하지만, 엄밀히 말해 우리가 관념적으로 생각하는 DFS 방문 순서와 다르다.

    DFS 고유한 성질을 사용해 문제를 해결하는 경우는 비재귀 코드를 이용하지 말것!

DFS 예시코드3 - 스택 구현(2) : 스택 메모리 제한 문제점 해결 코드

  • 이전 코드에서는 nxt를 스택에 넣은 직후에 바로 방문 여부, 즉 vis[nxt] 를 true 로 만들어 스택에 각 정점이 무조건 1번씩만 만들었다.

  • 반면 이 코드는 스택에 넣을 때 방문 표시를 남기는게 아니라, 스택에서 값을 뽑은 후에 방문 여부를 true 로 만들도록 했다.

  • 이렇게 수정하면 우리가 관념적으로 생각하는 DFS 동작 (방문순서 동작) 과 일차한다.

  • 스택 자체에는 각 정점이 무조건 1번씩 들어가지는 않고 여러 번 들어갈 수도 있지만, " if(visited[cur]) " 처리로 인해 결국 연결되니 정점을 보는 작업은 각 정점마다 최대 1번씩만 하기 떄문에 시간복잡도는 동일하게 O(V+E) 이다.

vector<int> adj[10];
bool visited[10];

void DFS(){
  stack<int> s;
  s.push(1);
  while(!s.empty()){
    int cur = s.top();
    s.pop();
    if(visited[cur]) 
      continue;
    visited[cur] = true;
    cout << cur << ' ';
    for(auto nxt : adj[cur])
      if(visited[nxt])
        continue;
      s.push(nxt);
}
profile
msung99
블로그 이전했습니다 🙂 : https://haon.blog
이전 포스트

ADT(추상 자료형), 스택(Stack)

다음 포스트

BFS (다차원 배열)

0개의 댓글