🗒️ 그래프 (12)

1. 2022.06.04 [Python] 그래프(Graph)

   그래프(Graph) 그래프(Graph)의 기본 그래프의 개념 그래프(Graph) : 여러 노드가 서로 연결된 자료구조 루트에서 하위 노드 방향으로만 이어지는 트리와 달리, 여러 노드가 연결되어 있을 수 있다. 트리도 그래프의 일종이지만, 트리와 그래프를 구현하는 코드 등이 확연히 다르기 때문에 이 둘은 별도로 생각하는 편이 낫다. 그래프의 종류 그래프는 정점을 연결하는 간선의 방향성 여부에 따라 방향 그래프와 무방향 그래프로 나눈다. 간선에 가중치(Weight)를 부여하여 가중치 그래프도 만들 수 있다. 무방향 그래프 트리의 노드(Node)에 해당하는 용어가 그래프에서는 정점(Vertex)이다. 정점을 연결하는 선은 간선(Edge)이므로 그래프는 정점과 간선의 집합으로 볼 수 있다. 그래프에서 정점은 V..
2. 2022.04.12 [Python] 파이썬을 이용하여 함수 그래프 그리기 (NumPy, matplotlib.pyplot)

   파이썬을 이용하여 함수 그래프 그리기 (NumPy, matplotlib.pyplot) 개요 파이썬의 넘파이(NumPy)와 matplotlib.pyplot을 사용하여 간단하게 그래프를 그릴 수 있다. 방법 코드 import numpy as np import matplotlib.pyplot as plt # (1) X축의 범위(Range) 설정 (입력) start = -10 # 시작점 # 입력 end = 10 # 끝점 + 1 # 입력 interval = 1 # 간격 # 입력 x = np.array(range(start, end, interval)) # print('X: ', x) # X 축의 범위를 확인하고 싶을 경우 주석 해제 # (2) 그래프의 축 이름 설정 name_X = 'Axis-X' # 입력 nam..
