30. 그래프 표현 방법

C언어에서는 다양한 방법으로 그래프를 표현한다.

 

우선 그래프를 표현할 때 주의해야 할 부분은 표현하려는 그래프가 가중치 그래프인지, 비 가중치 그래프인지를 확인해야 한다. 그리고 방향그래프인지, 무방향 그래프 인지를 확인해야 한다.

 

그래프를 표현하는 방법에는 2차원 배열을 이용하는 방법과 연결 리스트를 이용하는 방법이 존재한다.

---

2차원 배열을 이용한 표현 방법이다.

#include <stdio.h>

#define GRAPH_VERTEX_CNT 5

int Graph[GRAPH_VERTEX_CNT][GRAPH_VERTEX_CNT] = {0,};

void Add_Graph(int v1, int v2){
    Graph[v1][v2] = 1;
    Graph[v2][v1] = 1;
}

void Graph_Print(){
    int i, j;
    for(i=0;i<GRAPH_VERTEX_CNT;i++){
        for(j=0;j<GRAPH_VERTEX_CNT;j++)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
}

int main()
{
    Add_Graph(1, 3);
    Add_Graph(4, 2);
    
    Graph_Print();

    return 0;
}

위는 무방향 그래프, 비 가중치 그래프를 2차원 배열로 표현한 것이다.

 

만약 방향그래프라면 아래와 같이 변경하면 된다.

void Add_Graph(int v1, int v2){
    Graph[v1][v2] = 1;
}

가중치 그래프라면 아래와 같이 변화한다.

void Add_Graph(int v1, int v2, int w){
    Graph[v1][v2] = w;
    Graph[v2][v1] = w;
}

그래프에 정점과 간선을 추가하는 함수를 조금씩만 변형하면 배열을 이용한 그래프 표현은 쉽게 작성 가능하다.