그래프(Graph)
그래프는 노드(Node, 또는 정점 -vertex- 이라고도 부릅니다), 그리고 노드와 노드를 연결하는 간선(edge)으로 구성됩니다.

버텍스에서 바깥으로 나가는 엣지를 outdegree(진출차수),

버텍스에서 안으로 들어오는 경우를 indegree(진입차수)라고 합니다.

graph: 2개 이상의 경로가 가능, 무방향에서 양방향으로도 가능자기 자신을 돌 수 있고, loop도 가능합니다.
루트 노드 개념이 없고, 부모-자식 개념도 없습니다.
그래프 순회는 DFS, BFS로 이루어져 있습니다.
그래프는 네트워크 모델입니다.

graph 구현 방법

인접 행렬(Adjacency matrix): 버텍스와 버텍스간의 엣지를 자주 탐색할 때.

인접 리스트(Adjaceny list): 하나의 버텍스를 기준으로, 탐색을 자주할 때.

n x n으로 만들어지기 때문에, 간선의 수와 무관하게 n²의 메모리 공간이 필요합니다. 그래서 버텍스를 잇는 엣지의 여부를 O(1)안에 찾을 수 있는 장점이 있지만, 순회를 해야 될 때는 전부 다 돌아야 되기 때문에 그래프에 간선이 많은 밀집 그래프일 때 좋습니다.

JS로 무방향 graph 구현

• addNode : 그래프에 노드 추가하기
• contains: 그래프에 해당 노드가 있는지 확인
• removeNode: 노드 삭제하기
• hasEdge: 노드와 노드 사이에 엣지가 있는지 확인
• addEdge: 노드와 노드 사이에 엣지 추가
• removeEdge: 노드와 노드 사이의 엣지 삭제

class Graph {
constructor() {
/*
*  ex)
*    nodes = {
*      0: [ 1, 2 ],
*      1: [ 0 ],
*      2: [ 0 ]
*    }
*/
this.nodes = {};
}
addNode(node) {
this.nodes[node] = this.nodes[node] || [];
}
contains(node) {
if (this.nodes[node]) {
return true;
}
return false;
}
removeNode(node) {
if (!this.nodes[node]) {
return undefined;
}
for (let edge of this.nodes[node]) {
this.removeEdge(node, edge);
}
delete this.nodes[node];
}
/*hasEdge(fromNode, toNode) {
if (this.nodes[fromNode] &&
this.nodes[toNode] &&
this.nodes[fromNode].includes(toNode) &&
this.nodes[toNode].includes(fromNode)
) {
return true
}
return false
} */
hasEdge(fromNode, toNode) {
if (this.nodes[fromNode] &&
this.nodes[fromNode].includes(toNode)) {
return true;
}
return false;
}
addEdge(fromNode, toNode) {
this.nodes[fromNode].push(toNode);
this.nodes[toNode].push(fromNode);
}
removeEdge(fromNode, toNode) {
this.nodes[fromNode].pop(toNode);
this.nodes[toNode].pop(fromNode);
}
}
module.exports = Graph;

트리(Tree)

트리는 노드로 구성된 계층적 자료구조입니다. 최상위 노드(루트)를 만들고, 루트 노드의 child를 추가하고, 그 child에 또 child를 추가하는 방식으로 트리 구조를 구현할 수 있습니다.
같은 부모 노드에 붙어 있는 child node들을 묶어서 부를 땐 형제 노드라고 부릅니다.
더 이상의 자식 노드가 없는 노드는 나뭇잎과 같다고 해서 leaf node라고 부릅니다.

tree: 트리는 그래프의 특별한 케이스이며, “최소 연결 트리”라고도 불립니다.루트 노드 개념이 있고, 부모-자식 개념도 있습니다.자기 자신을 돌 수 없음은 물론이고 loop 순환도 불가합니다.부모-자식 관계의 흐름은 상하입니다.트리의 순회는 전위, 중위, 후위 순환으로 이어지고, 이것들은 모두 그래프의 DFS, BFS 안에 있습니다.트리에는 종류가 많습니다. (이진트리, 이진탐색트리, AVL트리, 힙트리 등)트리는 계층 모델입니다.

tree depth & height

트리의 깊이는 요소에서부터 시작합니다. 요소에서부터 root까지의 거리를 재는 것

• 트리의 높이(height): 트리 중 가장 긴 경로의 간선 개수를 말한다.
• 트리의 깊이(depth): 루트에서 현재 노드 사이의 간선 개수를 말한다.
• 트리의 레벨(level): 트리의 깊이와 정의가 비슷하지만 그 기준이 간선이 아닌 노드의 개수이다. 따라서 depth+1=leveldepth+1=level 이 성립한다.

출처: https://privatedevelopnote.tistory.com/93 [개인노트]

깊이 우선 탐색과 너비 우선 탐색

깊이 우선 탐색 방법 DFS(depth-first search)

하나의 정점으로 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법인데요, 어떠한 방향으로 쭉 뻗어진 것을 끝까지 탐색 후, 더는 길이 없다고 생각하게 되면 다음으로 넘어갑니다. 이 방법은 ‘모든 노드를 돌아보고 싶을 때’ 사용을 합니다. 단순 검색은 너비 우선 탐색보다 느리지만 조금 더 간단하다는 장점이 있습니다.

너비 우선 탐색 방법 BFS(Breadth-First Search)

깊이 우선 탐색 방법과 반대의 개념으로, 하나의 정점으로 시작해서 그 정점과 맞닿아 있는 가지들을 우선적으로 본 후, 그 다음 줄에 있는 가지들, 그 다음 줄에 있는 가지들을 차례대로 보는 법을 말합니다. 두 노드 사이의 최단 경로, 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용합니다.

DFS는 재귀로 움직일 수 있는 반면에 BFS는 재귀로 움직일 수 없습니다.
DFS는 스택을 사용하지만 BFS는 큐를 사용합니다.