[자료구조] #21 Graph(1)

• 그래프

 

임의의 두 개체의 연결 관계를 표현하는 자료구조이다.

추천 시스템, 검색 시스템, 지식 표현 및 추출에 사용될 수 있다.

 

• 그래프의 정의

 

그래프는 정점 집합과 간선 집합의 쌍으로 정의한다

 G = (V, E)

 

V(정점) : 하나의 노드는 고유한 key로 식별된다.

E(간선) : E = {(u, v) | u, v ∈ V}

 

• 그래프의 종류

 

방향 그래프

 

간선에 방향이 있어서 한쪽 방향으로만 갈 수 있다.

(u → v)로 표현한다.

(u → v) ≠ (v → u)

 

무방향 그래프

 

간선을 통해 양방향으로 갈 수 있다.

(u, v) 또는 (u ↔ v)로 표현한다.

(u, v) = (v, u)

 

가중치 그래프

 

간선에 비용(cost) 또는 가중치(weight)가 할당된 그래프이다.

 

• 그래프 용어

 

인접 정점

하나의 정점에서 간선에 의해 직접 연결된 정점들

 

G1에서 정점 A의 인접 정점 NA = {B, C, D}

 

방향 그래프에서는 방향에 따라 이웃의 개념이 다르다.

---

정점 차수

정점 차수 = 이웃 노드의 수

---

경로

그래프에서 간선을 따라 갈 수 있는 길

시작 정점이 s이고 도착 정점이 t인 하나의 경로이다. (여러 경로 존재 가능)

 

경로의 길이

경로를 구성하는데 사용된 간선의 수이다.

---

단순 경로

경로 중에서 반복되는 간선이 없는 경로이다.

{B, A, C, D}는 단순 경로이다.

 

(단순) 사이클

시작 정점과 도착 정점이 동일한 단순 경로이다.

{B, A, C, B}는 사이클이다.

---

연결 그래프

모든 정점 쌍에 대해 임의의 경로가 존재한다.

G1은 연결 그래프, G2는 비연결 그래프이다.

 

트리 (=uncycling connected graph)

사이클을 가지지 않는 연결 그래프

그래프의 특수한 형태이다.

---

완전 그래프

모든 정점이 연결되어 있는 무방향 그래프이다.

 

정점의 개수를 n이라고 하자.

 

하나의 정점은 n-1개의 간선을 가진다.

모든 정점에 대해 n(n-1)의 간선으로 카운트 된다.(중복 포함)

간선의 수(중복 제외) : n(n-1)/2

 

• 그래프의 ADT

 

insert_node(u) : 그래프에 key u를 가지는 노드 (노드 u)를 삽입한다.

insert_edge(u, v, w=1) : 간선 (u, v)를 삽입한다.(w = 가중치)

neighbors(u) : 노드 u에 인접하느 모든 정점의 집합을 반환한다.

remove_node(u) : 노드 u를 삭제한다.

*노드가 삭제될 때는 u와 연결된 간선도 모두 삭제한다.

 

• 그래프 표현 방법

 

인접 행렬

n x n의 정사각 행렬 A (n은 노드 수)

 

A[u][v] = 1 or true : 간선 (u, v)가 그래프에 존재하는 경우

A[u][v] = 0 or false : 존재하지 않는 경우

간선 가중치를 저장하는 경우 1대신 w로 대치한다.

 

인접 리스트

각 노드가 버킷을 가지며 버킷에 이웃 노드들을 저장한다.

 

• 그래프 클래스 구현

 

인접 행렬 기반 그래프의 구조

각 노드마다 index가 있으며 인접 행렬의 index에 대응한다.

index는 integer이고 0 ≤ index ≤ n-1의 범위를 가진다 가정한다.

인접 행렬은 2차원 배열로 표현된다.

 

사용 시나리오

일반적으로 인접 행렬 기반의 그래프를 구성할 때는 노드의 수 n을 미리 알고 정점의 수는 고정된다고 가정한다.

inset_node, remove_node 연산은 지원하지 않는데, 구현이 굉장히 복잡하기 때문이다.

 

