문돌이 Theo

그래프 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결관계를 표현 정점(Vertex)의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조 v : 정점의 개수, e : 간선의 개수 v 개의 정점을 가지는 그래프는 최대 v(v-1)/2 간선이 가능 선형 자료구조나 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이 그래프 유형 무향 그래프 (Undirected Graph) 유향 그래프 (Directed Graph) 가중치 그래프 (Weighted Graph) 사이클 없는 방향 그래프 (DAG, Directed Acyclic Graph) 완전 그래프 정점들에 대해 가능한 모든 간선들을 가진 그래프 부분 그래프 원래 그래프에서 일부의 정점이나 간선을 제외한..

설명 비선형 구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요 두 가지 방법 깊이 우선 탐색 (Depth First Search, DFS) 너비 우선 탐색 (Breadth First Search, BFS)] 깊이 우선 탐색 방법의 과정 시작 정점으로부터 한 방향으로 갈 수 있는 경로가 있는 깊이까지 탐색 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 후퇴 갈림길에서 다른 방향의 정점으로 탐색을 이어 진행 반복하여 모든 정점을 방문하는 순회방법 가장 마지막에 만났던 갈림길의 정점으로 되돌아가기 위해 후입선출 구조의 스택을 사용 DFS 알고리즘 # input # 7 8 (정점의 수, 간선의 수) # 1 2 1 3 2 4 2 5 4 6 5 6 6 ..