Graph.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 图论基础"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Graph(object):\n",
    "    def __init__(self,n,directed):\n",
    "        self.n = n\n",
    "        self.m = 0\n",
    "        self.directed = directed\n",
    "    def addEdge(v,w):\n",
    "        pass\n",
    "    def hasEdge(self,v,w):\n",
    "        pass\n",
    "    def getEdges(self,v):\n",
    "        pass\n",
    "    def V(self):\n",
    "        return self.n\n",
    "    def E(self):\n",
    "        return self.m\n",
    "class DenseGraph(Graph):\n",
    "    def __init__(self,n,directed):\n",
    "        self.n = n\n",
    "        self.m = 0\n",
    "        self.directed = directed\n",
    "        self.g = [[False for i in range(0,n)] for j in range(0,n)]\n",
    "    def addEdge(self,v,w):\n",
    "        if self.hasEdge(v,w):\n",
    "            return\n",
    "        self.g[v][w] = True\n",
    "        # 有向图\n",
    "        if not self.directed:\n",
    "            self.g[w][v] = True\n",
    "        self.m += 1\n",
    "    def hasEdge(self,v,w):\n",
    "        return self.g[v][w]\n",
    "    def getEdges(self,v):\n",
    "        n = self.n\n",
    "        edge_list = []\n",
    "        for i in range(0,n):\n",
    "            if self.g[v][i]:\n",
    "                edge_list.append(i)\n",
    "        return edge_list\n",
    "class SparseGraph(Graph):\n",
    "    def __init__(self,n,directed):\n",
    "        self.n = n\n",
    "        self.m = 0\n",
    "        self.directed = directed\n",
    "        self.g = []\n",
    "    def addEdge(self,v,w):\n",
    "        # O(v)\n",
    "        \"\"\"if self.hasEdge(v,w):\n",
    "            return\"\"\"\n",
    "        self.g[v].append(w)\n",
    "        # 有向图\n",
    "        if not self.directed and not v == w:\n",
    "            self.g[w].append(v)\n",
    "        self.m += 1\n",
    "    def hasEdge(self,v,w):\n",
    "        size = len(self.g[v])\n",
    "        for i in range(0,size):\n",
    "            if g[v][i] == w:\n",
    "                return True\n",
    "        return False\n",
    "    def getEdges(self,v):\n",
    "        return self.g[v]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 求无全图的联通分量 图的深度优先遍历\n",
    "class Conponent(object):\n",
    "    def __init__(self,graph):\n",
    "        self.graph = graph\n",
    "        # 记录dfs的过程中节点是否被访问\n",
    "        self.visited = [False for i in range(0,self.graph.V())]\n",
    "        # 每个节点所对应的联通分量标记\n",
    "        self.id = [-1 for i in range(0,self.graph.V())]\n",
    "        self.connection_count = 0\n",
    "        for i in range(0,self.graph.V()):\n",
    "            if not self.visited[i]:\n",
    "                self.dfs(i)\n",
    "                self.connection_count += 1\n",
    "    def dfs(self,v):\n",
    "        self.visited[v] = True\n",
    "        self.id[v] = self.connection_count\n",
    "        for i in self.graph.getEdges(v):\n",
    "            if not self.visited[i]:\n",
    "                self.dfs(i)\n",
    "    def getConnCount(self):\n",
    "        return self.connection_count\n",
    "    def isConnected(self,v,w):\n",
    "        return self.id[v] == self.id[w]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 最小路径问题 图的广度优先遍历\n",
    "class ShortesPath(object):\n",
    "    def __init__(self,graph,s):\n",
    "        self.graph = graph\n",
    "        self.visited = [False for i in range(0,self.graph.V())]\n",
    "        self.from_ids = [-1 for i in range(0,self.graph.V())]\n",
    "        self.orders = [-1 for i in range(0,self.graph.V())]\n",
    "        self.s = s\n",
    "        self.bfs(s)\n",
    "    def bfs(self,s):\n",
    "        from queue import Queue\n",
    "        q = Queue()\n",
    "        q.put(s)\n",
    "        self.visited[s] = True\n",
    "        self.orders[s] = 0\n",
    "        while not q.empty():\n",
    "            v = q.get()\n",
    "            for i in self.graph.getEdges(v):\n",
    "                if not self.visited[i]:\n",
    "                    q.put(i)\n",
    "                    self.visited[i] = True\n",
    "                    self.from_ids[i] = v\n",
    "                    self.orders[i] = self.orders[v] + 1\n",
    "    def hasPath(self,w):\n",
    "        return self.visited[w]\n",
    "    def showPath(self,w):\n",
    "        path_list = []\n",
    "        p = w\n",
    "        while not p == -1:\n",
    "            path_list.append(p)\n",
    "            p = self.from_ids[p]\n",
    "        path_list.reverse()\n",
    "        for i in range(0, len(path_list)):\n",
    "            if i == len(path_list)-1:\n",
    "                print(path_list[i])\n",
    "            else:\n",
    "                print(path_list[i],end='->')\n",
    "        return path_list\n",
    "    def path_len(self,w):\n",
    "        return self.orders[w]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "0->3->6\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[0, 3, 6]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dg = DenseGraph(10,False)\n",
    "dg.addEdge(0,1)\n",
    "dg.addEdge(0,3)\n",
    "dg.addEdge(1,3)\n",
    "dg.addEdge(4,3)\n",
    "dg.addEdge(6,3)\n",
    "dg.addEdge(5,4)\n",
    "dg.addEdge(6,8)\n",
    "dg.addEdge(8,9)\n",
    "dg.addEdge(0,9)\n",
    "dg.addEdge(7,5)\n",
    "c = Conponent(dg)\n",
    "print(c.getConnCount())\n",
    "s = ShortesPath(dg,0)\n",
    "s.showPath(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 最小生成树问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "针对带权无向图，连通图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "找V-1条边，连接V个顶点，使得权值最小"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "切分定理：给定任意一个切分，权值最小的横切边必定属于最小生成树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}