그래프
-
그래프Computer Science/자료구조 2023. 11. 22. 01:01
특징 정점과 간선으로 이루어진 자료구조. 연결된 정점간의 관계를 표현 할 수 있는 자료구조이다. 루트노드의 구분이 없다. 그래프는 Cyclic , 트리는 ACyclic 트리는 부모-자식 관계가 있지만, 그래프는 부모-자식관계가 없다. 그래프를 탐색 할 수 있는 알고리즘으로 DFS, BFS 순회 알고리즘이 있다. 구조 정점 Vertex : 각 노드 간선 Edge : 노드와 노드를 연결하는 선 ( link, branch ) 인접 정점 Adjacent Vertax : 간선 하나를 두고 바로 연결된 정점 정점의 차수 Degree - 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배 진입 차수 In degree : 방향 그래프에서 외부에서 오는 간..