그래프와 그래프 생성

그래프 자료구조는 버텍스(정점)와 엣지(간선)으로 이루어져 있는 자료구조 이다.

각 버텍스는 엣지를 통해 연결되어져 있다.

 

그래프의 엣지에는 가중치가 존재하는 경우도 있고,

방향이 존재하는 경우도 있다.

 

단방향, 양방향, 방향 X

가중치가 존재하는 그래프의 경우, 최소 값을 갖는 경로를 찾는 알고리즘에 활용된다.

 

그럼 이 그래프.. 코드로는 어떻게 구현할까?

 

인접 리스트를 이용한 구현 방법

- 2차원 벡터를 구성하여 표현한다. 

  벡터의 인덱스가 현재 버텍스 번호이고, 인덱스 내부의 벡터 배열이 해당 인덱스에 연결된 버텍스 번호이다.

#include <vector>

using namespace std;

void CreateGraph
{
    vector<vector<int>> graph;
    graph.reszie(6);
    
    graph[0] = {1, 3};
    graph[1] = {0, 2, 3};
    graph[3] = {4};
    graph[5] = {4};
}

 

위의 코드를 그림으로 나타내면 다음과 같다.

 

인접 행렬을 이용한 구현 방법

- array[n][m] 에서 n과 m이 버텍스의 번호이고 연결된 경우 true, 그렇지 않은 경우 false로 지정.

** 이 구현에서 핵심은 2차원 배열을 false로 초기화 시키는 데 있다.

void CreateGraph
{
    vector<vector<bool>> graph(6, vector<bool>(6,false));
    
    graph[0][1] = true;
    graph[0][3] = true;
    graph[1][0] = true;
    graph[1][2] = true;
    graph[1][3] = true;
    graph[3][4] = true;
    graph[5][4] = true;
    
}

 

bool 값을 갖는 2차원 배열로 그래프를 구성하는 아이디어를 활용하면

가중치를 갖는 그래프를 형성하는 것도 쉽게 구현이 가능하다.

 

가중치를 갖는 그래프

 

위의 그래프를 코드로 구현해보자.

void CreateWeightGraph
{
    vector<vector<int>> graph(6, vector<bool>(6,-1));
    
    graph[0][1] = 15;
    graph[0][3] = 35;
    graph[1][0] = 15;
    graph[1][2] = 5;
    graph[1][3] = 10;
    graph[3][4] = 5;
    graph[5][4] = 5;
    
}

 

다음에는 이어서 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)에 대해서 알아보겠다.

 

DFS

https://jcom0922.tistory.com/98

DFS (깊이 우선 탐색)