따라서 정점은 고정이고 간선만 삽입/삭제할 때 주로 사용된다.

 

실제 코드로 살펴보도록 하자.

#include <iostream>
#include <vector>
#include <list>

using namespace std;

// 그래프의 종류를 나타내는 열거형
enum GraphType {
    UNDIRECTED,           // 무방향 그래프
    DIRECTED,             // 방향 그래프
    UNDIRECTED_WEIGHTED,  // 가중치를 가진 무방향 그래프
    DIRECTED_WEIGHTED     // 가중치를 가진 방향 그래프
};

// 인접 행렬 기반의 그래프 클래스
class AdjMatGraph {
private:
    vector<vector<double>> A;  // 인접 행렬을 저장할 2차원 벡터
    int n;                     // 그래프의 노드 수
    GraphType type;            // 그래프의 종류

public:
    // 생성자: 그래프의 종류와 노드 수를 받아 초기화
    AdjMatGraph(GraphType type, int n) {
        this->type = type;
        for (int i = 0; i < n; i++)
            A.push_back(vector<double>(n));  // n x n 크기의 2차원 벡터 초기화
        this->n = n;
    }

 

처음 생성할 때는 시간이 오래 걸린다. (O(n²) time & space)

// 간선 삽입 함수: 두 노드와 가중치를 받아 간선을 삽입
    void insert_edge(int u, int v, double weight = 1.0) {
        if ((type == UNDIRECTED || type == DIRECTED) && weight != 1.0)
            throw "Error: edge weight is not allowable...";  
            // 무방향 또는 방향 그래프에서 가중치가 1이 아닌 경우 예외 발생

        A[u][v] = weight;  // u에서 v로의 간선 설정
        if (type == UNDIRECTED || type == UNDIRECTED_WEIGHTED)
            A[v][u] = weight;  // 무방향 그래프의 경우 반대 방향 간선도 설정
            
// 간선 제거 함수: 두 노드를 받아 간선을 제거
    void remove_edge(int u, int v) {
        A[u][v] = 0.0;  // u에서 v로의 간선을 제거 (0으로 설정)
        if (type == UNDIRECTED || type == UNDIRECTED_WEIGHTED)
            A[v][u] = 0.0;  // 무방향 그래프의 경우 반대 방향 간선도 제거
    }

    // 그래프 출력 함수: 인접 행렬을 출력
    void display() {
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++)
                cout << A[u][v] << " ";  // 각 노드 간의 간선 유무 출력
            cout << endl;
        }
    }

 

insert_edge와 remove_edge는 O(1) time이 소요된다.

// 주어진 노드 u의 입차 이웃 노드 목록을 반환
    vector<int> in_neighbors(int u) {
        vector<int> neighbors;
        for (int v = 0; v < this->n; v++)
            if (A[v][u] != 0.0)
                neighbors.push_back(v);  // u로 들어오는 간선이 있는 노드를 추가
        return neighbors;
    }

    // 주어진 노드 u의 이웃 노드 목록을 반환 (무방향 그래프일 때만)
    vector<int> neighbors(int u) {
        if (type == DIRECTED || type == DIRECTED_WEIGHTED)
            throw "neighbors() is not defined on directed graphs";  // 방향 그래프에서는 정의되지 않음
        return out_neighbors(u);  // 무방향 그래프에서는 out_neighbors()와 동일
    }
};

 

vector<int> out(in)_neighbors는 O(n) time이 소요된다.

int main() {
    // 무방향 그래프 생성
    AdjMatGraph graph(GraphType::UNDIRECTED, 4);
    
    // 간선 삽입
    graph.insert_edge(0, 1);
    graph.insert_edge(0, 3);
    graph.insert_edge(1, 2);
    graph.insert_edge(1, 3);
    graph.insert_edge(2, 3);
    
    // 그래프 출력
    graph.display();
    
    // 노드 0의 이웃 노드 출력
    for (int v : graph.neighbors(0))
        cout << v << " ";
    cout << endl;
    
    return 0;
}