그래프2 [graph]위상정렬 위상 정렬이란?DAG(Directed Acyclic Graph), 즉 방향 사이클이 없는 방향그래프에서 노드들의 순서화를 진행하는 것을 말한다. 즉 노드들간의 순서를 정렬한다는 의미이다. 위상정렬 알고리즘첫번째TopologicalSort(G) {for 1 to n{indegree가 0인 임의의 정점 u를 선택A[i] 2017. 7. 25. [graph] BFS,DFS graph를 나타내는 2가지 방식인접 행렬(Adjacency matrix)nxn 형태의 행렬로 나타냄. M(i,j)는 정점 i와 j를 연결하는 간선이 존재한다는 의미가 된다. 무방향그래프라면 i와 j가 서로 연결된 상태이며 M(i,j)=M(j,i)인 상태이다.저장공간은 O(n^2)이며, 어떤 노드 v에 인접한 모든 노드를 찾는것은 행렬의 한 row를 전부 탐색하는 것과 같기 때문에 O(n)이고, 어떤 간선 E(u,v)가 존재하는지 확인하는 것은 M(i,j)를 확인하면 되므로 O(1)이다.인접 리스트(Adjacency list)정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결리스트이다. 예를 들면 간선 E(1,2), E(1,5), E(5, 4)가 존재한다고 할 때 정점의 배열의 원소 중.. 2017. 7. 23. 이전 1 다음