본문 바로가기
PS/Algorithm

[알고리즘 개념정리] 8. 그래프/그래프 탐색

by 이지이즤 2022. 2. 5.

**본 포스팅은 22Winter 신촌캠프 초급반 강사 dart님의 강의를 참고하여 작성하였습니다.**

 

 

그래프

  • 정점(vertice)의 집합 V와 간선(edge)의 집합 E로 이루어지며
      보통 (V,E)로 표기한다.
  • 각각의 간선은 두 정점의 쌍으로 나타낸다.
  • 간선에 방향이나 가중치가 부여되는 경우도 있다.
  • 관련 용어
    무방향/방향 그래프, 인접, 사이클,
    가중치 그래프, 연결 그래프(정점들이 모두 이어져있는 그래프)
  • 간선 표현 방법
    인접 리스트 vector<int> adj[100005];
     : 간선 개수에 비례하는 메모리만 차지 but 연결성 여부 판단 O(V)
       대부분의 경우 정점 개수가 꽤 많기 때문에 인접 리스트가 유리하다.
    인접 행렬 int adj[1005][1005];
     : 연결성 여부 판단 O(1)에 가능 but 공간 복잡도 V^2
       간선에 가중치 부여가 쉽다는 장점도 있다. adj[a][b]=c (c가 간선의 가중치)


        

 

 

깊이 우선 탐색 (Depth First Search)

: 스택의 끝에 있는 정점을 빼서 방문한다.
  그리고 그 자식 정점들을 스택에 넣는 것을 반복한다.

  방문한 노드의 자식을 방문하고,
  또 그 자식을 방문하는 것을 반복하면서 깊게 탐색해 나간다. 

  DFS는 사이클 검출이나, 재귀적 구조를 띠는 것을 이용하여 dp에 사용할 수 있다.
  일단 최대한 깊이 파고들어가므로 어떤 경로 하나를 찾고 나서 프로세스를 종료하기 쉽다.

// 재귀로 구현 1
vector<int> adj[1005];
int visited[105] = {0};

void dfs(int cur){
    if(visited[cur]) return;
    visited[cur]=1;
    for(int next : adj[cur])
        dfs(next);
}

 

// 재귀로 구현 2
vector<int> adj[1005];
int visited[105] = {0};

void dfs(int cur){
    visited[cur]=1;
    for(auto &next : adj[cur])
        if(!visited[next]) dfs(next);
}

 

// 스택으로 구현
vector<int> adj[1005];
int visited[105] = {0};

void dfs(int start){
    stack<int> st;
    st.push(start);
    visited[start]=1;
    while(!st.empty()){
        int cur = st.top(); st.pop();
        for(int next : adj[cur]){
            if(visited[next]) continue;
            visited[next] = 1;
            //
            st.push(next);
        }
    }
}

 

 

너비 우선 탐색 (Breadth First Search)

: 먼저 들어간 게 먼저 빠져나오는 자료구조인 큐를 사용한다.
 시작 정점에서 시작해서 인접한 정점을 모두 탐색한 후 다음 단계로 간다.

  시작 정점에서 더 깊어지는 방향으로 일단 내려가 보는 깊이 우선 탐색과 달리,
  너비 우선 탐색은 한 단계 깊이를 모두 탐색한 후 다음 깊이로 내려간다.

  BFS는 최단거리를 찾을 수 있는 특성 때문에 그래프 모델링에 많이 사용된다.
  특정 상태 A에서 목표로 하는 상태 B까지 가기 위한 최소 연산 횟수 등을 구하는데 응용된다.

// 큐로 구현 
vector<int> adj[1005];
int visited[105] = {0};
int dist[1005] = {0};

void bfs(int start){
    queue<int> q;
    q.push(start);
    visited[start]=1;
    while(!q.empty()){
        int cur = q.front(); q.pop();
        for(int next:adj[cur]){
            if(visited[next]) continue;
            visited[next] = 1;
            dist[next] = dist[cur]+1;
            //
            q.push(next);
        }
    }
}

이때, dist배열은 시작 정점으로부터의 최단거리를 담고 있다.

 

 

 

그래프 모델링

그래프로 모델링해서 풀 수 있는 문제들이 있다.
대표적으로는 A상태에서 B상태로 가는 데에 거쳐야 하는 상태나 연산들이 있고,
B상태 까지 가기 위해 필요한 최소 연산 횟수를 구하는 문제가 있다.

어떤 상태에 연산을 가하면 새로운 상태들과 연결된다면
A점을 시작점으로 BFS를 시행하여 B상태까지의 최단거리를 구할 수 있다.

 

 

관련 문제

 

'PS > Algorithm' 카테고리의 다른 글

[알고리즘 개념정리] 10. 최단경로 알고리즘  (0) 2022.02.14
[알고리즘 개념정리] 9. 트리  (0) 2022.02.09
[알고리즘 개념정리] 7. 이분탐색/분할정복  (0) 2022.02.02
[알고리즘 개념정리] 6. 완전탐색/백트래킹  (0) 2022.01.29
[알고리즘 개념정리] 5. 선형 자료구조(스택,큐,덱)  (0) 2022.01.27

관련글

댓글

티스토리툴바