directed graph

소개

DFS, BFS, topological sorting, transitive closure, directed graph, graph에 대한 설명입니다.

학교 발표한 자료입니다.

목차

1 Introduction
2. Depth-First Search
3. Transitive Closure
4. Strongly Connected Component
5. Topological Sorting
6 Conclusion
7 References

본문내용

1.1 Directed Graphs
Directed Graph(줄여서 Digraph라고도 함)는 Node와 Edge를 가지는 그래프의 일종이다. Directed Graph라고 부르는 이유는 digraph안의 edge가 방향을 가지고 있기 때문이다. 다시 말해서 digraph의 edge는 Node들을 단방향으로만 연결한다.
2. Depth-First Search(DFS)

2.1 DFS의 정의
DFS는 깊이 우선 탐색을 말한다. root node에서 시작해서 edge가 존재하면 edge를 따라 다음 node로 이동하고 또 그 node의 edge를 따라 이동하는 식으로 탐색하는 방법이다.

2.2 edge의 종류
digraph에서 DFS를 실행하고 나면 DFS forest를 얻을 수 있다. tree가 아니고 forest인 이유는 기본 edge 이외의 다른 종류의 edges들이 있기 때문이다.

참고자료

· -C언어로 설명한 알고리즘 황종선.정영식 공저
· - Web Sites
· http://www.cs.hut.fi/~enu/tc.html
· http://en.wikipedia.org/wiki/Transitive_closure
· http://en.wikipedia.org/wiki/Strongly_connected_component
· http://www.cs.berkeley.edu/~vazirani/s99cs170/notes/lec12.pdf
· http://www.cs.fsu.edu/~cop4531/slideshow/chapter23/23-5.html
· http://en.wikipedia.org/wiki/Topological_sorting
· http://www.cs.sunysb.edu/~algorith/files/topological-sorting.shtml
· http://www.cs.auckland.ac.nz/~ute/220ft/graphalg/
· http://www.nist.gov/dads/HTML/topologcsort.html
· ww3.java2.datastructures.net/presentations/Digraphs.pdf
· www.cse.ucsd.edu/~dasgupta/101/lec3.ps