알고리즘(Algorithm)/그래프(Graph) (7) 썸네일형 리스트형 [그래프]길찾기 bfs 알고리즘(maze algorithm) 자료구조 그래프에서 모든 정점을 순회하기 위한 방법으로 너비우선탐색(BFS, Breadth First Search) algorithm 과 깊이우선탐색(DFS, Depth First Search) 알고리즘을 알아 봤었다. 이 bfs 와 dfs 알고리즘은 길찾기 (미로 탈출) 에도 유용하게 사용되는데 이 post 는 bfs 를 통해 길찾는것을 설명하겠다. 우선 그림 1과 같은 미로가 있다고 가정하자. 설명을 빨리 하기위해 매우 단순한(?) 미로를 선택하였다. 미로를 자료로 표현하기 위해 graph 로 표현할수 있지만 행렬(matrix)로 도 가능하다. 여기서는 행렬로 하겠다. 7X7 미로인 위 그림을 행렬로 표현하면 다음과 같다. 0 1 2 3 4 5 6 0 1 1 1 1 1 1 1 1 1 0 0 1 0 0.. [그래프] 그래프에서 사이클 찾는 방법들(Detect Cycle in an Graph) Q. 그래프에서 사이클이 이란 ? 그래프의 특정 정점에서 출발하여 돌아다니다가 다시 처음 출발했던 곳으로 되돌아 갈 수 있으면 사이클이 있다고 한다. 그림1에서 (a)는 Tj(출발) → Tn → Tm → Tj(출발지점으로 다시 돌아옴) 으로 순환되는 사이클이 있지만 (b)는 어디에서 출발하던 출발지점으로 다시 돌아올수 있는 방법이 없다. 즉 사이클이 존재하지 않는다. [출처] https://www.researchgate.net/figure/Example-of-cyclic-and-acyclic-graphs_fig2_2431833 Q. 사이클을 찾는다는 것은? 사이클을 검출(detect) 한다는 것은 그래프내에 사이클이 있는가? 있다면 총 몇 개 존재하는가 ? 그리고 사이클에 포함된 노드의 개수는 몇 개인가.. [그래프] 위상 정렬(Topological Sort) - Kahn's algorithm 방향 비싸이클 그래프(DAG, Directed Acyclic Graph) 는 보통 작업간의 우선순위를 표현하는 용도로 사용된다고 했다. 그런데 그래프에서 작업들을 어떤 순서로 해야하는지 알아야 하는데 어떻게 할 수 있을까 ? 예를들어 아래와 같은 DAG 가 있고 7부터 작업을 시작한다면 7 다음에 5를 할지 6을 할지 그 순서를 정해야 한다. 이와 같이 일어나야 할 순서에 따라 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상정렬(Topoligical Sort)을 이용할 수 있다. 그림 1)을 위상정렬 하면 그 순서는 7 6 5 4 3 2 1 0로 출력된다. 그럼 실제로 정렬시 작업이 우선순위에 맞는지 즉, 유효한 순서가 되기 위해서 어떤 조건을 만족해야 할까? 당연한 건데 작업의 순서는 .. [그래프] 모든 정점의 indegree 계산 방향그래프(Directed Graph) 구현에서 보다시피 모든 정점의 indegree 를 계산하는 방법은 에지가 추가될 때마다 미리 계산되어질수 있다. 예를들어 v -> w 에지가 추가된다면 w 인덱스에 indegree 의 카운트를 하나 증가 (14번 라인) 시키면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 // indegree[v] 는 정점 V의 incoming edge = indegree의 개수를 저장한다. private int[] indegree; ... public void addEdge(int v, int w) { validateVertex(v); validateVertex(w); // 무방향 그래프이니 역뱡향도 추가하였는데 방향그래프에서는 명확.. 그래프(Graph)-너비우선탐색(BFS, Breadth First Search) algorithm 지금까지 그래프란 무엇이고 그래프를 표현하기위한 방법으로 인접행렬과 인접리스트를 알아보았다. 이번에는 그래프의 모든 정점(노드)들을 방문하는 순회(traversal)에 대해서 알아보려고한다. 그래프의 일종인 트리에서도 이미 순회하는 방법을 알아 보았는데 pre-order, in-order, post-order, level-order 가 있었다. 그래프에서는 모든 정점들을 순회하기위한 방법은 여러가지가 있지만 대표적으로 2가지가 있는데 하나는 너비우선탐색(BFS, Breadth First Search)이고 다른 하나는 깊이우선탐색(DFS, Depth First Search)이다. △ [출처] https://neo4j.com/blog/graph-algorithms-neo4j-graph-algorithm-co.. 그래프(Graph)-깊이우선탐색(DFS, Depth First Search) 그래프를 순회하기위한 방법중 너비우선탐색(BFS, Breadth First Search) 은 알아봤고 이번에는 깊이우선탐색(DFS, Depth First Search)알고리즘을 살펴보자. 깊이우선탐색(DFS, Depth First Search)은 이진트리의 전위순회(pre order)과 비슷한 개념이고 재귀나 스택(Statck)를 이용하여 알고리즘을 구현할 수 있다. △ [출처] https://www.tutorialspoint.com/data_structures_algorithms/depth_first_traversal.htm 위에서 주어진 예제에서와 같이 DFS 알고리즘은 S에서 A에서 D로 G에서 E에서 B로, F에서 마지막으로 C로 이동한다. DFS를 스택를 이용하여 구현할 수 있다고 하였는데 코드.. 최소신장트리(Minimum Spanning Tree)-크러스컬(Kruskal) 알고리즘 최소신장트리를 생성하기위한 알고리즘으로 크러스컬 알고리즘을 설명한다. 만약 최소신장트리가 무엇인지 모른다면 최소신장트리(Minimum Spanning Tree) 를 먼저 학습해야한다. Q. 크러스컬 알고리즘은 무엇인가 ? 크러스컬 알고리즘은 최소신장트리를 생성하기위한 알고리즘 중하나로 핵심은 모든 그래프 G 에 연결된 모든 에지들의 가중치를 오름차순으로 정렬하고 에지 중 가장 작은 것부터 하나씩 이어 나가는 방법이다. 주의 할 점은 이어 붙일 때 그래프에 사이클이 생기지 않도록 해야(신장트리가 되려면 사이클이 없다고 얘기했다.) 한다는것이다. 그림으로 설명하면... STEP (a) 그래프에서 에지의 가중치가 가장 작은 E = (h,g)를 젤 먼저 선택한다. 이어서 가중치가 낮은 순서대로 하나씩 선택해 나.. 이전 1 다음
