Graph
노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 비선형 자료 구조
- 그래프는 node(혹은 vertice)와 edge(혹은 arcs)로 구성되어 있으며 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조로 네트워크 모델이다.
- 방향성에 따라 undirected graph 와 directed graph 로 나뉘며 간선에 비용이나 가중치를 할당하는 가중치 그래프(weighted graph)가 있다.
- 무방향 그래프(undirected graph): 간선을 통해 양방향으로 이동하며, 정점A와 정점B를 연결하는 간선은 (A, B)와 같이 쌍으로 표현한다.
- 방향 그래프(directed graph): 간선에 방향성이 존재한다. A →B 로만 갈 수 있는 간선은 <A, B>로 표시한다. <A, B> 와 <B, A>는 다르다.
- 가중치 그래프(weighted graph): 간선에 비용이나 가중치가 할당된 그래프로 ‘네트워크(Network)’라고도 한다.
그래프(Graph)의 구현방식
그래프의 표현방식은 인접 행렬과 인접 리스트 두가지 방식으로 나눌 수 있다.
인접리스트(Adjacency list)
- 노드에 연결되어 있는 노드 들을 리스트 로 표현한것이다. 방향・가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접리스트로 출력할 수 있다.
- 연결된 간선의 정보만을 저장하여 O(E)의 공간을 요구하여 공간 효율성이 우수하지만 두 정점이 서로 연결되어 있는 지 확인하기 위해 O(v)의 시간을 요구한다.
인접 행렬(Adjacency matrix)
- 인접행렬은 노드를 2차원 배열로 만든 것이다. 무방향 그래프에 가중치가 없는 그래프일 경우 인접행렬로 표현할 수 있다.
- 모든 정점들의 연결여부를 저장하여 O(V2)의 공간을 요구 하므로 공간 효율성이 떨어지지만 두 정점이 서로 연결되어 있는 지 확인하기 위해 O(1)의 시간을 요구한다.
Graph method
.addNode() : 새로운 node를 생성하여 그래프에 추가한다.
.contains() : node.value가 존재하는 지 확인하고 boolean 값을 출력한다.
.removeNode() : node를 삭제하고, 연결되어 있는 간선 또한 제거한다.
.addEdge() : 새로운 edge 를 생성하여 두 개의 노드를 연결한다.
.hasEdge() : node가 서로 연결되어 있는 지 확인하여 boolean 값을 출력한다.
.removeEdge() : node를 연결하는 edge를 제거한다.
.forEachNode() : 각 노드를한 번씩 호출하여 그래프를 통과한다.
출처- geeksforgeeks, velog.io, gmlwjd9405
