[Algorithm] Graph Theory

개념

---

그래프는 데이터 구조의 하나로서, 여러 개의 정점(Vertex)과 이들을 연결하는 간선(Edge)으로 구성된다.

 

그래프는 사회 네트워크, 인터넷 연결, 도로망 등 다양한 시스템을 모델링하는 데 사용된다.

 

그리고 간선을 나타낼 때는 단방향, 양방향을 고려할 수 있다.

 

가장 일반적인 두 가지 방법은 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)을 사용하는 것이다.

예시

---

위와 같은 그래프는 다음과 같이 설명할 수 있다. (양방향이라 할때)

 

$0$ → 1,4

0은 1,4로 연결되어있다.

$1$ → 0,2,3,4

1은 0,2,3,4와 연결되어있다.

$2$ → 1,3

2는 1,3과 연결되어있다.

$3$ → 1,2,4

3은 1,2,4와 연결되어있다.

$4$ → 0,1,3

4는 0,1,3과 연결되어있다.

인접 리스트(Adjacency List)

해당 그래프를 리스트를 사용하여 표현할 수 있다.

$0$ = [1,4]

$1$ = [0,2,3,4]

$2$ = [1,3]

$3$ = [1,2,4]

$4$ = [0,1,3]

 

Code(C++)

#include <iostream>
#include <list>
using namespace std;

class Graph {
    int V; // 정점의 수
    list<int> *adj; // 인접 리스트 포인터 배열
public:
    Graph(int V); // 생성자
    void addEdge(int v, int w); // 간선 추가
    void printGraph(); // 그래프 출력
};

Graph::Graph(int V) {
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w); // v 정점에 w를 추가
    adj[w].push_back(v); // w 정점에 v를 추가
}

void Graph::printGraph() {
    for (int v = 0; v < V; ++v) {
        cout << "Vertex " << v << ":\t";
        for (auto x : adj[v])
            cout << "-> " << x;
        cout << endl;
    }
}

int main() {
    Graph g(5); // 5개의 정점을 가진 그래프
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);

    g.printGraph();

    return 0;
}

Vertex 0:       -> 1-> 4
Vertex 1:       -> 0-> 2-> 3-> 4
Vertex 2:       -> 1-> 3
Vertex 3:       -> 1-> 2-> 4
Vertex 4:       -> 0-> 1-> 3

인접 행렬(Adjacency Matrix)

해당 그래프를 행렬표를 사용하여 표현할 수 있다.

$0$ = [1,4]

$1$ = [0,2,3,4]

$2$ = [1,3]

$3$ = [1,2,4]

$4$ = [0,1,3]

	0	1	2	3	4
0	0	1	0	0	1
1	1	0	1	1	1
2	0	1	0	1	0
3	0	1	1	0	1
4	1	1	0	1	0

인접한 부분이 있으면 1, 없으면 0을 넣어주면 된다.

Code(C++)

#include <iostream>
using namespace std;

class Graph {
    int V; // 정점의 수
    int **adj; // 인접 행렬 포인터
public:
    Graph(int V); // 생성자
    void addEdge(int v, int w); // 간선 추가
    void printGraph(); // 그래프 출력
};

Graph::Graph(int V) {
    this->V = V;
    adj = new int*[V];
    for (int i = 0; i < V; ++i) {
        adj[i] = new int[V];
        for (int j = 0; j < V; ++j)
            adj[i][j] = 0;
    }
}

void Graph::addEdge(int v, int w) {
    adj[v][w] = 1; // v에서 w로의 간선 추가
    adj[w][v] = 1; // 무방향 그래프인 경우, w에서 v로도 추가
}

void Graph::printGraph() {
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j)
            cout << adj[i][j] << " ";
        cout << "\n";
    }
}

int main() {
    Graph g(5); // 5개의 정점을 가진 그래프
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);

    g.printGraph();

    return 0;
}

0 1 0 0 1 
1 0 1 1 1
0 1 0 1 0
0 1 1 0 1
1 1 0 1 0