[알고리즘] 그래프

그래프

---

• 자료구조의 일종
• 정점(Node, Vertex)과 간선(Edge)로 이루어져 있음
• G = (V, E)로 나타낸다
• 차수(Degree): 정점과 연결되어 있는 간선의 개수
• 방향 그래프이 경우에는 In-degree, Out-degree로 나누어서 차수를 계산한다

 

그래프의 표현

---

인접 행렬

• 정점의 개수를 V라고 했을 때 V*V 크기의 이차원 배열을 이용
• A[i][j] =1 (i→j 간선이 있을 때, 가중치가 있을 경우 가중치), 0 (없을 때)
• 공간 복잡도: O(\(V^2\))

인접 리스트

• A[i] : i와 연결된 정정을 리스트로 포함
• 리스트의 크기는 동적으로 변경할 수 있어야(원칙적으로는 링크드 리스트, c++에서는 vector 사용)
• 공간 복잡도: O(E)
• 대체적으로 인접 리스트가 효율적

 

그래프의 탐색

---

깊이 우선 탐색(DFS)

• 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고 갈 수 없으면 정점으로 돌아간다

//인접 행렬을 이용한 구현
void dfs(int x){
    check[x] = true;
    for(int i=1; i<=n; i++){
        if(a[x][i]==1 && check[i]==false){
            dfs(i);
            }
    }
}

//인접 리스트를 이용한 구현
void dfs(int x){
    check[x] = true;
    for(int i=0; i<a[x].size(); i++){
        int y = a[x][i];
        if(check[y] == false) {
            dfs(y);
        }
    }
}

너비 우선 탐색(BFS)

• 큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식
• 큐에 넣을 때 방문했다고 체크해야 한다

//인접 행렬을 이용한 구현
queue<int> q;
check[1] = true;
q.push(1);

while(!q.empty()){
    int x = q.front(); q.pop();
    for(int i=1; i<=n; i++){
        if(a[x][i] == 1 && check[i] == false) {
            check[i] = true;
            q.push(i);
        }
    }
}

//인접 리스트를 이용한 구현
queue<int> q;
check[1] = true;
q.push(1);

while(!q.empty()){
    int x = q.front(); q.pop();
    for(int i=1; i<=a[x].size(); i++){
        int y = a[x][i];
        if( check[y] == false){
            check[y] = true; q.push(y);
        }
    }
}

시간 복잡도

• 인접 행렬: O(\(V^2\))
• 인접 리스트: O(V+E)

 

이분 그래프

---

• 그림과 같이 A와 B로 나눌 수 있으면 이분 그래프라고 한다
• A에 포함되어 있는 정점끼리 연결된 간선이 없다
• B에 포함되어 있는 정점끼리 연결된 간선이 없다
• 모든 간선의 한 끝 점은 A에, 다른 끝 점은 B에 있다

참고

---

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

이분 그래프 - 위키백과, 우리 모두의 백과사전