자료구조 (2) 썸네일형 리스트형 그래프, DFS, BFS 그래프정점(Vertex)와 간선(edge)의 집합으로 객체들을 연결 시킨 것. 복잡한 사건들, 객체들 사이의 관계를 나타낼 때 사용된다. 방향이 없이 간선만 연결되 있는 그래프는 무방향 그래프.화살표로 정점간의 방향을 나타내어 연결한 그래프를 방향 그래프라고 한다. 이제 모든 정점이 다 연결 되있는 상태를 완전 그래프라고 한다. 완전 그래프에도 역시 방향, 무방향 그래프가 존재한다.여기서 간선의 수가 차이가 나는데,방향의 경우 N(N-1). 여기서 N은 정점의 수다.무방향의 경우 N(N-1) / 2. 그래프에서 정점의 연결상태를 나타내는 표현법이 있다. 인접 행렬과 인접 리스트가 있다. 인접 행렬은 자신과 연결되있는 정점을 행렬로 표현한 것이다. 연결이 되있는 정점은 1, 안 되있다면 0으로 표현한다.특.. 트리 (Tree) 전위, 중위, 후위, 레벨 순회 트리(Tree)그래프의 일종으로 여러 노드가 한 노드를 가리킬 수 없는 구조.서로 다른 두 노드를 잇는 길이 하나뿐인 그래프. 간단한 부연 설명을 해보자면.. 루트노드 : 트리의 시작 노드 간선 : 노드와 노드를 잇는 선 차수 : 해당 트리의 최대 자식노드의 수 리프노드 : 아무런 자식이 없는 노드. 자식노드 : 위로 간선이 연결되어 부모를 가진 노드. 부모노드 : 아래로 간선이 연결되어 자식을 가진 노드. 형제노드 : 같은 부모를 가진 노드 조상노드 : 해당 노드의 부모 + 부모의 부모 + ... 대손을 거쳐 올라간다.높이 : 간선의 수 서브트리 : 자식노드가 루트노드가 되어 새로 생성된 트리. 트리의 벤다이어그램은 대충 이렇다. 이제 이진 트리부터 한 번 살펴보자. 아주 기본적인 이진 트리. 이진 트.. 이전 1 다음
