그래프(Graph)

출처: geeksforgeeks

노드(node)와 간선(edge)를 포함하는 비선형 자료구조. 노드를 정점(vertices)이라고 표현하기도 한다.

그래프에서 간선은 방향을 갖거나 갖지 않을 수 있고, 간선의 연결로 사이클(Cycle)이 생기기도 한다.

사실 이전에 배운 트리는 그래프의 한 형태이다. (트리는 루트가 있고, 사이클이 없으며, 아래 방향으로만 흐르는 그래프이다.) 👉 트리(Tree)에 대한 문서 보러가기

그래프의 특성

• 방향 그래프(Directed): 간선에 방향이 있는 그래프
• 무방향 그래프(Undirected): 간선에 방향이 없는 그래프

• Cyclic 그래프: 그래프 내부에 사이클이 있는 그래프
• Acyclic 그래프: 사이클을 이루지 않는 그래프

그래프를 표현하는 방법

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

예를 들어 인접행렬 adj가 있다고 할 때, adj[i][j]는 정점 i와 정점 j의 간선(edge) 유무를 나타낸다.

출처: geeksforgeeks

• 간선(edge)을 제거하는데 O(1)이 걸린다.
• 단 노드의 개수의 제곱만큼의 배열 공간이 필요하다.

2. 인접 리스트(Adjacency List): 배열에 노드들을 나열하고, 노드간의 관계는 연결 리스트(Linked List)로 나타내는 방법

출처: geeksforgeeks

Ref

• 그래프 - 엔지니어대한민국
• geeksforgeeks