그래프
정의
- 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조입니다.
- 정점 집합(Node)과 간선 집합(Edge)으로 표현할 수 있습니다.
사용예시
- 인물관계도
- 지하철 노선도
페이지 랭크알고리즘
특징
- 정점은 여러 개의 간선을 가질 수 있습니다.
- 크게 방향 그래프와 무방향 그래프로 나눌 수 있습니다.
- 간선은 가중치를 가질 수 있습니다.
- 사이클이 발생할 수 있습니다. (무한 루프 주의)
구현방법
- 인접 행렬(Adjacency Matrix, 2차원 배열), 인접 리스트(Adjacency List, 연결 리스트) 두 가지 방식으로 그래프를 표현할 수 있습니다.
JS 에서의 구현
깃허브: https://github.com/HyeonWooGa/algorhithm-code-snippet
무방향 그래프
정의
- 간선으로 이어진 정점끼리는 양방향으로 이동이 가능합니다.
- 표현하기에 (A, B)와 (B, A)는 같은 간선으로 취급됩니다.
사용예시
- 양방향 통행 도로
방향 그래프
정의
- 간선에 방향성이 존재하는 그래프입니다.
- 양방향으로 갈 수 있더라도 <A, B>와 <B, A>는 다른 간선으로 취급됩니다.
사용예시
- 일방 통행 도로
연결 그래프
정의
- 모든 정점이 서로 이동 가능한 상태인 그래프입니다.
- 가족관계 그래프
비연결 그래프
정의
- 특정 정점쌍 사이에 간선이 존재하지 않는 그래프 입니다.
사용예시
- 친한친구 설문 그래프
완전 그래프
정의
- 모든 정점끼리 연결된 상태인 그래프입니다.
사이클
정의
- 그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분입니다.
Aim for the TOP, Developer