오늘의 다짐
오늘 진행된 강의에서 학습한 내용은 무엇인가요?
그래프: 개요, 특징, 표현 방법, 예시 코드, 실제 사용 예시
개요
그래프는 정점(Node)과 간선(Edge)으로 구성된 자료구조입니다.
- 정점: 객체나 개체를 나타냅니다. (예: 도시, 사람, 웹 페이지)
- 간선: 정점 간의 연결을 나타내며, 정점들 간의 관계를 정의합니다. (예: 도로, 친구 관계, 링크)
특징
- 데이터 구조: 그래프는 객체 간의 관계를 표현하는데 유용합니다.
- 다양한 유형: 방향 그래프(간선에 방향이 있는 경우)와 무방향 그래프(간선에 방향이 없는 경우)가 있습니다.
- 가중치: 간선에 가중치를 부여하여 거리, 비용 등을 표현할 수 있습니다.
표현 방법
- 인접 행렬: 2차원 배열을 사용하여 정점 간의 연결 여부를 나타냅니다.
- 장점: 간선 존재 여부를 빠르게 확인 가능, 정점과 간선 수가 고정된 경우 효율적
- 단점: 메모리 사용량이 많음, 희소 그래프에는 비효율적
- 인접 리스트: 각 정점에 연결된 정점들의 리스트를 저장합니다.
- 장점: 메모리 사용량이 적음, 희소 그래프에 효율적, 동적 그래프에 적합
- 단점: 간선 존재 여부 확인에 비교적 느림
장점
- 관계 표현: 객체 간의 관계를 명확하게 표현하고 시각화할 수 있습니다.
- 경로 탐색: 최단 경로, 최대 흐름 등 다양한 경로 탐색 알고리즘에 활용됩니다.
- 사회망 분석: 친구 관계, 협업 관계 등 사회망 데이터 분석에 유용합니다.
- 추천 시스템: 사용자와 아이템 간의 유사성을 기반으로 추천 시스템 구축에 활용됩니다.
- 지도 시스템: 도로, 건물 등 공간 정보를 표현하고 경로 안내에 활용됩니다.
단점
- 메모리 사용: 밀집한 그래프의 경우 메모리 사용량이 많아질 수 있습니다.
- 연산 복잡도: 특정 작업 (예: 최단 경로 탐색)에 대한 연산 복잡도가 높을 수 있습니다.
- 처리 속도: 대규모 그래프를 처리할 때 속도가 느려질 수 있습니다.
시간 복잡도
- 간선 존재 여부 확인: O(1) (인접 행렬 사용) 또는 O(n) (인접 리스트 사용, n은 정점 수)
- 최단 경로 탐색: Dijkstra 알고리즘: O(E log V), V는 정점 수, E는 간선 수
- 최대 흐름: Ford-Fulkerson 알고리즘: O(E f), E는 간선 수, f는 최대 흐름
실제 사용되는 예시
- 사회망: 친구 관계, 팔로워 관계 등을 표현하고 분석
- 지도 시스템: 도로, 건물 등 공간 정보를 표현하고 경로 안내
- 추천 시스템: 사용자와 아이템 간의 유사성을 기반으로 추천
- 네트워크 분석: 통신 네트워크, 컴퓨터 네트워크 등의 구조와 성능 분석
- 게임: 맵 구조, 캐릭터 이동 경로 등을 표현
예시 코드 (Java)
무방향 그래프 예시 코드 (Java)
다음은 인접 행렬과 인접 리스트 두 가지 방식으로 표현된 무방향 그래프의 예시 코드입니다.
1. 인접 행렬 (Adjacency Matrix)
public class UndirectedGraphUsingAdjacencyMatrix {
private int[][] adjacencyMatrix;
public UndirectedGraphUsingAdjacencyMatrix(int vertices) {
this.adjacencyMatrix = new int[vertices][vertices];
}
public void addEdge(int v1, int v2) {
adjacencyMatrix[v1][v2] = 1;
adjacencyMatrix[v2][v1] = 1; // 무방향 그래프이므로 양방향 연결 표시
}
public void printAdjacencyMatrix() {
for (int i = 0; i < adjacencyMatrix.length; i++) {
for (int j = 0; j < adjacencyMatrix[0].length; j++) {
System.out.print(adjacencyMatrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
UndirectedGraphUsingAdjacencyMatrix graph = new UndirectedGraphUsingAdjacencyMatrix(5);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
System.out.println("인접 행렬:");
graph.printAdjacencyMatrix();
}
}설명:
1. 클래스 정의: UndirectedGraphUsingAdjacencyMatrix 클래스는 인접 행렬을 사용하여 무방향 그래프를 표현합니다.
멤버 변수:
2. adjacencyMatrix: 2차원 배열로 정점 간의 연결 정보를 저장합니다.
생성자:
3. UndirectedGraphUsingAdjacencyMatrix(int vertices): 생성자는 그래프의 정점 개수를 입력받아 adjacencyMatrix 를 초기화합니다.
addEdge 메서드:
4. addEdge(int v1, int v2): 두 정점 v1과 v2 사이에 간선을 추가합니다. 무방향 그래프이므로 양방향 연결을 표현하기 위해 adjacencyMatrix[v1][v2]와 adjacencyMatrix[v2][v1] 를 1로 설정합니다.
5. printAdjacencyMatrix 메서드: printAdjacencyMatrix()** : 인접 행렬을 출력하여 그래프의 연결 정보를 시각적으로 보여줍니다.
6. main 메서드: 예시 그래프를 생성하고 간선을 추가한 후 printAdjacencyMatrix 메서드를 호출하여 인접 행렬을 출력합니다.
2. 인접 리스트 (Adjacency List)
public class UndirectedGraphUsingAdjacencyList {
private Map<Integer, List<Integer>> adjacencyList;
public UndirectedGraphUsingAdjacencyList(int vertices) {
this.adjacencyList = new HashMap<>();
for (int i = 0; i < vertices; i++) {
adjacencyList.put(i, new ArrayList<>()); // 각 정점에 대한 연결 리스트 초기화
}
}
public void addEdge(int v1, int v2) {
adjacencyList.get(v1).add(v2);
adjacencyList.get(v2).add(v1); // 무방향 그래프이므로 양방향 연결 표시
}
public void printAdjacencyList() {
for (Map.Entry<Integer, List<Integer>> entry : adjacencyList.entrySet()) {
System.out.print(entry.getKey() + ":");
for (Integer neighbor : entry.getValue()) {
System.out.print(" " + neighbor);
}
System.out.println();
}
}
public static void main(String[] args) {
UndirectedGraphUsingAdjacencyList graph = new UndirectedGraphUsingAdjacencyList(5);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(1
무방향 그래프의 인접 리스트
인접 리스트는 그래프의 연결 정보를 표현하는 또 다른 방식입니다. 인접 행렬과 달리, 인접 리스트는 각 정점에 연결된 다른 정점들을 리스트 형태로 저장합니다.
장점:
- 메모리 사용량이 더 효율적일 수 있습니다. 특히, 연결 밀도가 낮은 그래프에서 효과적입니다.
- 특정 정점에 연결된 정점들을 빠르게 찾을 수 있습니다.
- 간선 추가 및 삭제가 비교적 간단합니다.
단점:
- 모든 정점 간의 연결 여부를 확인하기 위해서는 전체 리스트를 순회해야 합니다.
- 인접 행렬에 비해 코드가 다소 복잡해질 수 있습니다.
예시 코드 (Java)
public class UndirectedGraphUsingAdjacencyList {
private Map<Integer, List<Integer>> adjacencyList;
public UndirectedGraphUsingAdjacencyList(int vertices) {
this.adjacencyList = new HashMap<>();
for (int i = 0; i < vertices; i++) {
adjacencyList.put(i, new ArrayList<>()); // 각 정점에 대한 연결 리스트 초기화
}
}
public void addEdge(int v1, int v2) {
adjacencyList.get(v1).add(v2);
adjacencyList.get(v2).add(v1); // 무방향 그래프이므로 양방향 연결 표시
}
public void printAdjacencyList() {
for (Map.Entry<Integer, List<Integer>> entry : adjacencyList.entrySet()) {
System.out.print(entry.getKey() + ":");
for (Integer neighbor : entry.getValue()) {
System.out.print(" " + neighbor);
}
System.out.println();
}
}
public static void main(String[] args) {
UndirectedGraphUsingAdjacencyList graph = new UndirectedGraphUsingAdjacencyList(5);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
System.out.println("인접 리스트:");
graph.printAdjacencyList();
}
}설명:
- 클래스 정의:
UndirectedGraphUsingAdjacencyList클래스는 인접 리스트를 사용하여 무방향 그래프를 표현합니다. - 멤버 변수:
adjacencyList:HashMap객체를 사용하여 정점과 연결된 정점들의 리스트를 저장합니다.
- 생성자:
UndirectedGraphUsingAdjacencyList(int vertices): 생성자는 그래프의 정점 개수를 입력받아adjacencyList를 초기화합니다. 각 정점에 빈 리스트를 할당합니다.
- addEdge 메서드:
addEdge(int v1, int v2): 두 정점v1과v2사이에 간선을 추가합니다. 무방향 그래프이므로 양방향 연결을 표현하기 위해adjacencyList.get(v1).add(v2)와adjacencyList.get(v2).add(v1)를 사용하여 연결 리스트에 추가합니다.
- printAdjacencyList 메서드:
printAdjacencyList(): 모든 정점과 연결된 정점들을 순서대로 출력합니다.
- main 메서드:
- 예시 그래프를 생성하고 간선을 추가한 후
printAdjacencyList메서드를 호출하여 연결 정보를 출력합니다.
- 예시 그래프를 생성하고 간선을 추가한 후
방향 그래프
방향 그래프의 인접 행렬
예시 코드 (Java)
public class DirectedGraphUsingAdjacencyMatrix {
private int[][] adjacencyMatrix;
public DirectedGraphUsingAdjacencyMatrix(int vertices) {
this.adjacencyMatrix = new int[vertices][vertices];
}
public void addEdge(int source, int destination) {
adjacencyMatrix[source][destination] = 1;
}
public void printAdjacencyMatrix() {
for (int i = 0; i < adjacencyMatrix.length; i++) {
for (int j = 0; j < adjacencyMatrix[0].length; j++) {
System.out.print(adjacencyMatrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
DirectedGraphUsingAdjacencyMatrix graph = new DirectedGraphUsingAdjacencyMatrix(5);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 0);
graph.addEdge(4, 1);
System.out.println("인접 행렬:");
graph.printAdjacencyMatrix();
}
}설명:
- 클래스 정의:
DirectedGraphUsingAdjacencyMatrix클래스는 인접 행렬을 사용하여 방향 그래프를 표현합니다. - 멤버 변수:
adjacencyMatrix: 2차원 배열로 정점 간의 연결 정보를 저장합니다.
- 생성자:
DirectedGraphUsingAdjacencyMatrix(int vertices): 생성자는 그래프의 정점 개수를 입력받아adjacencyMatrix를 초기화합니다.
- addEdge 메서드:
addEdge(int source, int destination): 두 정점source와destination사이에 방향성 간선을 추가합니다.adjacencyMatrix[source][destination]에 1을 저장하여 해당 방향으로 연결이 있음을 표시합니다.
- printAdjacencyMatrix 메서드:
printAdjacencyMatrix(): 인접 행렬을 출력하여 그래프의 연결 정보를 시각적으로 보여줍니다.
- main 메서드:
- 예시 그래프를 생성하고 간선을 추가한 후
printAdjacencyMatrix메서드를 호출하여 인접 행렬을 출력합니다.
- 예시 그래프를 생성하고 간선을 추가한 후
주의:
- 방향 그래프의 인접 행렬은 대각선 값들이 항상 0이어야 합니다. 왜냐하면, 정점은 스스로 연결될 수 없기 때문입니다.
- 인접 행렬 방식은 모든 정점 간의 연결 여부를 확인하기 위해 전체 행렬을 순회해야 한다는 단점이 있습니다. 특히, 연결 밀도가 낮은 그래프에서는 비효율적일 수 있습니다.
방향 그래프의 인접 리스트
예시 코드 (Java)
public class DirectedGraphUsingAdjacencyList {
private Map<Integer, List<Integer>> adjacencyList;
public DirectedGraphUsingAdjacencyList(int vertices) {
this.adjacencyList = new HashMap<>();
for (int i = 0; i < vertices; i++) {
adjacencyList.put(i, new ArrayList<>()); // 각 정점에 대한 연결 리스트 초기화
}
}
public void addEdge(int source, int destination) {
adjacencyList.get(source).add(destination);
}
public void printAdjacencyList() {
for (Map.Entry<Integer, List<Integer>> entry : adjacencyList.entrySet()) {
System.out.print(entry.getKey() + " -> ");
for (Integer neighbor : entry.getValue()) {
System.out.print(neighbor + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
DirectedGraphUsingAdjacencyList graph = new DirectedGraphUsingAdjacencyList(5);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 0);
graph.addEdge(4, 1);
System.out.println("인접 리스트:");
graph.printAdjacencyList();
}
}설명:
- 클래스 정의:
DirectedGraphUsingAdjacencyList클래스는 인접 리스트를 사용하여 방향 그래프를 표현합니다. - 멤버 변수:
adjacencyList:HashMap객체를 사용하여 각 정점에서 출발하는 연결된 정점들을 리스트 형태로 저장합니다.
- 생성자:
DirectedGraphUsingAdjacencyList(int vertices): 생성자는 그래프의 정점 개수를 입력받아adjacencyList를 초기화합니다. 각 정점에 빈 리스트를 할당합니다.
- addEdge 메서드:
addEdge(int source, int destination): 두 정점source와destination사이에 방향성 간선을 추가합니다.adjacencyList.get(source).add(destination)을 사용하여source정점의 연결 리스트에destination정점을 추가합니다.
- printAdjacencyList 메서드:
printAdjacencyList(): 모든 정점에서 출발하는 연결된 정점들을 방향과 함께 출력합니다.
- main 메서드:
- 예시 그래프를 생성하고 간선을 추가한 후
printAdjacencyList메서드를 호출하여 연결 정보를 출력합니다.
- 예시 그래프를 생성하고 간선을 추가한 후
장점:
- 인접 행렬에 비해 메모리 사용량이 더 효율적일 수 있습니다. 특히, 연결 밀도가 낮은 그래프에서 효과적입니다.
- 특정 정점에서 출발하는 모든 연결된 정점들을 빠르게 찾을 수 있습니다.
- 간선 추가 및 삭제가 비교적 간단합니다.
단점:
- 모든 정점에서 출발하여 도달할 수 있는 모든 정점들을 확인하기 위해서는 전체 리스트를 순회해야 합니다.
- 인접 행렬에 비해 코드가 다소 복잡해질 수 있습니다.
주의:
- 방향 그래프의 인접 리스트에서 각 정점의 연결 리스트는
- 출발 정점에서 도달 가능한 정점들만 포함해야 합니다.
- 반대 방향으로 연결된 정점은 포함하지 않아야 합니다.
오늘 얻은 인사이트는 무엇인가요?
결론
이 글에서는 그래프를 표현하는 두 가지 주요 방식인 인접 행렬과 인접 리스트에 대해 살펴보았습니다. 각 방식의 특징, 장점, 단점, 예시 코드를 통해 비교 분석했습니다.
인접 행렬:
- 모든 정점 간의 연결 여부를 쉽게 확인해야 하는 경우
- 특정 정점으로부터 도달 가능한 정점들을 빠르게 찾아야 하는 경우
- 연결 밀도가 높은 그래프를 다루는 경우
인접 리스트:
- 메모리 사용량이 중요한 경우 (특히, 연결 밀도가 낮은 그래프에서)
- 특정 정점에서 출발하는 연결된 정점들을 빠르게 찾아야 하는 경우
- 간선 추가 및 삭제가 빈번하게 발생하는 경우
어떤 방식을 선택할지는 구체적인 문제 상황과 요구 사항에 따라 달라질 수 있습니다.
추가 고려 사항:
- 그래프의 크기 (정점 개수, 간선 개수)
- 사용 가능한 메모리 공간
- 알고리즘 수행 속도
- 개인적인 선호도 및 코드 작성 편의성
'스케쥴 > 스터디' 카테고리의 다른 글
| [항해99 취업리부트 TIL] 4주차 2일 (1) | 2024.06.12 |
|---|---|
| [항해99 취업리부트 TIL] 3주차 5일 (5) | 2024.06.10 |
| [항해99 취업리부트 TIL] 3주차 3일 (0) | 2024.06.07 |
| [항해99 취업리부트 TIL] 3주차 2일 (0) | 2024.06.06 |
| [항해99 취업리부트 TIL] 3주차 1일 (0) | 2024.06.05 |