Graph Data Structure(그래프 자료구조)

1. 그래프(Graph) 란?

단순히 노드(또는 vertex)와 그 노드를 연결하는 간선(edge)을 하나로 모아놓은 자료구조이다.
즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조로 여러 개의 고립된 부분 그래프(Isolated Subgraphs)로 구성될 수 있다.
방향(directed)/무방향(undirected) 그래프 모두 존재한다.

 

트리 자료구조는 그래프 자료구조에 포함된다.

 

 

2. 그래프의 활용

• 지하철 노선도의 최단경로
• 구글맵 최단경로
• 페이스북 팔로워 등

 

 

3. 구현을 위한 의사코드(Pseudo Code)

자바스크립트 그래프 형태
graph = {
	"data1": {
    	"value": "data1",
        "from": [],
        "to": ["data2", "data3"]
        },
    "date2": {
    	"value": "data2",
        "from": ["data1"],
        "to": ["data3"]
        },
    "date3": {
    	"value": "data3",
        "from": ["data2", "data1"],
        "to": ["data1"]
        }
}

위와 같은 형태로 그래프를 구성하고 만든다.
1. 하나의 데이터 노드를 만들기 위해 Node constructor 함수를 만든다.
2. 데이터, 연결을 받는 데이터, 연결하는 데이터를 "from"과 "to" 배열에 담는다.
3. 해당 노드의 (value, to) 값이 Edge가 된다.
4. addNode, removeNode, addEdge, edgeList 등 필요한 메소드를 만든다.

 

 

4. 참고자료(References)

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html
https://www.zerocho.com/category/Algorithm/post/584b9033580277001862f16c