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

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

- https://inf.run/Azjw

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

 

그래프는 정점과 간선의 집합으로,  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으로 채워져 있다.)