algorithm/concept (2) 썸네일형 리스트형 [자료구조] 그래프(Graph) 이전 포스트의 트리(Tree) 자료 구조는 그래프의 한 종류이다. 하지만 모든 그래프가 트리는 아니다. 그래프(Graph) - 노드와 그 노드를 연결하는 간선(edge)를 하나로 모아 놓은 것이다. - 사이클(cycle)이 존재할 수도 있고 존재하지 않을 수도 있다. 사이클이 없는 그래프를 비순환 그래프(acyclic graph) 라고 부른다. - 방향성이 있을 수도 있고 없을 수도 있다. 그래프 표현 방법 1. 인접 리스트(Adjacency list) - 그래프를 표현할 때 사용되는 가장 일반적인 방법이다. - 아래 그래프를 인접 리스트로 표현하면 다음과 같다. adj[0]: 1 adj[1]: 2 adj[2]: 0, 3 adj[3]: 2 2. 인접 행렬(Adjacency matrix) - N*N boo.. [자료구조] 트리(Tree) 트리와 그래프는 대표적인 *비선형 자료구조 이다. (선형 구조에는 배열, 연결리스트, 스택, 큐 등이 있다.) 트리(Tree) - 노드로 이루어진 자료구조이다. - 사이클(cycle) 이 존재할 수 없다. - 하나의 루트 노드를 가진다. 루트 노드(root node)는 0개 이상의 자식 노드(child node)를 가진다. (반복) - 자식이 없는 노드는 '말단'(= leaf node)이라고 부른다. 트리의 종류 이진 트리(Binary tree) - 각 노드가 최대 2개의 자식을 갖는 트리 이진 탐색 트리(Binary search tree) - 모든 노드가 특정 순서를 가진 이진 트리 (특정 순서 속성은 모든 노드에 대해 반드시 참이여야 한다.) 예) 아래 1번 트리는 '왼쪽 자식 노드 이전 1 다음
