얼거스 개발 일지

특징

정점과 간선으로 이루어진 자료구조.

연결된 정점간의 관계를 표현 할 수 있는 자료구조이다.

루트노드의 구분이 없다.

그래프는 Cyclic , 트리는 ACyclic

트리는 부모-자식 관계가 있지만, 그래프는 부모-자식관계가 없다.

그래프를 탐색 할 수 있는 알고리즘으로 DFS, BFS 순회 알고리즘이 있다.

구조

정점 Vertex : 각 노드 간선 Edge : 노드와 노드를 연결하는 선 ( link, branch ) 인접 정점 Adjacent Vertax : 간선 하나를 두고 바로 연결된 정점 정점의 차수 Degree - 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배 진입 차수 In degree : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수 Out degree : 방향 그래프에서 외부로 나가는 간선의 수 경로 길이 Path length : 경로를 구성하는데 사용된 간선의 수 단순 경로 Simple path : 경로 중에서 반복되는 정점이 없는 경우 사이클 Cycle : 단순 경로의 시작 정점과 끝 정점이 동일한 경우

종류

무방향 그래프

간선에 방향이 없음 = 양 방향 이동 가능 정점 A - B 간선의 표현 : (A, B) = (B, A)

방향 그래프

간선에 방향이 있음 = 해당되는 방향으로만 이동 가능 정점 A -> B 간선의 표현 : <A, B> != <B, A>

가중치 그래프

간선에 값이 있는 그래프 값 = 이동 비용

완전 그래프

모든 정점이 서로 연결되어 있는 그래프 정점이 N개일 경우, 간선의 수는 n(n-1)/2개

그래프 탐색

DFS 깊이 우선 탐색

Depth First Search 각 노드에 방문했는지 여부를 체크할 배열과 스택을 이용하여 구현

BFS 너비 우선 탐색

각 노드에 방문했는지 여부를 체크할 배열과 큐를 이용하여 구현

그래프의 구현

인접 행렬 Adjacency Matrix

2차원 배열 이용

인접 행렬의 장단점

1. 간선 정보의 확인과 업데이트가 빠름 O(1)
2. 인접 행렬을 위한 메모리 공간 차지

   

인접 리스트 Adjacency List

연결 리스트 이용

인접 리스트의 장단점

1. 메모리 사용량이 상대적으로 적고, 노드의 추가 삭제가 빠름
2. 간선 정보 확인이 상대적으로 오래 걸림

인접 행렬 VS 인접 리스트

• 인접 행렬 : 노드의 개수가 적고, 간선의 수가 많을 때 유리 = 밀집 그래프 Dense Graph

• 인접 리스트 : 노드의 개수가 많고 간선의 수가 적을 때 유리 = 희소 그래프 Sparse graph

전체 노드 탐색에 걸리는 시간

인접 행렬 : O(N²) -> N : 전체 정점 개수 인접 리스트 : O(E) -> E : 전체 간선 개수

BFS? DFS?

두개를 어떤 때에 사용해야 할 지 감이 안잡혀서 챗봇에게 물어보았다!

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 그래프와 트리 탐색 알고리즘 중 가장 기본적인 두 가지입니다. 문제를 해결할 때 어떤 탐색 알고리즘을 사용할지 결정하는 것은 문제의 성질과 요구 사항에 따라 다릅니다.

DFS를 사용할 때 적절한 경우

모든 노드를 방문하거나 경로를 찾는 문제에서 효과적입니다. 사이클이 존재하는지 확인해야 하는 경우에 유용합니다. 백트래킹을 활용하는 경우에 사용됩니다. 예를 들어, 퍼즐 문제나 미로 찾기 등에서 경로 탐색에 DFS를 사용할 수 있습니다. 재귀 호출이나 스택을 사용하여 구현하기 때문에, 메모리 사용량이 상대적으로 적습니다.

BFS를 사용할 때 적절한 경우

시작 노드로부터 가장 가까운 노드를 찾아야 하는 경우에 유용합니다. 최단 경로를 찾아야 하는 경우, 특히 가중치가 없는 그래프에서 BFS를 사용할 수 있습니다. 그래프의 모든 노드를 동일한 레벨에서 탐색하고자 할 때 사용됩니다. 큐를 사용하여 구현하기 때문에, 탐색 순서가 보장되어 있습니다.

문제를 읽고 위의 조건들을 고려하여, 문제에 따라 DFS 또는 BFS를 선택할 수 있습니다. 어떤 문제는 두 가지 탐색 알고리즘 중 하나만 적합할 수도 있고, 어떤 문제는 두 가지 알고리즘 모두 사용하여 해결할 수 있습니다. 문제를 꼼꼼히 읽고 요구 사항을 이해하는 것이 가장 중요합니다.