Carat Thinker

오늘은 그래프 알고리즘에 대해서 포스팅하려고 합니다. 그래프 자료구조에 대한 설명은 첨부된 링크를 참고해주세요! https://lifeofsw.tistory.com/26 자료구조 ④ 그래프 : 정의, 표현 방법 그래프란 노드와 에지로 구성된 집합 노드 : 데이터를 표현하는 단위 에지 : 노드를 연결하는 요소 위 그림은 방향이 있는 그래프이다. 그래프는 방향이 없을 수도 있으며, 양방향 그래프일수도 lifeofsw.tistory.com 유니온 파인드 여러 영역에서 사용되는 알고리즘 그래프의 사이클이 생성되는지 판별하는 알고리즘 union 연산 : 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶음 노드 a, b,가 $ a \in A, b \in B $ 일 때, union(a, b) = $..

그래프란 노드와 에지로 구성된 집합 노드 : 데이터를 표현하는 단위 에지 : 노드를 연결하는 요소 위 그림은 방향이 있는 그래프이다. 그래프는 방향이 없을 수도 있으며, 양방향 그래프일수도 있다. 그래프 표현 방법 에지 리스트 : 에지를 중심으로 그래프를 표현 노드 중심 알고리즘이 아닌 에지 중심 알고리즘에 사용 에지 리스트로 가중치 없는 그래프 표현 방향이 있는 그래프 : 출발 노드와 도착 노드를 표현하는 2개의 열 방향이 없는 그래프 : 2번씩 넣거나(A-B, B-A 순) 1번만 넣고 코딩 시 2번씩 호출한다 에지 리스트로 가중치 있는 그래프 표현 출발 노드, 도착 노드, 가중치를 표현하는 3개의 열 장점 : 구현이 쉽다 단점 : 특정 노드와 관련되어 있는 에지를 탐색하는 것은 어려움 인접 행렬 : ..