그래프 자료구조에 대해 설명해보세요
그래프는 정점과 간선으로 이루어진 자료구조
사실 트리는 그래프의 일종임. 하지만 그래프는 트리와 달리 정점마다 간선이 존재하지 않을 수 있으며, 루트노드,부모노드,자식노드 개념이 존재하지 않음
그래프를 구현할 수 있는 두 방법에 대해서 설명해주세요
연결 리스트와 배열을 이용하여 구현할 수 있음
각 방법에 대해, "두 정점이 연결되었는지" 확인하는 시간복잡도와 "한 정점에 연결된 모든 정점을 찾는" 시간복잡도, 그리고 공간복잡도를 비교해 주세요
두 정점이 연결되어있는지 확인하는 시간 복잡도의 경우 배열은 인덱스로 찾아가서 O(1)이 걸리지만, 연결리스트의 경우 노드들을 순회하면서 검색하기 때문에 최악의 경우 O(v)가 걸림. 한 정점에 연결된 모든 정점을 찾는 시간 복잡도의 경우 배열은 O(v), 연결리스트는 O(E)가 걸림. 공간복잡도의 경우 배열은 O(v^2), 연결리시트는 O(v+E)임
정점의 개수가 N개, 간선의 개수가 N^3 개라면, 어떤 방식으로 구현하는 것이 효율적일까요?
위와 같은 경우는 간선의 수가 많기 때문에 매우 밀집된 그래프임. 이렇게 밀집된 그래프일 경우 일반적으로 연결 리스트로 구현하는게 더 효율적임. 연결리스트는 공간 효율성과 간선 추가/삭제에 있어서 효율적임.
사이클이 없는 그래프는 모두 트리인가요? 그렇지 않다면, 예시를 들어주세요
그래프가 되려면 사이클이 없는 것 뿐더러, 간선의 방향성이 존재해야함. 사이클은 없지만, 간선의 방향성이 존재하지 않는 그래프는 트리가 아님
그래프에서 최단거리를 구하는 방법에 대해 설명해 주세요
그래프에서 최단거리 알고리즘은 다양하게 있음. 다익스트라 알고리즘, 벨만-포드 알고리즘, BFS 등이 있음
BFS는 가중치가 모두 없거나 모두 동일한 경우, 다익스트라나 밸만포드의 경우는 가중치가 있는 그래프에서 최단거리 구할때 용이함. 벨만포드는 특히 음의 가중치를 처리할 때 유용함.
🫠
