그래프(Graph) 자료구조란 무엇인가?

알고리즘, SQL/알고리즘

킹갓홍 2023. 12. 28. 00:03

개요

DFS와 BFS에 대해서 정리를 해보려고 정리하던 중 그래프 자료구조에 대한 정리가 선행되어야 할 것 같아서 그래프 자료구조에 대해 먼저 정리하고자 한다.

그래프 자료구조란 연결되어 있는 원소간의 관계를 표현한 자료구조이다.

그래프는 위와 같이 노드와(Node) 간선(Edge)의 집합으로 노드는 정점(Vertex)라고도 불린다.

즉, 노드는 하나의 도시가 되고, 간선들은 도로를 잊는 도로가 된다.

정점/노드(Vertex/Node) : 객체 또는 위치

간선(Edge) : 정점들간의 연결관계를 나타내는 선

인접 정점(Adjacent Vertex) : 간선에 의해 직접 연결된 정점

차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수

사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

루트 노드(Root Node) : 부모 노드가 없는 최상위 노드

단말 노드(Leaf Node) : 자식 노드가 없는 노드

크기(Size) : 모든 노드의 개수

깊이(Depth) : 루트 노드로 부터 거리

높이(Height) : 깊이의 최대 값

해당 그림에서 크기가 헷갈리게 나온거 같은데,

전체 그래프를 기준으로 크기는 모든 노드의 개수인 9

루트노드는 A

단말노드는 H, I, E, F, G

깊이는 G를 기준으로 하면 2

높이는 3이 된다.

무방향 그래프

간선에 방향이 없는 그래프

방향 그래프

한쪽 방향으로만 갈 수 있는 간선이 존재하는 그래프

A에서 B로 가는 간선은 <A,B>로 표시되며, <B,A>와는 서로 다른 간선이 된다.

완전 그래프

그래프에 속해있는 모든 정점이 서로 모두 연결된 그래프

무방향 완전 그래프 정점수를 n이라고 하면, 하나의 정점은 n-1개의 다른 정점하고 연결이 되므로, 총 간선의 수는 n(n-1)/2가 된다.

부분 그래프

기존 그래프에서 일부 정점이나 간선을 제외해서 만든 그래프

가중치 그래프

간선에 가중치가 할당된 그래프

유향 비순환 그래프

방향 그래프에서 사이클이 없는 그래프

참고자료

https://leejinseop.tistory.com/43