자료구조 - 그래프

pa324·2019년 10월 6일
0

그래프

  • 그래프란 사물을 정점(Vertex)과 간선(Edge)으로 나타내기 위한 도구이다.
  • 그래프를 구현하는 방법에는 인접행렬(Adjacency Materix)와 인접리스트(Adjacency List)방식이 있다.
  • 인접행렬은 2차원 배열을 이용하고, 인접 리스트는 리스트를 사용한다.

인접행렬을 이용한 그래프

  • 0번째 인덱스에서 0번째 인덱스로 가는 비용은 0
  • 0번째 인덱스에서 1번째 인덱스로 가는 비용은 3
  • 0에서 2로가는 비용은 7
  • 1에서 0으로 가는비용 3
  • 1에서 1로가는 비용 0
  • 1에서 2로가는 방법 없으므로 무한
    .
    .
    .

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

  • 모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고한다.
  • 모든 간선에 가중치가 없는 그래프를 비가중치 그래프라고 한다.
  • 무방향 비가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접행렬로 출력할 수 있다.

무방향 비가중치 그래프 구현

#include<stdio.h>
int a[1001][1001];
int n,m;
int main() {
	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]);
		}
		printf("\n");
	}
	return 0;
}

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

  • 모든 간선이 방향을 가지는 그래프를 방향 그래프라고 한다.
  • 모든 간선에 가중치가 있는 그래프를 가중치 그래프라고 한다.
  • 방향 가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접리스트로 출력할 수 있다.

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



#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
	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() {
	int n,m;
	scanf("%d %d",&n,&m);
	Node **a = (Node**)malloc(sizeof(Node*) * (n+1));
	
	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;
}

비교

  • 인접행렬은 모든 정점들의 연결여부를 저장하여 O(V2)의공간 요구하므로 공간 효율성이 떨어지지만 두 정점이 서로 연결되어 있는지 확인하기 위해 O(1)의 시간 요구
  • 인접리스트는 연결된 간선의 정보만을 저장하여 O(E)의 공간을 요구하여 공간 효율성이 우수하지만 두 정저밍 서로 연결되어 있는지 확인하기 위해 O(v)의 시간을 요구한다.
profile
안녕하세요

0개의 댓글