3. 2021.07.04 코사라주 알고리즘(Kosaraju's Algorithm)

   코사라주 알고리즘(Kosaraju's Algorithm) 그래프에서 강한 연결 요소를 찾는 가장 쉽고 널리 사용되는 방법 DFS를 2번 수행하는 형태로 동작함. ① 입력 그래프 자체에 DFS를 수행함. ② 입력 그래프를 전치하여 DFS를 수행함. 코사라주 알고리즘은 일반적으로 DFS 방식 의 순회를 사용하지만, BFS 도 사용할 수 있음. DFS 방식이 전통적인 방식 복잡할 수 있는 문제를 직관적으로 단순화하는 측면에서 매우 효과적이며, 구현하기도 쉬운 편임. 입력 그래프가 인접 리스트 로 표현되어 있을 경우, O(V + E) 형태의 선형 점근적 시간 복잡도 를 갖기 떄문에 매우 효율적임. 코사라주 알고리즘에서 인접 행렬 을 사용하는 것은 권장되지 않음. 그래프 순회에서 각 정점의 이웃을 찾기 위해 상당..
4. 2021.07.02 벨만-포드 알고리즘(Bellman-Ford Algorithm)

   벨만-포드 알고리즘(Bellman-Ford Algorithm) 음수 가중치가 있는 그래프를 다룰 때 사용하는 알고리즘 그래프의 모든 에지에 대해 다익스트라의 그리디 선택 방법을 (V - 1)번 반복하여 점진적으로 최단 거리를 찾음. V : 정점의 개수 다익스트라 알고리즘보다 높은 점근적 시간 복잡도를 가짐. 다익스트라 알고리즘이 잘못 해석할 수 있는 그래프에 대해서도 정확한 결과를 제공함. 코드 1 음수 가중치 사이클 이 없을 경우 #include #include #include using namespace std; struct Edge { int src; int dst; int weight; }; const int UNKNOWN = INT_MAX; vector BellmanFord(vector edge..
5. 2021.06.30 프림의 최소 신장 트리 알고리즘(Prim's Minimum Spanning Tree Algorithm)

   프림의 최소 신장 트리 알고리즘(Prim's Minimum Spanning Tree Algorithm) MST 문제 정점 집합 V의 가중치를 갖는 에지 집합 E로 구성된 그래프 G = 가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하는 문제 크루스칼 알고리즘(Kruskal Algorithm) 그래프의 모든 에지를 최소 힙 에 추가하고, 사이클을 만들지 않는 최소 가중치의 에지를 이용하여 MST를 구성함. 프림 알고리즘(Prim's Algorithm) BFS의 동작 방식과 유사함. 먼저 시작 정점을 이용하여 경계를 구성함. 경계는 이전에 방문했던 정점들에 의해 구성됨. 현재 경계에 인접한 정점을 반복적으로 탐색함. 이때 프림 알고리즘은 경계를 관통하는 에지 중에서 가장..
6. 2021.06.30 깊이 우선 탐색(DFS, Depth-First Search)

   깊이 우선 탐색(DFS, Depth-First Search) 너비 우선 탐색(BFS, Breadth-First Search) 시작 장점에서 시작하여 점차 탐색 범위를 넓혀 나가는 방식 방문하지 않은 정점을 저장하기 위해 큐(Queue) 를 사용함. 선입선출(FIFO) 자료구조 큐에 있는 정점들은 큐에 들어갔던 순서대로 제거됨. 이러한 큐의 속성을 이용하여 시작 정점에 가까이 있는 정점들을 먼저 처리할 수 있음. 시간 복잡도 : O(V + E) 깊이 우선 탐색(DFS, Depth-First Search) 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식 더 방문할 정점이 없어지면, 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복함. 이러한 그래프 탐색 방..
7. 2021.06.30 너비 우선 탐색(BFS, Breadth-First Search)

   너비 우선 탐색(BFS, Breadth-First Search) 시작 정점을 경계(Frontier)에 추가하는 것으로 시작함. 경계는 이전에 방문했던 정점들 에 의해 구성됨. 현재 경계에 인접한 정점을 반복적으로 탐색함. 시간 복잡도 : O(V + E) V : 정점의 개수 E : 에지의 개수 모든 정점에 대해 자식 정점을 손자 정점보다 먼저 방문한다 는 점이 중요한 특징 BFS를 구현할 경우, 보통 경계를 별도의 자료구조로 만들어서 명시적으로 사용하지는 않음. 대신 정점 ID를 큐(Queue) 에 저장하여 시작 정점과 가까운 정점을 멀리 있는 정점보다 먼저 방문할 수 있도록 구현함. 동작 과정 ① 먼저 시작점인 우리집 정점을 방문함. 빨간색 점선 : 현재 경계 인접한 정점으로 R1과 R2가 있음. ② R..
8. 2021.06.28 그래프 순회 문제(Graph Traversal Problem) ; 그래프 탐색 문제(Graph Search Problem)

   그래프 순회 문제(Graph Traversal Problem) ; 그래프 탐색 문제(Graph Search Problem) 그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제 그래프 순회 문제를 수학적으로 표현할 경우 그래프 G = 가 주어질 떄, 특정 정점 s로부터 시작하여 모든 정점 v ∈ V를 방문하는 문제라고 할 수 있음. 그래프 순회 문제는 그래프에서 특정 정점을 찾기 위한 용도 로 사용될 수 있기 떄문에 그래프 탐색 문제(Graph Search Problem) 라고도 부름. 여러 그래프 탐색 알고리즘이 존재하고, 각각은 서로 다른 순서로 모든 정점을 방문함. 종류 너비 우선 탐색(BFS, Breadth-First Search) 깊이 우선 탐색(DFS, Depth-First Sea..
9. 2021.06.27 웰시-포웰 알고리즘(Welsh-Powell Algorithm)

   웰시-포웰 알고리즘(Welsh-Powell Algorithm) 차수(Degree) 가 높은 정점부터 차례대로 그래프 컬러링을 수행하는 방법 다음의 순서를 따름. ① 단계 모든 정점을 차수에 대한 내림차순으로 정렬하고 배열에 저장함. ② 단계 정렬된 배열에서 색상이 지정되지 않은 첫 번째 정점을 선택하고, 이 정점과 연결된 모든 정점을 조사하여 아직 사용되지 않은 색상을 해당 정점에 지정함. 이 색상을 C라고 지칭하겠음. ③ 단계 정렬된 배열에서 색상이 지정되지 않은 정점을 모두 찾고, 만약 이 정점의 이웃이 C 색상을 가지고 있지 않다며 해당 정점에 C 색상을 지정함. ④ 단계 배열에 색상이 지정되지 않은 정점이 남아 있다면 ②단계로 이동함. 남아 있는 정점이 없다면 종료함. 이때까지 정점에 지정된 색상..
10. 2021.05.19 [C++] 인접 리스트를 이용하여 그래프 구현하기

    인접 리스트를 이용하여 그래프 구현하기 서론 인접 리스트(Adjacent List)를 이용하여 그래프(Graph)를 구현해보자. 코드 #include #include #include enum class city : int { MOSCOW, LONDON, SEOUL, SEATTLE, DUBAI, SYDNEY }; std::ostream& operator
11. 2021.05.19 [C++] 인접 행렬을 이용하여 그래프 구현하기

    인접 행렬을 이용하여 그래프 구현하기 서론 인접 행렬(Adjacent Matrix)을 이용하여 그래프(Graph)를 구현해보자. 코드 #include #include enum class city : int { MOSCOW, LONDON, SEOUL, SEATTLE, DUBAI, SYDNEY }; std::ostream& operator
12. 2017.06.19 [C] 그래프(Graph)

    그래프(Graph) [그래프란?] - 그래프(graph) : 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조. 예) 지도 - 지도를 그래프로 표시하면 하나의 도시에서 다른 도시로 갈 때 최단 거리 경로가 어떤 것인지를 알고리즘을 이용해 쉽게 찾을 수 있음. - 운영 체제에서 프로세스와 자원들이 어떻게 연관되는지를 그래프로 표현하게 되면 시스템의 효율이나 교착 상태 유무 등을 알아낼 수 있음. - 그래프는 많은 문제들을 표현할 수 있는 훌륭한 논리적 도구. - 선형 리스트나 트리의 구조로는 복잡한 문제들을 표현할 수 없음. - 그래프 구조는 인접 행렬이나 인접 리스트로 메모리 에 표현되고 처리될 수 있으므로 광범위한 분야의 다양한 문제들을 그래프로 표현하여 컴퓨터 프로그래밍에 의해 해결할 수 있..