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