그래프(Graph) 알고리즘
9.1 그래프의 표현 방법1. 인접 행렬 (Adjacency Matrix)정의: 2차원 배열로 노드 간 연결 관계를 표현장점: 연결 확인이 빠름 (O(1))단점: 메모리 소모 큼 (O(n²))# 무방향 그래프 예시adj_matrix = [ [0, 1, 1, 1], # 0번 노드 → 1,2,3 연결 [1, 0, 0, 1], # 1번 노드 → 0,3 연결 [1, 0, 0, 1], # 2번 노드 → 0,3 연결 [1, 1, 1, 0] # 3번 노드 → 0,1,2 연결]2. 인접 리스트 (Adjacency List)정의: 각 노드마다 연결된 노드 리스트를 저장장점: 메모리 효율적 (O(n+e))단점: 연결 확인이 느림 (O(n))# 무방향 그래프 예시 (0번 노드 → 1,2,3 연..
2025. 4. 19.
그래프 이론 기초
1. 그래프란?그래프(graph)란 여러 개의 점(정점, 노드, vertex)과 이 점들을 연결하는 선(간선, edge)으로 이루어진 자료구조입니다.그래프의 예시:지하철 노선도소셜 네트워크(사람이 노드, 친구 관계가 간선)지도(도시가 노드, 도로가 간선)2. 그래프의 구성 요소정점(Vertex, Node):정보를 담고 있는 점. 예: 도시, 사람, 컴퓨터 등.간선(Edge):정점과 정점을 연결하는 선. 예: 도로, 친구 관계, 네트워크 케이블 등.3. 그래프의 종류1) 방향 그래프(Directed Graph)간선에 방향이 있음.예: 트위터 팔로우(한쪽만 연결 가능)표기: (A → B) : A에서 B로만 이동 가능2) 무방향 그래프(Undirected Graph)간선에 방향이 없음.예: 페이스북 친구(양방..
2025. 4. 19.