자료구조 그래프(graph)란?

그래프(graph)란?

그래프란 비선형(non-linear) 자료구조이며 노드(node)와 엣지(edge)로 구성되어 있으며 트리도 그래프의 한 형태이다.

트리와 그래프의 차이점은 트리는 root가 있고 사이클이 없는 방향 그래프 이다. 트리는 방향그래프라 방향이 있는데 무방향 그래프로 그려진 이유는 root로 부터 아래로만 방향을 갖기 때문에 그리지 않는다. 이러한 재약들이 그래프에는 없다. 그래프에는 방향이 있는 방향그래프(Directed graph)라고 하고 방향이 없는 그래프를 무방향그래프(Undirected graph) 라고 한다.

 

 

direct and undirect graph

 

그래프의 표현

그래프를 인접행렬(Adjacency Matrix) 또는 인접리스트(Adjacency List)로 표현할수 있다.

인접행렬

인접행렬은 2차원 배열에다 표현하는 방법으로  표에다 포현할수 있다. 서로 연결이 되어있으면 1 연결이 되지 않았으면 0 으로 표현한다. 간접적으로 이어진건 포함하지 않고 직접적으로 연결된것만 표현한다.

	0	1	2	3	4
0	0	1	1	0	1
1	1	0	1	1	1
2	1	1	0	1	0
3	0	1	1	0	1
4	1	1	0	1	0

 

 

인접리스트(Adjacency List)

배열의 노드들을 나열하고 관계를 Linked List로 표현하는 방법이다.

배열방에다가 모든노드를 집어넣고 각 배열방에 있는 해당 노드와 인접한 노드들을 링크드 리스트로 쭉 나열하는것

 

나열 순서는 상관 없으며, 노드들의 개수는 엣지의 겟수를 m이라고 할때 갯수는 2m개가 된다. 

사진상에는 7개의 edge가 있으며 2x7=14로 14개의 노드가 존재하는걸 볼수있다

 

---

그래프의 연결에 종류

 

1. Cyclic은 노드들이 그래프 내부에 서클을 만드는 경우를 Cyclic
2. 사이클이 하나도 없는 경우 Acyclic
3. 노드가 자기 자신을 가르키는 경우 self edge

---

property

node: 값을 받을수 있는 노드.

edge: 노드와 노드를 연결해줄 링크

 

 

Method

.addNode(): 새로운 노드를 받아와서 그래프에 추가

.contains():  입력 값이 그래프 내에 있는지 검색

.removeNode(): 해당 노드를 그래프에서 제거함. 엣지도 제거

.addEdge(): 두 개의 노드들을 연결

.hasEdge(): 두 개의 노드가 연결되어 있는지 확인함

.removeEdge(): 두 노드 사이의 연결을 제거

.forEachNode(): 

 

 

 

사진 참조 https://www.zerocho.com/category/Algorithm/post/584b9033580277001862f16c