정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조
정점 집합
과 간선 집합
으로 표현할 수 있다.
[사진출처]
https://velog.io/@gimtommang11/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EA%B7%B8%EB%9E%98%ED%94%84
용어
간선으로 이어진 정점끼리는 양방향으로 이동이 가능
(1,2)와 (2,1)은 같은 간선으로 취급
ex) 양방향 통행 도로
간선에 방향성이 존재
만약 양방향으로 갈 수 있다고 해도 (1,2)와 (2,1)은 다른 간선으로 취급
ex) 일방통행 도로
노드들 중, 간선에 의해 연결되어있지 않은 노드가 있는 그래프
모든 정점이 서로 이동 가능한 상태인 그래프
(무방향 그래프와 그림이 같음)
모든 정점끼리 연결된 상태인 그래프
한 정점의 간선 수 = (모든 정점 수 - 1)
모든 간선의 수 = (모든 정점 수 - 1) * 정점 수
그래프의 정점과 간선의 부분집합에서 순환이 되는 부분
2차원 배열로 표현
const graph = Array.from(
Array(5), () => Array(5).fill(false)
);
graph[0].push(1); // 0 -> 1
graph[0].push(3); // 0 -> 3
graph[1].push(2); // 1 -> 2
graph[2].push(0); // 2 -> 0
graph[3].push(2); // 3 -> 2
graph[4].push(0); // 4 -> 0
연결 리스트로 표현
const graph = Array.from(
Array(5), () => []
);
graph[0].push(1); // 0 -> 1
graph[0].push(3); // 0 -> 3
graph[1].push(2); // 1 -> 2
graph[2].push(0); // 2 -> 0
graph[3].push(2); // 3 -> 2
graph[4].push(0); // 4 -> 0
그래프 관련 문제
가장 먼 노드
프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.