위상정렬.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 위상 정렬\n",
    "단방향 그래프에서 A->B의 관계가 있을 경우, 반드시 A를 먼저 출력 후, B를 출력합니다.     \n",
    "A->B<-C일 경우, A 또는 C를 먼저 출력 후, B를 출력합니다. A와 C의 출력 순서는 상관없습니다.  \n",
    "위상 정렬은 보통 대학교의 어떤 수업을 듣기 위해서 반드시 기초 수업을 마쳐야 할 경우,  어떤 수업부터 들어야하는 지  \n",
    "정렬할 때 많이 사용합니다.  \n",
    "또한 어떤 프로그램을 빌드할 때, 위상 정렬을 사용하여, 기초 라이브러리부터 응용 라이브러리를 순서대로 호출하기도 합니다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\na ---> d ---> e <--- c\\n       ^\\n       |\\n       b\\n'"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "a ---> d ---> e <--- c\n",
    "       ^\n",
    "       |\n",
    "       b\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "엣지 정보를 딕셔너리에 저장합니다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "adjacency_list = defaultdict()\n",
    "adjacency_list['a'] = ['d']\n",
    "adjacency_list['b'] = ['d']\n",
    "adjacency_list['c'] = ['e']\n",
    "adjacency_list['d'] = ['e']\n",
    "adjacency_list['e'] = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "노드의 정보를 visited_list에 저장합니다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "visited_list = defaultdict()\n",
    "visited_list['a'] = False\n",
    "visited_list['b'] = False\n",
    "visited_list['c'] = False\n",
    "visited_list['d'] = False\n",
    "visited_list['e'] = False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "output_stack = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "노드 방문 시, visited_list의 해당 노드값을 True로 변경하여, 다시 방문 하지 못하도록 합니다.  \n",
    "방문된 노드의 이웃 노드들을 차례대로 재귀적으로 위상정렬을 수행합니다.  \n",
    "모든 이웃 노드를 방문 했을 시, 현재 노드를 output 스택에 저장합니다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "def topology_sort(vertex):\n",
    "    if not visited_list[vertex]:\n",
    "        visited_list[vertex] = True\n",
    "        for neighbor in adjacency_list[vertex]:\n",
    "            topology_sort(neighbor)\n",
    "        output_stack.insert(0, vertex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "visited_list의 첫번째 노드부터 순차적으로 위상정렬을 진행합니다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "for vertex in visited_list:\n",
    "    topology_sort(vertex)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['c', 'b', 'a', 'd', 'e']"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "output_stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 시간복잡도: \n",
    "O(V+E)\n",
    "# 공간복잡도: \n",
    "2 dictionaries, 1 list required"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}