전체 글 (55) 썸네일형 리스트형 그래프 (Graph) - 최단 경로 (Dijkstra, Ford 알고리즘) 최단 경로 가중치 graph, 출발점(source), 종점(destination), 방향 graph 전제 조건 방향 그래프 G = (V, E) n개의 정점 G의 간선에 대한 가중치 함수 lengt(i, j) 출발점 v 문제점 1. 단일 출발점 / 모든 종점 (간선의 길이가 양수인 경우) ex ) 간선 비용 (length) 최단 경로 비용 (dist) Dijkstra 알고리즘 - 비용 모든 가중치가 양수일때만 적용 가능 단계 ① S = 출발점 v를 포함하여 이미 최단 경로가 발견된 정점들의 집합 ② S에 속하지 않는 정점들 중 dist 값이 최소인 정점 u 선택, 이는 S의 원소가 됨 ③ S에 속하지 않는 정점들에 대해 새로운 최단 경로가 존재하는 경우, 해당 정점에 대한 dist 값 갱신 즉, dist[.. Ford 알고리즘 void Graph::AllLengths (const int n) { for (int i=0; i Dijkstra 알고리즘 class 정의 - 정적 생성 class Graph { private: int length[nmax][nmax];// 가중치 int dist[nmax];// 최단 경로 비용 bool s[nmax];// 정점이 S에 포함되었는지의 여부 int n;// 정점 수 public: Graph (const int vertices = 0): n(verticies) {}; void ShortestPath (const int); int choose (const int); } class 정의 - 동적 생성 class Graph { private: int **length; int *dist; bool *s; int n; public: Graph (const int vertices = 0): n(vertices) { leng.. Prim 알고리즘 방법 초기 T의 정점 집합은 하나의 정점만을 포함 트리 T에 인접한 간선들 중 T와 사이클을 형성하지 않는 최소 비용 간선 (u, v)를 T에 추가 T에 n-1개의 간선이 포함될때까지 추가 단계 반복 // G가 최소한 하나의 정점을 가진다고 가정 TV = {0};// 정점 0으로 시작. 간선은 empty // T에 포함되어 있는 양 끝점들을 포함하고 있는 집합 for (T=Ø; T 간선수 < n-1; (u, v)를 T에 추가){ (u, v) = (u ∈ TV) && (v ∉ TV)인 최소 비용 간선 if (그런 간선 없음) break; v를 TV에 추가 } if (T 간선수 < n-1) cout Kruskal 알고리즘 방법 한 번에 하나씩 비용이 가장 적은 간선을 선택하여 T에 이미 포함된 간선들과 사이클을 형성하지 않는 간선들만을 차례로 T에 추가 T에 n-1개의 간선들이 존재하면 멈춤 특징 인접 행렬, 리스트가 아닌 table 사용 E 배열 v w cost T 배열 (0으로 초기화 된 T에 조건 만족하는 i번째 간선 삽입) i 0 0 T=Ø while ( (T가 n-1개 미만의 간선 포함) && (E != empty) ) { E에서 최소 비용 간선 (v, w) 선택 E에서 (v, w) 삭제 if ( (v, w)가 T에서 사이클 미형성 ) T에 (v, w) 추가 else (v,w) 거부 } if (T가 n-1개 미만 간선 포함) cout 그래프 (Graph) - 최소비용 신장 트리 (Minimum Cost Spanning Tree) 신장 트리 연결 그래프 G에서 모든 정점들을 포함하며 tree인 부분 graph 방법 임의의 정점에서 출발하여 DFS 또는 BFS로 graph 탐색 시, 정점 v에서 인접하며 방문되지 않은 정점 w가 존재할 때, 간선 (v, w)의 집합 가중치 무방향 graph에서 신장 트리 비용 = 신장 트리에 포함된 간선들의 비용 최소비용 신장 트리 (Minimum Cost Spanning Tree) - 최소의 비용을 갖는 신장 트리 - ex) Kruskal, Prim, Sollin 조건 그래프 내의 간선들만 사용 n-1개의 간선만 포함 사이클 미포함 Kruskal Prim cycle check O cycle check X 9-2. 그래프 (Graph) - 너비 우선 탐색 (Breadth First Search, BFS) void Graph::BFS (int v){ // 정점 v에서 시작 visited = new bool[n]; for (int i=0; i 너비 우선 탐색 (Breadth First Search, BFS) 너비 우선 탐색 - 연결 graph, 무방향 graph - queue 사용 단계 ① 시작 정점 v 방문 ② v에 인접한 모든 정점들 방문 ③ 새롭게 방문한 정점들에 인접하면서 아직 방문하지 못한 정점들 방문 ④ 더 이상 방문할 정점 없으면 종료 ex) 0 – 1 – 2 – 3 – 4- 5 – 6 – 7 순으로 방문 분석 ① 인접 리스트 사용 리스트 node 수 2e개 만큼 조사 → O(e) 소요 ② 인접 행렬 사용 한 정점에 인접한 정점들 조사하는데에 O(n) 소요 ∴ 전체 원소 조사 → O(n2) 소요 이전 1 2 3 4 5 6 7 다음 목록 더보기
