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

그래프란?

단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조

그래프 구현 방식

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

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

 

그래프(Graph)와 관련된 용어

정점(vertex): 위치라는 개념. (node 라고도 부름)
간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점
정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
참조 : https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

 

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

// 무방향 비가중치 그래프와 인접 행렬
#define _CRT_SECURE_NO_WARINGS
#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; i <= n; j++) {
			printf("%d ", a[i][j]);
		}
		printf("\n");
	}
	system("pause");
}

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

// 방향 가중치 그래프와 인접 리스트
#define _CRT_SECURE_NO_WARNINGS
#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));
	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");
	}
	system("pause");
}