그래프 표현 방법: 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List) 비교 그래프는 컴퓨터 과학에서 매우 중요한 자료구조로, 데이터 간의 관계를 효과적으로 표현할 수 있다. 그래프를 표현하는 방법을 선택할 때는 해결하려는 문제의 특성과 그래프의 구조를 고려해야 한다. 간선이 적은 희소 그래프의 경우 인접 리스트가 메모리와 성능 면에서 우수 간선이 많은 밀집 그래프나 정점 간 연결 여부를 빠르게 확인해야 하는 경우에는 인접 행렬이 적합하다. 실제로는 두 방법을 혼합하거나 응용한 자료구조를 사용하기도 한다. 많은 실제 응용 사례(소셜 네트워크, 웹 페이지 연결 등)에서는 정점 수에 비해 간선 수가 적은 희소 그래프의 특성을 가지므로 인접 리스트가 더 많이 사용되는 경향이 있다. ...
스패닝 트리(Spanning Tree) 스패닝 트리(Spanning Tree) 는 무방향 그래프(Undirected Graph)의 모든 정점을 포함하면서, 사이클 없이 연결된 부분 그래프이다. 다시 말해, 원래 그래프의 모든 정점을 최소한의 간선으로 연결한 트리 구조이다. 신장 트리는 그래프 이론의 핵심 개념으로, 다양한 실제 문제 해결에 활용된다. 최소 신장 트리 알고리즘인 크루스칼, 프림, 보로프카는 각각 다른 상황에서 최적의 성능을 보이며, 알고리즘 선택은 그래프의 특성과 문제 요구사항에 따라 달라진다. 신장 트리의 응용은 네트워크 설계, 클러스터링, 이미지 처리 등 다양한 분야에 걸쳐 있으며, 그 변형과 확장은 더 복잡한 문제를 해결하는 데 도움이 된다. 최적화 기법과 효율적인 자료구조를 활용하면 대규모 그래프에서도 신장 트리를 효과적으로 계산할 수 있다. ...
무방향 그래프(Undirected Graph) 무방향 그래프(Undirected Graph) 는 각 간선(Edge)에 방향성이 없는 그래프이다. 즉, 정점 A와 정점 B가 간선으로 연결되어 있으면, A에서 B로 가는 것과 B에서 A로 가는 것이 동일하다. 무방향 그래프 특징 간선이 양방향(↔)으로 연결됨 정점 간 이동에 방향성이 없음 정점의 차수(Degree)는 해당 정점과 연결된 간선의 개수 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 등의 알고리즘이 적용 가능 연결 그래프(Connected Graph)와 비연결 그래프(Disconnected Graph) 개념 적용 가능 무방향 그래프의 표현 방법 1 2 3 A — B | | C — D A - B (A와 B는 서로 연결됨) A - C (A와 C는 서로 연결됨) B - D (B와 D는 서로 연결됨) C - D (C와 D는 서로 연결됨) 무방향 그래프의 인접 행렬(Adjacency Matrix) 표현 A B C D A 0 1 1 0 B 1 0 0 1 C 1 0 0 1 D 0 1 1 0 설명 ...
방향 그래프(Directed Graph) 방향 그래프(Directed Graph, Digraph) 는 각 간선(Edge)에 방향성이 부여된 그래프이다. 즉, 간선이 단방향이므로 A → B 는 이동할 수 있지만 B → A 로는 이동할 수 없다. 방향 그래프는 일방향 관계가 있는 다양한 시스템을 모델링할 수 있다. 웹, 사회 연결망, 컴퓨터 시스템, 생물학적 네트워크 등 다양한 분야에서 방향 그래프를 활용한 알고리즘과 모델이 개발되고 있다. 방향 그래프 특징 간선이 한 방향(→)으로만 연결됨 단방향 관계를 표현할 때 사용 (예: 팔로우 관계, 웹 페이지 링크) 진입 차수(In-degree)와 진출 차수(Out-degree) 개념이 존재 진입 차수(In-degree): 해당 정점으로 들어오는 간선의 개수 진출 차수(Out-degree): 해당 정점에서 나가는 간선의 개수 방향 그래프의 표현 방법 방향 그래프 예시 ...