전체 글140 알고리즘 - 벨만 포드(Bellman-ford) 최단 경로 탐색 알고리즘. 간선 가중치가 음수인 경우에도 적용가능함. 단, 사이클의 가중치 합이 음수인 경우가 존재하는 그래프는 최단 경로를 구할 수 없음. 1. 그래프의 간선정보를 저장. (출발노드, 도착노드, 가중치) 를 저장. 2. 시작 노드를 지정. 3. 모든 정점까지의 거리를 무한대로 설정. 4. 모든 간선을 확인해, 출발노드에서 도착노드로 이동했을때의 거리가 이미 저장된 도착노드까지의 거리보다 짧은경우 거리를 갱신. 거리 = 가중치. dist[v] > dist[u] + w 인 경우, dist[v] = dist[u] + w 로 갱신. 5. 4를 V-1번 반복. V는 노드 수. 6. 음수 사이클여부를 확인하려면 한번더 반복하고, 이때 거리가 갱신되는 노드가 발견되면 음수사이클이 존재함. 2020. 3. 9. 알고리즘 - 다익스트라(dijkstar) 알고리즘 최단 경로를 찾기 위해 사용하는 알고리즘. 하나의 출발점부터 모든 정점으로의 최단 거리를 계산하는 알고리즘. 1. 시작점 결정 2. 전체 거리를 무한대(코드상에서는 0)로 설정. 3. 현재 위치에서 갈수 있는 정점 저장. 전체거리를 최소로 늘릴수 있는 경로를 갱신. 불가능하면 스킵. 4. 선택하지 않았던 정점중 가장 짧은 거리에 있는 정점을 현재 정점으로 갱신. 5. 3~4 번 반복. 단순 구현으로는 시작점에서 각 정점에 대한 거리를 배열에 저장해가면서 각 정점으로의 최단 경로들을 찾아가는 방법이 있다... 10개의 정점을 가지는 그래프라고 가정할때 10개의 요소를 가지는 배열에 순서대로 각 정점에 대한 최단 경로를 저장하는 것. 당연히 자기 자신으로의 경로는 0의 거리를 가진다. 효율적인 구현으로는 우.. 2020. 3. 6. Graph 그래프는 저장된 자료들사이의 관계를 나타내기를 위한 구조. 정점(Vertex) : 자료를 나타내는 단위로 리스트나 트리의 노드와 같은 의미. 간선(Edge) : 정점을 연결하는 선을 의미하며 자료사이의 관계를 나타냄. 가중치(Weight) : 한 정점에서 다른 정점으로 이동하는데 필요한 자원을 나타냄. 즉, 간선의 값. 가중치를 표시하지 않는다면 1로 생각해도 무방. 차수(Degree): 그래프에 연걸된 간선 수. 노드사이의 모든 연결 간선수를 나타냄. - 입력 차수 : 방향성 그래프일때 노드로 들어오는 간선수. - 출력 차수 : 방향성 그래프일때 노드에서 나가는 간선수. 단순 경로 : 그래프의 한 정점에서 다른 정점으로의 경로 중, 모든 정점을 단 한번씩만 방문하는 경로. 사이클(Cycle) : 단순 .. 2020. 3. 5. 알고리즘 - DFS(Depth First Search) 그래프 탐색법 중 하나. 완전탐색이나 백트래킹등 탐색의 횟수, 그래프 경로가 정해져있거나 예측 가능한 경우의 문제에 사용. 1. 선택한 정점에서 해야할 작업 진행. 2. 선택한 정점에서 연결된 정점중 아직 방문하지 않은 정점 방문 3. 더 방문할 정점이 없으면(전부 방문 or 연결 정점 없음.) 이전 정점으로 되돌아감. 4. 1~3 반복. 이전 정점으로 되돌아가는 기능을 위해 Stack을 사용함. -> 재귀함수로도 가능함. 2020. 3. 5. 이전 1 ··· 15 16 17 18 19 20 21 ··· 35 다음