[그래프] 그래프의 표현

📌 그래프의 표현

⭐ 에지 리스트

• 에지를 중심으로 그래프를 표현
• 구현하기 쉬움
• 벨만포드, MST 알고리즘에서 사용

✅ 단점

• 노드 중심 알고리즘에는 잘 사용하지 않음

✅ 가중치 없는 에지 리스트

• 출발 노드, 도착 노드만 표현

✅ 가중치 있는 에지 리스트

• 출발 노드, 도착 노드, 가중치를 표현

---

⭐ 인접 행렬

• 2차원 배열의 자료구조 이용
• 노드를 중심으로 표현

✅ 단점

• 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야하므로 노드개수에 비해 에지가 적을때 공간효율성이 떨어짐
• 노드 개수가 많은 경우 2차원 배열 선언 자체를 할 수 없음

✅ 가중치 없는 인접 행렬

• 1을 저장하는 이유는 가중치가 없기 때문

✅ 가중치 있는 인접 행렬

---

⭐ 인접 리스트

• ArrayList로 그래프를 표현
• 노드 개수만큼 ArrayList를 선언
• 노드와 연결된 에지를 탐색하는 시간이 매우 뛰어남
• 노드 개수가 커도 공간효율이 좋아 메모리초과도 발생하지 않음
• 대부분 사용

✅ 가중치 없는 인접 리스트

A[3].add(4);

✅ 가중치 있는 인접 리스트

class Node{
	int e;
    int v;
    
    Node(int e, int v){
    	this.e = e;
        this.v = v;
    }
}

A[3].add(new Node(4, 13));