크래프톤 정글 주제별 탐구 -그래프-

정의

그래프는 트리와 유사하면서 차이를 가지고 있다. 오히려 정확한 정의를 바라보자면, 트리가 그래프의 유형 중 하나라고 볼 수 있다.

그래프란, 정점(Vertex)와 변(Edge)로 구성되어 있는 자료구조형이다.

특징

그래프는 크게 두가지로 나눌 수 있는데, 이는 변에 방향성이 있는지에 따라 변한다.

유향 그래프(Directed Graph)의 경우, 변에 방향성이 존재하며, 무향 그래프(Undirected Graph)의 경우, 변에 방향성이 없다.

유향 그래프의 경우, 이에 따라 변에 정해진 방향으로만 이동할 수 있지만, 무향 그래프의 경우 양방향 이동이 자유롭게 가능하다.

이에 따라, 길이 있다는 점과 노드가 있어서 최단 경로 문제에 자주 등장한다.

가중 그래프(weight graph)의 경우, 변(Edge)에 가중치가 있는 경우를 의미한다.

사이클(Cycle)은 순환이 가능한 부분을 뜻한다.

부가되는 알고리즘들

4색정리

다익스트라 알고리즘

외판원 순회 문제

최단 경로 문제

쾨니히스베르크 다리 건너기 문제

해밀턴 회로

Minimum Spanning Tree

Max-flow Min-cut Algorithm

네트워크 이론

컴퓨터과학

라우터

일본 최장편도승차권 문제(LOP)

DFS, BFS