Intro to Computational Thinking and Data Science 4
그래프는 네트워크를 표현하는 것 뿐만 아니라, state 를 표현할 수 있다. Nodes represent states of system Edges represent actions that cause a change of state 그러면 그래프 문제는...
graph
Graph Challenges, Minimum Spanning Trees, Shortest Paths
Graph Process Challenge 1 Is a graph bipartite? 그래프가 bipartite 인가 하는 문제는, 그래프의 노드를 이렇게 두 그룹으로 나눌 수 있느냐 하는 문제다. (http://en.wikipedia.org) 알고리즘이 얼마나 어려운가는 이렇게...
Graph Search and Connectivity
기본적인 그래프 탐색 방법 DFS, BFS 에 대해 배우고 약간씩 응용하여 shortest path, conncected components, topological order, strongly connected components 등을 찾는 방법을 배운다. 마지막 부분에선 웹이 어떻게...
Graphs, The Contraction Algorithm
이번엔 지난시간에 배운 randomized algorithm 을 새로운 domain 인 그래프에 적용해 보고, contraction algorithm 이 무엇인지 알아본다. Graphs 용어 정리부터 시작하자. edge (E) 는 pair of vertices 와...