[알고리즘/java] 그래프와 인접행렬

[알고리즘/java] 그래프와 인접행렬

이 글은 인프런 [자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 ] 강의를 수강하며 작성한 글입니다.

- https://inf.run/Azjw

그래프는 정점과 간선의 집합으로, G(V, E) [정점 V 간선 E] 로 표현한다.

그 종류는 무방향 그래프, 방향 그래프, 가중치 방향그래프로 나눌 수 있다.

<무방향그래프>

무방향그래프

무방향 그래프는 방향이 없지만 양방향이라고 생각하면 편하다. 즉 1은 2로 2는 1로 갈 수 있다.

행과 열을 모두 노드라고 생각한다.

이를 인접행렬 2차원 배열로 표현하면 아래와 같다.

graph[a][b] = 1;

graph[b][a] = 1;

(배열의 빈 칸은 0으로 채워져 있다.)

<방향그래프>

방향그래프

방향 그래프는 각 노드에서 다른 노드로 정해진 방향으로만 갈 수 있다.

행에서 열로 갈 수 있다라고 생각하면 편하다.

== (1은 2과 3으로 갈 수 있다. 2는 5로 갈 수 있다. ..)

이를 인접행렬 2차원 배열로 표현하면 아래와 같다.

graph[a][b] = 1;

(배열의 빈 칸은 0으로 채워져 있다.)

<가중치 방향그래프>

가중치 방향그래프

가중치 방향그래프는 방향그래프에서 비용 을 추가한 것이라고 생각하면 편하다.

(1에서 2로 갈 때 비용이 2만큼 든다.)

이를 인접행렬 2차원 배열로 표현하면 아래와 같다.

graph[a][b] = c;

(배열의 빈 칸은 0으로 채워져 있다.)

from http://bumbleb22.tistory.com/12 by ccl(A) rewrite - 2021-12-21 21:00:25