以Python實作演算法

以Python實作演算法– Algorithms Implements using Python ... BFS; 深度優先搜尋Depth-first Search, DFS; 最短路徑演算法Shortest Path ... 以Python實作演算法–AlgorithmsImplementsusingPython2018年12月7日2021年12月28日Misc,PythonTags:algorithmbellman-fordbfsbubblesortcountingsortdfsdijkstragraphsheapsortinsertionsortmergesortquicksortradixsortselectionsortshortest-pathsortingTOC 圖論GraphTheory 廣度優先搜尋Breadth-firstSearch,BFS 深度優先搜尋Depth-firstSearch,DFS 最短路徑演算法ShortestPath 圖論GraphTheory G(V,E) 由頂點（vertex,node）和連接頂點的邊（Edge）關聯成的圖形 其中關聯分作有方向性(directed)及無方向性(undirected) 須考慮最大流問題(maximumflow) 在程式語言有幾種方式來建構Graphs: 相鄰矩陣adjacencymatrixes 圖片來源 陣列edgelistrepresentation 1234567891011 classNode:     def__init__(self,name):        self.name=name        self.visited=False        self.neighbors=[]  #Nodes        self.predecessor=None  #useinshortestpath     def__repr__(self):        return'Node(name={})'.format(self.name)  應用 最短路徑演算法ShortestPathAlgorithm:GPS,高頻交易 生成樹協定SpanningTreeProtocol,STP 爬蟲 廣度優先搜尋Breadth-firstSearch,BFS 時間複雜度：O(V+E)（分別遍歷所有節點和各節點的所有鄰居） 空間複雜度：O(V)（Queue中最多可能存放所有節點） 用於有效率的迭代(traversal) 迭代的方式為鄰近的先訪問(level-ordered) 劣勢在於儲存指標記憶體空間，有時用DFS替代 使用FIFO的Queue來實作，Queue為空代表完成迭代 應用 machinelearning Edmonds-Karp演算法 Cheney演算法 以Python實作，輸出請參考gist 12345678910111213141516171819202122 classBFS:    """    ForBFS,usequeue;ForDFS,usestackorrecursion    """    def__init__(self,start):        self.queue=[]        self.start=start     deftraversal(self):        self.start.visited=True        self.queue.append(self.start)         whileself.queue:  #O(V)             node=self.queue.pop(0)            yieldnode             forninnode.neighbors:  #O(E)                ifnotn.visited:                    n.visited=True                    self.queue.append(n)  深度優先搜尋Depth-firstSearch,DFS 時間複雜度：O(V+E) 空間複雜度：O(logV)（訪問至末端節點後LIFO，Stack最多只會同時存在logV個節點，也就是樹的高度） 為了解MazeProblem而生的演算法 效能比BFS稍佳 使用LIFO的Stack來實作 應用 拓撲排序TopologicalOrder Kosaraju演算法:推薦系統RecommandSystem 判斷Grapth是否有cycle(DAG) Maze 以Python實作，輸出請參考gist 12345678910111213141516171819202122 classDFS:    """    ForBFS,usequeue;ForDFS,usestack/recursion(osstack)    """    def__init__(self,start):        self.start=start     deftraversal(self):        interface=self.stack()        interface(self.start)        returnself.result     defstack(self):        self.result=[]        definterface(node):            self.result.append(node)                        node.visited=True            forninnode.neighbors:                ifnotn.visited:                    interface(n)        returninterface  最短路徑演算法ShortestPath 主要用於找出Graph中兩節點之間的最短路徑 已知起點或終點，求最短的遍歷：Dijkstra、Bellman-Ford 求某起點到某終點的最短路徑：A*search 找全局最短路徑：Floyd-Warshall 最短路徑的應用 GPS RoutingImformationProtocal,RIP Avidan-Shamirmethod 先實作以下Dijkstra、Bellman-Ford演算法會用到的類別：Node、Edge 123456789101112131415161718192021222324252627282930313233 classEdge:    def__init__(self,weight,start,target):        self.weight=weight        self.start=start        self.target=target         ifselfnotinstart.edges:            start.edges.append(self)     def__repr__(self):        return'Edge(weight={0},start={1},target={2})'.format(            self.weight,            self.start,            self.target        ) classNode:    def__init__(self,name):        self.name=name        self.visted=False        self.predecessor=None        self.edges=[]  #Edges        self.min_cost=sys.maxsize     def__repr__(self):        return'Node(name={})'.format(self.name)     def__cmp__(self,other):        returnself.cmp(self.min_cost,other.min_cost)     def__lt__(self,other):        returnself.min_costcost:                    edge.target.min_cost=cost                    edge.target.predecessor=edge.start         foredgeinself.edges:            ifself.check_cycle(edge):                self.has_cycle=True     @staticmethod    defcheck_cycle(edge):        return(edge.start.min_cost+edge.weight)arr[j]:    swap(i,j)  冒泡排序BubbleSort 平均時間複雜度:O(N^2) stable、in-place 12345678910 defbubble_sort(arr):    defswap(x,y):        arr[x],arr[y]=arr[y],arr[x]     iter_time=len(arr)-1    foriinrange(iter_time):        forjinrange(0,iter_time-i):            ifarr[j]>arr[j+1]:                swap(j,j+1)  選擇排序SelectionSort 平均時間複雜度:O(N^2) 適用長度小的陣列(長度10~20)，效能甚至比quicksort、mergesort佳 寫入次數較插入排序要少 in-place 1234567891011121314151617 defselection_sort(arr):    defswap(x,y):        arr[x],arr[y]=arr[y],arr[x]     foriinrange(len(arr)-1):         index=i         forjinrange(i+1,len(arr)):            ifarr[j]0andarr[j-1]>arr[j]:            swap(j,j-1)            j-=1     returnarr  快速排序QuickSort 屬分治法（divideandconqueralgorithm），可以由遞迴來實作 時間複雜度：O(N^2)~O(NlogN) in-place 1234567891011121314151617181920212223242526272829 defquick_sort(arr):    arr=quick_sort_recur(arr,0,len(arr)-1)    returnarr defquick_sort_recur(arr,first,last):    iffirst