그래프 표현

---

그래프를 표현하는 3가지 방법

1. 엣지

• 가중치가 없는 그래프

2차원 배열에 저장 -> [i] [j] 의 값이 그래프 시작노드와 끝 노드이다.
단방향이 아닐 경우, 값에 [1,2] [2,1] 을 모두 넣어준다.

• 가중치가 있는 그래프

3차원 배열에 저장 -> [i] [j] [k] 의 값이 그래프 시작노드, 끝 노드, 가중치이다.

엣지 리스트는 벨만포드나 크루스칼 알고리즘에서 사용한다.
특정 노드와 관련되있는 엣지를 탐색하기란 쉽지 않다.
즉, 노드 중심 알고리즘에서는 사용하면 전체 노드 중에 해당 노드를 탐색해야 하므로 시간 복잡도가 크다.

2. 인접 행렬

• 가중치가 없는 그래프

인덱스가 시작노드와 끝 노드가 된다.
값에는 노드의 유무 (보편적으로 0과 1)를 삽입한다.

• 가중치가 있는 그래프

값에 가중치를 넣어주면 된다.

인접 행렬 또한 특정 노드와 관련되있는 엣지를 탐색하기란 쉽지 않다.
N번의 탐색이 필요하기 때문이다.
또한, 에지가 적을 때는 공간 효율성도 떨어진다.
따라서, 노드 개수에 따라 적절히 판단해서 사용할 지 말지를 판단하는 게 중요하다.

3. 인접 리스트

• 가중치가 없는 그래프

ArrayList<Integer>[5];

리스트 배열로 선언한다. (리스트의 장점과 배열의 장점을 모두 사용할 수 있겠지!)
Integer에 유의!

• 가중치가 있는 그래프

클래스를 만들고 ArrayList에 자료형으로 넣어준다.

class {
	int 끝나는 점;
    int 가중치;
}

ArrayList<Node>[5];
A[3] 이 시작점
A[3].add(new node (4,13));