자료구조: 그래프 (Graph)

그래프란?

 

노드(Vertex)가 있고 그 노드를 연결하는 간선(edge)을 하나로 모아놓은 비선형 자료구조

 

그래프의 종류

 

• 무방향 그래프(undirected graph): 간선을 통해 양방향으로 이동하며, 정점A와 정점B를 연결하는 간선은 (A, B)와 같이 쌍으로 표현한다.
• 방향 그래프(directed graph): 간선에 방향성이 존재한다. A →B 로만 갈 수 있는 간선은 <A, B>로 표시한다. <A, B> 와 <B, A>는 다르다.
• 가중치 그래프(weighted graph): 간선에 비용이나 가중치가 할당된 그래프로 ‘네트워크(Network)’라고도 한다.

그래프의 구현 방식

 

1. 인접 행렬

 

2. 인접 리스트

 

그래프 메서드

 

.addNode() : 새로운 node를 생성하여 그래프에 추가한다.
.contains() : node.value가 존재하는 지 확인하고 boolean 값을 출력한다.
.removeNode() : node를 삭제하고, 연결되어 있는 간선 또한 제거한다.
.addEdge() : 새로운 edge 를 생성하여 두 개의 노드를 연결한다.
.hasEdge() : node가 서로 연결되어 있는 지 확인하여 boolean 값을 출력한다.
.removeEdge() : node를 연결하는 edge를 제거한다.
.forEachNode() : 각 노드를한 번씩 호출하여 그래프를 통과한다.