포시코딩

개요 대표적인 그래프 탐색 알고리즘 너비 우선 탐색(Breadth First Search:BFS) 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식 깊이 우선 탐색(Depth First Search:DFS) 정점의 자식들을 먼저 탐색하는 방식 예제 BFS 방식: A - B - C - D - G - H - I - E - F - J * 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들(형제 노드들)을 먼저 순회한다. DFS 방식: A - B - D - E - F - C - G - H - I - J * 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회한다. 구현 파이썬에서는 딕셔너리와 리스트 자료 구조를 활용해 그래프를 표현할 수 ..

그래프(Graph)란? 노드(Node)와 간선(Edge)로 이루어진 자료구조. 노드(Node): 위치를 뜻한다. 버텍스(Vertex), 정점이라고도 불림 간선(Edge): 위치 간의 관계를 표시한 선. 노드를 연결한 선으로 링크(link) 또는 브랜치(branch)라고도 한다. 인접 정점(Adjacent Vertex): 간선으로 직접 연결된 노드 참고용어 정점의 차수(Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(In-Degree): 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수 경로 길이(Path Length): 경로를 구성하기 위해 사용된 간선의 수 단순 경로(Simple Path): 처음 정점과 끝 ..

그래프란? 연결되어있는 원소간의 관계를 표현한 자료구조 비선형 구조는 표현에 초점이 맞춰져있고 선형 구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있는 반면, 그래프 자료구조는 연결 관계에 초점이 맞춰져 있다. 그래프 용어 노드(Node): 연결 관계를 가진 각 데이터를 의미. 정점(Vertax)이라고도 한다. 간선(Edge): 노드 간의 관계를 표시한 선. 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점) 그래프의 종류 유방향 그래프(Directed Graph): 방향이 있는 간선을 갖는다. 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있다. 무방향 그래프(Undirected Graph): 방향이 없는 간선을 갖는다. 무방향 그래프의 표현방법 1...