Floyd Algorithm - 모든 정점 사이의 최단 경로 - Dijkstra : 정점의 수 n개 만큼 반복 실행 - Floyd : 한 번에 찾아 준다 - 인접 행렬 weight[][] 2차원 배열에 대한 3중 반복 루프 - O(n³) Ak[i][j]를 0~k까지의 정점만을 이용한 정점 i~j까지의 최단경로 원하는 최종 결론 : An-1[i][j] A-1 → A0 → A1 → ..... → An-1순으로 최단거리 구하기 ▶ Floyd Algorithm Code int A[MAX_VERTEX][MAX_VERTEX]; void floyd(graph* g) { for (int i = 0; i n; i++) { for (int j = 0; j n; j++) { A[i][j] = g->weig..

Prim VS Dijkstra - 전체적인 틀은 BFS와 유사 Prim 각 정점의 distance는 집합 S에 존재하는 정점과 연결하는데 발생하는 weight → 각 정점의 weight는 여러 번 바뀐다 → 시작 정점 v ~ 모든 정점에 도달하는 최소비용 계산 Dijkstra 시작 정점 v ~ 모든 정점까지의 최단 거리 계산 Prim : 집합 S에서 해당 정점까지의 거리 (S ~ v) DIjkstra : 집합 S의 시작정점 r에서 해당 정점까지의 가장 짧은 거리 (S(r) ~ v) 알고리즘 비교 Prim void prim_mst(graph* g, int v) { // v = 시작 정점 init_distance(distance); init_selected(selected); distance[v] = 0; ..

최단경로 - 정점 i ~ 정점 j까지 간선들의 weight 합이 최소가 되는 경로 Dijkstra 하나의 시작 정점 ~ 모든 다른 정점까지의 최단 경로 Floyd 모든 정점 ~ 다른 모든 정점까지의 최단 경로 Dijkstra Algorithm - 탐욕적 방법 (greedy method) 이용 - 특정 시작 정점 ~ 다른 모든 정점까지의 최단 경로 계산 - 가중치가 음수가 아닐 때 정상적으로 작동 - Dijkstra → Greedy → DP(최단경로 + 길찾기) / 매 상황에서 가장 비용이 적은 최선의 정점 선택 - 시작정점으로부터 거리를 저장하는 distance[] 1차원 배열이 필요 - O(n²) 시작 정점(v) 선택 시작 정점으로부터 다른 모든 정점까지의 distance 업데이트 (한 번에 갈 수 없..

Prim MST Algorithm - 시작 정점에서부터 신장 트리 집합을 확장해가는 알고리즘 - 인접 정점들 중에서 가중치가 최소인 정점을 선택해가면서 트리를 확장 이전 단계에서 만들어진 신장 트리를 확장 - n개의 정점에 대해서 n-1개의 간선을 선택하면 알고리즘 종료 - 배열로 구현 or 최소히프로 구현 - 어떤 정점에서 시작하던간에 똑같은 트리 생성 - O(n²) ※ 각 정점으로부터 거리 distance 배열, 선택된 정점 selected 배열 (모든 정점 distance = INF로 초기화) v의 인접 정점들 distance 업데이트 인접 정점들 중 distance가 가장 낮은 정점(w) 선택 v와 w를 하나의 그룹으로 간주하고 해당 그룹으로부터 distance 다시 업데이트 n-1개 간선 선택할..

신장 트리 (Spanning Tree) - 그래프의 모든 정점들을 포함하는 트리 - 모든 정점들이 연결되어 있어야 하고, 사이클을 포함하면 안된다 최소 신장 트리 (Minimum Spanning Tree) - 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장트리 - 모든 정점들을 가장 적은 수의 간선, 비용으로 연결 - n개의 정점들에 대해 반드시 n-1개의 간선만 사용 + 사이클 포함 X ex) 도로 건설, 전기 회로, 통신, 배관,.... Kruskal Algorithm, Prim Algorithm Kruskal MST Algorithm - 탐욕적 방법 (greedy method) 이용 - 간선을 기반으로 하는 알고리즘 - 간선의 개수 e개 → O(|e|log₂|e|) - 매 선택마다 최선의..

BFS(stack) VS DFS(queue) BFS : 깊이 우선 탐색 - stack or 순환으로 구현 DFS : 너비 우선 탐색 - queue로 구현 #include #include // 인접 리스트(BFS - 스택 / DFS - 큐) #define MAX_VERTEX 50 #define TRUE 1 #define FALSE 0 typedef int element; // 그래프 구현 typedef struct graphnode { int vertex; struct graphnode* link; }graphnode; typedef struct graph { int n; graphnode* list[MAX_VERTEX]; }graph; int visited[MAX_VERTEX]; void init_vis..

BFS(stack) VS DFS(queue) BFS : 깊이 우선 탐색 - stack or 순환으로 구현 DFS : 너비 우선 탐색 - queue로 구현 #include #include // 인접 행렬 (BFS-스택 / DFS-큐) #define MAX_VERTEX 50 #define TRUE 1 #define FALSE 0 typedef int element; typedef struct graph { int n; // 정점 개수 int vertex[MAX_VERTEX]; // 정점 저장 배열 int matrix[MAX_VERTEX][MAX_VERTEX]; }graph; int visited[MAX_VERTEX]; void init_visited(int arr[]) { for (int i = 0; i <..

BFS - 너비 우선 탐색 - 원형큐로 구현 - 인접 행렬 : O(n²) (정점 n개) - 인접 리스트 : O(n+e) (정점 n개, 간선 e개) 시작 정점으로부터 거리가 d인 정점들을 모두 방문 (d=1) 그 다음에 거리가 d+1인 정점들을 모두 방문 d+2 / d+3,.... 정점들을 차례대로 방문 거리가 0인 시작 정점(v)을 방문 v로부터 거리가 1인 정점 모두 방문 v로부터 거리가 2인 정점 모두 방문 마지막 정점 방문할 때 까지.,.... 인접 행렬로 구현한 BFS Queue : bfs_mat_queue(graph* g, int v) 큐 생성 v 방문완료 표시 v를 큐에 enqueue 큐에서 dequeue (정점 v dequeue) -- (1) dequeue된 정점 v의 인접 정점(w)들을 방..

DFS - 깊이 우선 탐색 - 인접 행렬(순환/stack), 인접 리스트로 구현 - 어떤 노드를 방문했는지 검사를 무조건 해줘야 한다 (검사를 안해주면 무한 루프에 빠진다) 검사를 위한 배열 int visited[MAX_VERTEX] → dfs 시작할 때, 전부 FALSE로 초기화 - 인접 행렬 : O(n²) (정점 n개) - 인접 리스트 : O(n+e) (정점 n개, 간선 e개) 인접 행렬로 구현한 DFS 1. 순환 : dfs_mat_recur(graph* g, int v) 정점 v에서부터 dfs 시작 v는 방문완료니까 visited배열에 TRUE 표시 v의 인접 정점 w에서 탐색 시작 -- (1) matrix[v][w] == 1 (인접)이고, visited[w] == FALSE (방문 X)이면, 정점..

그래프 탐색 방법 DFS (Depth First Search) : 깊이 우선 탐색 BFS (Breath First Search) : 너비 우선 탐색 DFS ≒ 전위/중위/후위 순회 BFS ≒ 레벨 순회 DFS (Depth First Search) - 깊이 우선 탐색 - 한 방향으로 끝까지 진행 - 더 이상 갈 곳이 없으면, 가장 가까운 곳으로 다시 되돌아가서(backtracking) 해당 지점에서부터 다시 탐색을 시작 ▶ 구현 방법 1. 인접 행렬 2. 인접 리스트 순환 호출 사용 stack 사용 : 인접 정점들을 stack에 저장했다가 꺼내서 다시 탐색 BFS (Breath First Search) - 너비 우선 탐색 - 현재 정점으로부터 가장 가까운 노드를 먼저 방문 - 멀리 떨어져 있는 정점은 나중..

그래프의 표현방법 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용 인접 리스트(Adjacency List) : 연결 리스트를 사용 인접 리스트 - 각 연결 리스트들의 노드는 인접 정점들을 저장 - 각 연결 리스트들은 헤더 노드를 보유 → 헤더 노드는 배열로 구성 → 배열의 인덱스를 이용해서 각 정점의 연결 리스트에 접근 그래프 인접리스트 구현 #define MAX_VERTEX 50 typedef struct graphnode { int vertex; // 각 노드의 정점 struct graphnode* link; // 정점들간에 연결해주는 link }graphnode; typedef struct graph { int n; // 정점의 개수 graphnode* list[MAX_VERTEX..

그래프의 표현방법 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용 인접 리스트(Adjacency List) : 연결 리스트를 사용 인접 행렬 - 정점의 수 n개에 대해 n×n의 2차원 배열로 구성 - 간선 (i, j)가 그래프에 존재하면 m[i][j] = 1 - 간선 (i, j)가 그래프에 없으면 m[i][j] = 0 - n개의 정점이 존재하면 n²개의 메모리가 필요 → 메모리 낭비가 크다 - 간선이 매우 많은 밀집 그래프에는 적합하다 - 간선이 적은 희소 그래프의 경우에는 메모리 낭비가 크므로 적합하지 않다 무방향 그래프 = 행렬이 대칭으로 구성 그래프 인접행렬 구현 #define MAX_VERTEX 50 typedef struct graph { int n; // 정점의 개수 coun..