[자료구조] 그래프의 개념과 구현

그래프란 사물을 정점(Vertex)과 간선(Edge)으로 나타내기 위한 도구입니다. 

그래프는 2가지 방식으로 구현할 수 있습니다. 

 

1) 인접행렬(Adjacency Matrix) : 2차원 배열을 사용하는 방식

2) 인접리스트(Adjacency List) : 리스트를 사용하는 방식

 

 

 

무방향 비가중치 그래프와 인접 행렬

- 모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고 합니다. 

- 모든 간선에 가중치가 없는 그래프를 비가중치 그래프라고 합니다. 

- 무방향 비가중치 그래프가 주어졌을때 연결되어 있는 상황을 인접 행렬로 출력할 수 있습니다. 

 

#include <stdio.h>

int a[1001][1001];
int n,m;

int main(void){
	scanf("%d %d", &n, &m);  //간선의 개수
    for(int i=0; i<m; i++){
    	int x,y;
 
        scanf("%d %d", &x, &y); //연결되어 있는 정점
        
        //방향성이 없기 때문에 서로 연결되어 있다. 
        a[x][y] = 1;
        a[y][x] = 1;
    }
    for(int i=1; i<=n; i++){
    	for(int j=1; j<=n; j++){
        	printf("%d ", a[i][j]); //배열 출력
        }
    }
}
     

 

 

방향 가중치 그래프와 인접 리스트

- 모든 간선이 방향을 가지는 그래프를 방향 그래프라고 합니다. 

- 모든 간선에 가중치가 있는 그래프를 가중치 그래프라고 합니다. 

- 방향 가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 리스트로 출력할 수 있습니다. 

#include <stdio.h>
#include <stdlib.h>

/* 스택기반의 연결리스트 */
typedef struct {
	int index;
    int distance;
    struct Node *next; // 다음 노드르 기록
} Node;

/* 연결 정보를 앞에다가 차례대로 */
void addFront(Node *root, int index, int distance){
	Node *node = (Node*)malloc(sizeof(Node));
    node->index = index;
    node->distance = distance;
    node->next = root->next;
    root->next = node;
}

void showAll(Node *root){
	Node *cur = root->next;
    while(cur!=NULL){
    	printf("%d(거리: %d)", cur->index, cur->distance);
        cur = cur -> next;
    }
}

int main(void){
	int n,m;
    scanf("%d %d", &n, &m);
    Node** a = (Node**)malloc(sizeof(Node*) * (n+1))l
    for(int i=1; i<=n; i++){
    	a[i] = (Node*)malloc(sizeof(Node));
        a[i]->next = NULL;
    }
    for(int i=0; i<m; i++){
    	int x, y, distance;
        scanf("%d %d %d", &x, &y, &distance);
        addFront(a[x], y, distance);
    }
    for(int i=1; i<=n; i++){
    	printf("원소 [%d]: ", i);
        showAll(a[i]); //특정한 노드에 연결되어 있는 다른 정점들을 출력하는 함수
        printf("\n");
    }
    return 0;
}
    

 

* 정리

1) 인접 행렬은 모든 정접들의 연결 여부를 저장하여 O(V^2)의 공간을 요구하므로 공간 효율성이 떨어지지만 두 정점이 서로 연결되어 있는지 확인하기 위해 O(1)의 시간을 요구합니다. 

2) 인접 리스트는 연결된 간선의 정보만을 저장하여 O(E)의 공간을 요구하므로 공간 효율성이 우수하지만 두 정점이 서로 연결되어 있는 지 확인하기 위해 O(V)의 시간을 요구합니다.