<TIL 20.06.16> Graph, Tree

Graph

그래프 자료구조는 상하위의 개념이 없이 각각의 node(정점, vertice)와 그 node들 간의 간선(edge)을 하나로 모아 놓은 자료구조이다

 

방향 그래프                                                                                                                              무방향 그래프

 

• 그래프는 꼭 모든 node들이 서로 관계를 갖고 있어야만 하지 않다. 따라서 그래프는 node 간 연결이 없는 고립된 부분이 있을 수도 있고, 순환할 수도 있고, 안 할 수도 있기 때문에 가장 형식에 얽매이지 않은 자료구조라고 볼 수 있다.
• 방향 그래프(Directed Graph)와 무방향 그래프(undirected Graph)가 존재한다.
• 방향 그래프에서 사용되는 용어로 한 노드에서 외부로 향하는 간선의 수를 나타내는 진출차수(out-degree) 외부 노드에서 들어오는 간선의 수를 나타내는 진입차수(in-degree)
• 위 그래프에서 A노드의 진출차수는 2 진입차수는 1이다.
• 무방향 그래프에서 하나의 정점에 인접한 정점의 수를 나타내는 차수(degree)가 있다.

• 인접 정점(adjacent vertex) : 간선에 의해 연결된 정점인 인접 정점

 

Tree

트리 자료구조는 노드로 구성된 계층적 자료구조로서, 루트노드에 child를 추가하는 방식으로 구현할 수 있다.

• 그래프 자료구조에 포함된 방향성 그래프이다.
• 노드(node) : 트리의 구성요소 (1, 2, 3, 4, 5, 6)
• 간선(edge) : 노드와 노드를 연결하는 연결선
• 루트 노드(root node) : 트리 구조에서 제일 위에 존재하는 노드(1)
• 단말 노드(terminal node) : 아래로 다른 노드가 연결되어 있지 않은 노드(4, 5, 6)
• 내부 노드(internal node) : 단말 노드를 제외한 노드(1, 2, 3)
• 노드 간에는 부모, 자식, 형제관계가 있다. 부모 노드(2) - 자식 노드(4), 형제 노드(4-5)

 

Graph와 Tree의 차이점