Coding Diary

1. 개념 정점(노드)과 간선(에지)으로 이루어진 자료구조. 정점은 고유한 식별자를 가지고 있고, 간선은 정점들끼리의 관계를 나타낸다. 2. 종류 1) 방향 그래프 간선에 방향성이 있는 그래프를 의미한다. A에서 출발해서 B로 가는 간선이 존재한다면 이는 A에서 B로 가는 방향을 가진 간선이고, 이러한 정점과 간선을 모아 놓으면 방향 그래프이다. A에서 B로는 갈 수 있지만, B에서 A로 가는 길은 없다. 2) 무방향 그래프 간선에 방향이 없다. A에서 B가 연결되어 있으면 출발과 도착이 없고 그냥 둘이 연결 된 거다. A에서 B로 갈 수 있고, B에서 A로도 갈 수 있다. 3) 가중치 그래프 A와 B가 연결이 되어 있는데 그 연결된 간선에 가중치가 부여된 것이다. 이러한 가중치는 두 정점 사이의 거리,..

1. 에지 리스트 1) 개념 에지 리스트는 에지를 중심으로 그래프를 표현한다. 2차원 배열에 각 에지의 출발 노드와 도착 노드를 저장한다. 만약 가중치가 있는 에지일 경우 각 에지의 출발 노드, 도착 노드, 가중치를 저장한다. 2) 종류 ⓛ 가중치가 없는 에지 int[2][6] edgeList = {{1,2},{1,3},{2,5},{2,4},{3,4},{4,5}}; ② 가중치가 있는 에지 int[2][6] edgeList = {{1,2,4},{1,3,1},{2,5,2},{2,4,1},{3,4,7},{4,5,4}}; + 만약 방향이 없는 에지면 {1,2}와 {2,1}은 같은 것이니 둘 중 하나만 저장하면 된다. 3) 특징 구현하기가 쉽다 에지만 딱 나와있기 때문에 특정 노드가 어떤 에지와 연결되어 있는지,..

1. 개념 주어진 어떤 정점을 출발하여 체계적으로 그래프의 모든 정점들을 순회하는 것을 그래프 순회라고 한다. DFS는 그래프를 순회하는 방법 중 하나이다. DFS는 시작 노드부터 출발해서, 시작 노드와 인접한 것 중 하나를 방문한다. 그리고 그 방문한 것과 인접한 것을 또 방문한다. 이렇듯 시작 노드부터 인접한 것을 따라 계속 그걸 방문해나가는 방법이다. 마치 아래 방향으로 쭉 깊이있게 탐색하는 것 같다. 만약, 더 이상 방문할 것이 없다면 이전 노드로 돌아와서 이전 노드와 인접해 있지만 아직 방문하지 않은 노드를 방문해 나간다. 2. 예시 위와 같은 그래프를 DFS로 방문하면 다음과 같다. 같은 단계일 경우 오름차순으로 노드를 방문한다. 1 -> 2 -> 6 -> 8 -> 3 -> 5 -> 4 -> ..