그래프 알고리즘이란

그래프 알고리즘이란?

추상적인 대상들이 가지고있는 연결관계를 점과 선으로 표현한 방법이 그래프 알고리즘이 사용되는 이유입니다.

 

그래프의 용어

그래프는 정점(Vertex) 간선(Edag) 이루어져있습니다.

• 정점(Vertex)은 말 그대로 사물 , 데이터 등의 담고싶은 구성요소들을 의미합니다.
• 간선(Edag)은 정점(Vertex)들간의 연결관계를 의미합니다. 

 

그래프의 예시

네시 아니고 예시

그래프의 예시 이미지와 같이 여러개의 정점들과 정점들을 있는 간선이 존재하면 그래프가 됩니다.

그래프는 우리가 실제로 흔히 볼수있는 구조관계들을 그래프로 비유해볼수있습니다.

• 지하철 노선간의 관계
• SNS의 팔로우 관계

비유한 관계들은 접전과 간선만으로 표현할 수 없는 서로 다른 간선들의 길이가 존재합니다.

이렇게 간선의 길이정보가 필요한경우 간선간의 크기값을 그래프에서 Weight(가중치)라고합니다.

예시 그래프는 화살표가 존재하는것으로 보면 양방향이 아닌 일방적인 방향을 지시하고 이름은 방향 그래프라고 합니다.

그래프의 사용용도에 따라 서로 다른 그래프를 가지며 이름도 달라집니다.

 

---

그래프의 종류

• 가중치 그래프(Weight Graph) : 간선의 가중치가 있는 그래프
• 방향 그래프 (Directed Graph) : 간선의 방향이 있는 그래프
• 무방향 그래프 (UnDirected Graph) : 간선의 방향이 없는 그래프
• 무루트 트리(Unroot Tree) : 간선의 존재가 정점을 잇는 방법이 하나만 존재하는 그래프

---

 

그래프 구현

위 글을 통해서 그래프의 용어 구조 그래프의 종류를 정리해보았습니다.

지금부터 예시의 그래프를 c++로 직접 구현해보겠습니다.

 

 

그래프 생성 CreateGraph()

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

struct Vertex
{
    vector<Vertex*> edges;
    //int myData
};

vector<Vertex>  CreateGraph()
{
    vector<Vertex> v;
    v.resize(6);
    v[0].edges.push_back(&v[2]);
    v[0].edges.push_back(&v[4]);
    v[0].edges.push_back(&v[5]);

    v[1].edges.push_back(&v[4]);
    v[1].edges.push_back(&v[5]);

    v[2].edges.push_back(&v[0]); //Check1
    v[2].edges.push_back(&v[3]);
    v[2].edges.push_back(&v[4]);

    v[3].edges.push_back(&v[2]);

    v[4].edges.push_back(&v[0]);
    v[4].edges.push_back(&v[1]);
    v[4].edges.push_back(&v[2]);
    v[4].edges.push_back(&v[5]);
    
    v[5].edges.push_back(&v[0]);
    v[5].edges.push_back(&v[1]);
    v[5].edges.push_back(&v[4]);

    return v;
}

int main()
{
    vector<Vertex> graph;
    graph = CreateGraph();
    return 0;
}

 

코드 설명

struct Vertex

구조체 Vertect 멤버데이터는 접점데이터를 벡터구조로 저장합니다.

구조체로 정의된 정점이기에 멤버데이터는 모두 접근제한자 관계없이 public 입니다. 

 

CreateGraph()

예시 이미지의 그래프를 순수 구현으로 정점같의 접점들을 표현합니다.

고유한 데이터를 구현하는것이기에 코드는 길어질수밖에없습니다.

 

Check1

우리가 구현하는 예제의 그래프는 무방향 그래프이기에 0번 정점이 2번 정점을 연결했지만 다시 한번 2번 정점에서 0번 정점을

연결해줄 필요가 있습니다 만약 예제가 화살표로 0->2를 표시하였다면 중첩되는 코드를 지워야합니다.

 

---

간선의 갯수를 출력하는 프로그램 만들기

 

구현된 그래프를 활용하여 정점의 번호를 입력하면 간선의 갯수를 구하는 프로그램을 만들어보겠습니다.

int main()
{
    int number = 0;
    vector<Vertex> graph;
    graph = CreateGraph();

    
    while (true)
    {
        cout << "그래프 탐색기에 오신것을 환영합니다." << endl;
        cout << "간선의 갯수를 출력할 정점의 번호를 입력해주세요" << endl;
        
        cin >> number;
        cout << graph[number].edges.size() << endl;
         
    }
    return 0;
}

 

매우 쉬는 코드로 프로그램의 제작이 가능합니다 이로써 우리는 그래프의 접점의 갯수를 알고싶을때

직접 세어보지않고 프로그램을 통해서 갯수를 확인할수있습니다.

 

출력 결과

---

 

특정 정점의 연결여부 출력하는 프로그램 만들기

입력한 정점과 비교대상의 정점이 연결이 되어있는지 여부를 출력하는 프로그램을 만들어보겠습니다.

int main()
{
    int number = 0;
    const int TEST_VERTEX = 3;
    vector<Vertex> graph;
    graph = CreateGraph();

    while (true)
    {
        cout << "정점 테스트기를 실행해주셔서 감사합니다." << endl;
        cout << TEST_VERTEX + "번 정점의 연결 여부를 확인합니다 비교 정점을 입력해주세요" << endl;
        
        cin >> number;
        if(number == TEST_VERTEX)
        continue;
        
        bool connected = false;
        for(Vertex* edge : graph[number].edges)
        {
            if(edge == &graph[TEST_VERTEX])
            {
                connected = true;
                break;
            }
        }

        cout << connected << endl;
    }
    return 0;
}

 

구현과정

 

 

2번 정점만 유일하게 3번 정점을 연결하고있습니다.

2를 제외한 나머지 정점은 false가 출력되면 프로그램이 정상적으로 동작한다는것을 알수있습니다.

프로그램 사용자가 3을 입력하는 경우의 예외 상황을 미리 생각하고 처리해야합니다.

 

출력결과