컴퓨터 이론66 36. Bellman-Ford 알고리즘 벨만-포드 알고리즘이란? 음의 가중치를 가지는 그래프에서 최단거리를 구하는 알고리즘이다. 음의 가중치를 가지는 그래프에서 다익스트라 알고리즘은 사용할 수 없는 것일까? 다익스트라 알고리즘은 각 간선의 가중치가 양수인 경우에만 올바른 결과를 보장하기 때문에 사용할 수 없다. 반면에 벨만-포드 알고리즘은 간선의 가중치가 음수인 경우에도 올바른 결과를 보장한다. 벨만-포드 알고리즘 구현 1. 시작 노드를 선택하고, 시작 노드로부터 모든 노드까지의 최단거리를 무한대로 초기화한다. 이때 시작 노드의 최단거리는 0으로 초기화 한다. 2. 모든 간선에 대해 반복한다. 각 반복에서는, 모든 노드에 대해 최단거리를 갱신한다. 3. 모든 노드에 대해 최단 거리를 갱신한 후, 만약 어떤 노드의 최단거리가 갱신된다면, 해당 .. 2023. 5. 16. 35. Dijkstra 알고리즘 다익스트라 알고리즘이란? 다익스트라 알고리즘은 시작 노드로부터 다른 모든 노드까지의 최단거리를 찾는 알고리즘이다. 이 알고리즘은 그리디 알고리즘의 일종으로, 현재까지 발견된 최단거리가 가장 작은 노드를 선택하여 최단거리를 갱신하는 방식으로 동작한다. 다익스트라 알고리즘 구현 #include #include #include #define MAX_VERTICES 1000 // 최대 노드 개수 #define INF INT_MAX // 무한대 int graph[MAX_VERTICES][MAX_VERTICES]; // 그래프 int dist[MAX_VERTICES]; // 최단거리 int visited[MAX_VERTICES]; // 방문 여부 int dijkstra(int start, int n) { // 초기.. 2023. 5. 15. 34. Prim 알고리즘 Prim 알고리즘이란? Kruskal 알고리즘과 마찬가지로 그리디 알고리즘을 기반으로 하며, 어떤 정점을 선택할 때 그 정점과 연결된 간선 중 최소 비용 간선을 선택하는 방식으로 동작한다. Prim 알고리즘의 동작 방식 1. 임의의 정점을 선택하고 이 정점을 시작점으로 설정한다. 2. 시작점과 인접한 간선 중 최소 비용 간선을 선택한다. 3. 선택한 간선으로 연결된 정점 중 방문하지 않은 정점들 중 최소 비용의 간선을 선택한다. 4. 모든 정점을 방문할 때까지 2, 3 과정을 반복한다. #include #include #define infinity 9999 #define MAX 20 int G[MAX][MAX],spanning[MAX][MAX],n; int prims(); int main() { int .. 2023. 5. 12. 33. Kruskal 알고리즘 Kruskal 알고리즘은 그리디 알고리즘을 사용하여 최소비용 신장 트리를 구하는 알고리즘이다. 이 알고리즘은 그래프의 간선을 가중치의 오름차순으로 정렬한 뒤, 사이클을 생성하지 않는 작은 가중치 간선부터 선택하여 트리를 만드는 방식으로 동작한다. #include #include #define MAX_VERTICES 100 #define MAX_EDGES 100 typedef struct { int start, end, weight; } Edge; int parent[MAX_VERTICES]; int cmp(const void* a, const void* b) { Edge* x = (Edge*)a; Edge* y = (Edge*)b; return x->weight - y->weight; } int find.. 2023. 5. 11. 32. 최소비용 신장 트리 최소비용 신장 트리란? 가중치 그래프에서 모든 정점을 포함하면서 간선의 가중치 합이 최소인 트리를 의미한다. 즉, 그래프에서 일부 간선을 선택하여 트리를 만들었을 때, 선택한 간선의 가중치 합이 최소인 트리를 구하는 것이다. 최소비용 신장 트리를 사용하는 이유? 네트워크 설계, 회로 기판 설계, 도로 건설 등 다양한 분야에서 활용된다. 최소비용 신장 트리를 찾는 알고리즘은? Kruskal, Prim, Sollin 알고리즘이 있으며 앞으로 이 3가지 알고리즘에 대해서 알아보고자 한다. 2023. 5. 11. 31. 단절점 단절점이란? 그래프에서 단절점이란 그래프를 두 개 이상의 연결 요소로 분할하는데 필요한 정점이다. 즉, 단절점을 제거하면 그래프가 더 이상 연결되지 않거나, 두 개 이상의 연결 요소로 분할된다. 단절점 찾기 단절점을 찾기 위해서는 그래프를 탐색하면서 해당 정점을 제거했을 때 그래프가 분리되는지를 확인해야 한다. DFS를 이용하여 단절점을 찾을 수 있다. #include #include #include #define MAX_SIZE 100 int adj[MAX_SIZE][MAX_SIZE]; // 인접 행렬 bool visited[MAX_SIZE]; // 방문 여부 배열 int dfn[MAX_SIZE]; // 정점 발견 순서 int low[MAX_SIZE]; // 정점의 low 값 // n: 정점 개수, m.. 2023. 5. 10. 이전 1 ··· 3 4 5 6 7 8 9 ··· 11 다음