CS15 Fundamentals of Data Structures - AOV(Topological Sort) #AOV : A directed graph G in which the vertices represent tasks or activities and the edges represent precedence relations between tasks is an activity-on-network or AOV network. #Topological order : A topological order is a linear ordering of the vertices of a graph such that, for any two vertices i and j, if i is a predecessor of j in the network, then i precedes j in the linear ordering. #Hea.. 2015. 8. 23. Fundamentals of Data Structures - Shortest Path Algorithm 2 #Bellman and Ford Algorithm- 시작점으로부터 각 정점까지의 최단경로의 거리를 구할 수 있다. 벨만포드 알고리즘은 다익스트라 알고리즘과 달리 음수값을 계산할 수 있으며, 음수에 의한 사이클의 여부를 확인할 수 있다. 만약 사이클이 있다면, 해당 최단경로의 거리를 구하지 못한다.- 다익스트라와 비슷하게, 초기의 distance값은 무한대로 설정하며, 1번 루프시에는 간선의 길이가 1, 즉, 시작점으로부터 가장 인접한 정점과의 거리값을 distance에 저장한다.- 루프가 반복될때마다 처리하는 간선의 길이는 1씩 늘어나며, 루프가 실행될때마다 본래 distance의 값보다 작은 거리의 값이 있으면 갱신한다. 루프는 정점 - 1 만큼 반복한다.- 루프가 끝나면, 다시 한 번 최단거리가 없는.. 2015. 8. 19. Fundamentals of Data Structures - Shortest Path Algorithm #Dijkstra - Dijkstra는 Prim Algorithm이랑 매우 비슷하며, 구현된 코드 또한 별반 다르지 않다. info. found[v] : src로부터 v까지 해당하는 경로가 최단경로일때 v는 found에 속하게 되며, 이는 최종적인 경로이다. 최단경로가 아닐경우 found에 속할 수 없다.distance[dest] : src로부터 dest까지 거리를 뜻한다.1. found 집합을 만든다.2. 초기 distance[]는 src와 인접한 정점들로 거리의 값을 매긴다.2-1. 이 때, 거리가 없을 경우, 매겨진 거리보다 훨씬 큰 값으로 값을 매겨서 계산에 지장이 없게끔 한다.2-2. src - src의 거리는 0이며, 초기 src는 최단경로집합에 속한다.3. 집합이 모든 정점들을 속하지않는한 .. 2015. 8. 18. Fundamentals of Data Structures - Minimum Cost Spanning Trees #Minimum Cost Spanning Tree : 가장 작은 비용를 가지는 신장 트리. #Greedy method ; 매번 선택을 할 때마다 가장 최선의 선택을 하는 것. 최소비용신장트리를 구현하기전에 몇 가지 규칙이 있다. 1. 그래프상에서는 간선만을 사용한다. 2. (최대 정점수 - 1) = (간선의 수)만큼의 간선을 사용한다. 3. Cycle이 생기지않게 한다. #Kruskal's Algorithm : 가장 작은 비용을 가지는 간선부터 계속해서 추가한다. 추가하는 도중에 사이클을 만드는 간선이 있으면 추가하지않고 버린다. 모든 간선이 처리되면, 간선의 수를 확인한다. 이 때, 간선의 수가 최대 정점수 - 1 만큼이 아니면 최소신장트리는 없다고 출력하고 그렇지 않으면 최소비용과 경로를 출력한다. .. 2015. 8. 11. Fundamentals of Data Structures - Elementary Graph Operations #Depth First Search: 링크드 리스트를 기본적으로 사용하며, 한 정점을 시작하여, 이 정점과 인접한, 즉, 연결된 노드들 순서대로 방문한다. (이 때, 순서는 리스트에 삽입된 순서임으로 어떠한 순서로 삽입되느냐에 따라 DFS를 실행했을 때 결과가 달라진다.) 방문한 정점이 이미 방문했던 정점이라면 다음 정점을 방문한다. 방문한 정점이 방문하지 않았던 정점이면 해당 정점을 시작으로 처음 정점의 과정을 되풀이한다. 이 때 사용하는 ADT는 스택으로 방문하지 않은 정점들을 방문할 때마다 stack에 쌓는다. 방문이 모두 완료되면(해당 정점에 연결된 모든 노드들을 방문하면), 스택에서 빠진다. 이 때 스택은 함수 호출에 의한 스택으로 사용자가 직접 설정하는 리스트 기반의 스택과는 다르다. 따라서,.. 2015. 8. 11. Fundamentals of Data Structure - Graph #Graph : G 로 표기하며, V (nonempty set of verticex) 와 E (edges)로 구성된 셋이다. - Euler path : 그래프 내의 vertex의 degree가 모두 짝수인 경우, Euler path가 성립한다. - Undirected graph(오른쪽 그림) / Directed graph (왼쪽 그림) - directed graph에서 위 그림의 a 와 c 처럼 직접적인 path가 있으면, a 와 c의 관계를 strongly connected라 한다. - undirected graph에서 두 vertex사이에 직접적이든 다른 vertex들을 거쳐가든 이어져있기만 하면, 둘의 관계를 connected라 한다. - graph는 기본적으로 adjacency matrix와 ad.. 2015. 8. 10. 이전 1 2 3 다음
