그래프 탐색 정점(Node, Vertex)과 간선(Edge)로 이루어진 그래프. 이 그래프를 탐색하는 방법에는 대표적으로 두 가지 방법이 있습니다. 깊이 우선 탐색(DFS, Depth-First Search)와 너비 우선 탐색(BFS, Breadth-First Search) 입니다. 물론 다른 그래프 탐색 알고리즘도 존재하나, 이 둘이 가장 유명한 방법이지 않을까 싶네요. 깊이 우선 탐색 (DFS, Depth - First Search) DFS는 깊이 우선이라는 이름처럼 깊이를 우선적으로 탐색합니다. 한 노드의 연결된 노드를 먼저 탐색한다는 의미죠. 해당 그래프를 DFS로 탐색한다면 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 순서로 탐색합니다. 한 노드를 탐색할 때, 해당 노드와 연결된 ..

이번에 알아볼 것은 그래프 탐색의 대표적인 방법인 그래프의 표현 방법인 인접 리스트와 인접 행렬입니다. 그래프와 트리에 관한 내용은 이전 포스팅을 참고해주세요. https://uknowblog.tistory.com/357 [자료구조] 그래프(Graph)와 트리(Tree) - 점과 선의 예술 그래프(Graph) 그래프란 무엇일까요? 점과 선이요. 가장 간단하면서 가장 잘 나타낸 말인 것 같습니다. 이산 수학과 컴퓨터 공학에서 말하는 그래프는 각각의 정점(Node, Vertex)이 간선(Edge)으로 이어 uknowblog.tistory.com 그래프의 연결 표현 : 인접 배열과 인접 리스트 그래프의 연결을 표현하는 방법에는 인접 배열과 인접 리스트가 있습니다. 이름처럼 배열을 썼느냐, 리스트를 썼느냐의 차..

그래프(Graph) 그래프란 무엇일까요? 점과 선이요. 가장 간단하면서 가장 잘 나타낸 말인 것 같습니다. 이산 수학과 컴퓨터 공학에서 말하는 그래프는 각각의 정점(Node, Vertex)이 간선(Edge)으로 이어진 형태입니다. 그래프의 시초 위 두 개의 그림은 다들 수학시간때 한 번씩 본 그림일텐데요. '쾨니히스베르크 다리 건너기' 문제입니다. 쾨니히스베르크(현 러시아 칼리닌그라드) 중앙에는 섬이 있는데, 7개의 다리를 단 한 번씩만 모두 건널 수 있느냐? 라는 문제입니다. 이걸 단순화 시킨게 아래의 그림인데, 각 육지를 점, 다리를 선으로 나타낸 것이 그래프의 시초 중 하나라고 추측되고 있습니다. 참고로 위 문제는 '한 번씩 모두 건널 수 없다'라는 것이 수학적으로 증명되었으며, 자세한 내용은 오일..