그래프란?
단순히 노드(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");
}
'C자료구조' 카테고리의 다른 글
자료구조: 순차 탐색(Sequential Search) & 이진 탐색(Binary Search) (0) | 2019.08.30 |
---|---|
자료구조: 우선순위 큐(Priority Queue) (0) | 2019.08.30 |
자료구조: 이진 트리(Binary Tree) (0) | 2019.08.29 |
자료구조: 기수 정렬(Radix Sort) (0) | 2019.08.29 |
댓글