Algorithm

本文是为了2019年春季的Design & Analysis of Algotirhm而撰写，目的是总结课程中学到的算法。

Sorting

import time


class Sort:
    """
    Class for all kinds of sorting algorithms implemented in Python3
    Notes:
        if maxone - minone in the list < nlogn, we can use counting sort
        else range k of the nums is >> nlong, we can use radix sort. Both Algos are O(n)

        if we need to sort for numbers in other number system, like bin or hex, we need to use Radix Sort

        if nums are very huge and cannot load at a time, we need to use heap sort with forward-method for building heaps
    """
    def InsertSort(self, nums):
        """
        :intro: insertion sort
        :param nums: unsorted nums (list)
        :return: sorted nums (list)
        """
        sorted_nums = nums[:1]
        for num in nums[1:]:
            for sorted_num_index in range(len(sorted_nums) - 1, -1, -1):
                if sorted_nums[sorted_num_index] > num:
                    if sorted_num_index == 0:
                        sorted_nums.insert(sorted_num_index, num)
                    else:
                        continue
                else:
                    sorted_nums.insert(sorted_num_index + 1, num)
                    break
        return sorted_nums

    def MergeSort(self, nums):
        """
        :intro: merge sort
        :param nums: unsorted nums (list)
        :return: sorted nums (list)
        """

        def divide(given_nums):
            """
            :intro: dimidiate given array
            :param given_nums: given array (list)
            :return: two parts of dimidiated array (list)
            """
            return given_nums[:(len(given_nums) // 2)], given_nums[(len(given_nums) // 2):]

        def merge(left_nums, right_nums):
            """
            :intro: merge sorted arrays
            :param left_nums: one sorted array (list)
            :param right_nums: another sorted array (list)
            :return: merged sorted array (list)
            """
            merged_nums = []
            l = r = 0
            for i in range(len(left_nums) + len(right_nums)):
                if left_nums[l] < right_nums[r]:
                    merged_nums.append(left_nums[l])
                    l += 1
                else:
                    merged_nums.append(right_nums[r])
                    r += 1
                if l == len(left_nums):
                    merged_nums += right_nums[r:]
                    break
                if r == len(right_nums):
                    merged_nums += left_nums[l:]
                    break
            return merged_nums

        if len(nums) >= 2:
            nums_l, nums_r = divide(nums)
            nums_l = self.MergeSort(nums_l)
            nums_r = self.MergeSort(nums_r)
            return merge(nums_l, nums_r)
        return nums

    def HeapSort(self, nums):
        """
        :intro: heap sort  # 从小到大排需建立大根堆，从大到小需建立小根堆，或者reverse一下
        :param nums: unsorted array
        :return: sorted array
        """

        def adjust(nums, start, end):
            """
            :intro: adjust given heap, which contained in a given nums
            :param nums: given nums
            :param start: the startpoint of heap
            :param end: the endpoint of heap
            :return: adjusted heap, which contained in the previous nums
            """
            root = start
            left = 2 * start + 1
            right = 2 * start + 2
            if left < end and nums[left] < nums[root]:
                root = left
            if right < end and nums[right] < nums[root]:
                root = right
            if root != start:
                nums[start], nums[root] = nums[root], nums[start]
                adjust(nums, root, end)
            return nums

        length = len(nums)
        for i in range(length // 2 - 1, -1, -1):
            adjust(nums, i, length)
        for j in range(length - 1, -1, -1):
            nums[0], nums[j] = nums[j], nums[0]
            adjust(nums, 0, j)

        return nums[::-1]

    def CountingSort(self, nums):
        """
        :intro: Counting sort for n integers, where value range k of n < nlogn
        :param nums: unsorted array
        :return: sorted array
        """
        minone = min(nums)
        gap = 1 - minone  # 把负数填充成大于等于1的正数
        maxone = max(nums)
        sorted_nums = [0] * len(nums)
        countings = [0] * (maxone - minone + 1)
        for num in nums:
            countings[num + gap - 1] += 1
        summings = [sum(countings[:c + 1]) for c in range(len(countings))]
        for num in nums[::-1]:
            sorted_nums[summings[num + gap - 1] - 1] = num
            summings[num + gap - 1] -= 1
        return sorted_nums

    def RadixSort(self, nums):
        """
        :intro: Radix sort for n integers, where value range k of n can be far bigger than nlogn
        :param nums: unsorted array
        :return: sorted array
        """
        # Radix Sort必须使用stable的算法来进行每一个数位上的排序，同时数位上数的范围最多是0～9，远小于n，所以最好用Counting Sort
        # 这里建立一个特殊的counting sort，是为了返回原list中元素的index，方便定位

        def CountingSort_withindex(nums):
            """
            :intro: Counting sort and kept original indexes
            :param nums: unsorted array
            :return: sorted array
            """
            minone = min(nums, key=lambda x: x[1])[1]
            gap = 1 - minone  # 把负数填充成大于等于1的正数
            maxone = max(nums, key=lambda x: x[1])[1]
            sorted_nums = [0] * len(nums)
            countings = [0] * (maxone - minone + 1)
            for num in nums:
                countings[num[1] + gap - 1] += 1
            summings = [sum(countings[:c + 1]) for c in range(len(countings))]
            for num in nums[::-1]:
                sorted_nums[summings[num[1] + gap - 1] - 1] = (num[0], num[1])
                summings[num[1] + gap - 1] -= 1
            return sorted_nums

        minone = min(nums)
        gap = -minone  # 把负数填充成大于等于0的数
        nums = [num + gap for num in nums]
        length = len(str(max(nums)))
        l = 0
        digits = [(n, nums[n] // (10 ** l) % 10) for n in range(len(nums))]
        while l < length:
            c_digits = CountingSort_withindex(digits)
            l += 1
            digits = [(i, nums[i] // (10 ** l) % 10) for i, d in c_digits]

        return [nums[i] - gap for i, d in digits]

    def QuickSort(self, nums):
        """
        :intro: Quick Sort for n numbers
        :param nums: unsorted array
        :return: sorted array
        """
        if len(nums) <= 1:
            return nums
        else:
            pivot = nums.pop()
            s1, s2 = [], []
            for num in nums:
                if num < pivot:
                    s1.append(num)
                else:
                    s2.append(num)
            return self.QuickSort(s1) + [pivot] + self.QuickSort(s2)

    def QuickSort_inplace_1(self, nums, p, r):
        """
        :intro: Quick Sort for n numbers (in place version 1: keep move smaller elements front of the pivot)
        :param nums: unsorted array
        :param p: start position of sorting any part of the whole array
        :param r: end position of sorting any part of the whole array
        :return: sorted array
        """
        def Partition(nums, p, r):
            """
            :intro: Partition for given array, by keeping move smaller elements front of the pivot
            :param nums: any array
            :param p: start position of targeted array waiting to be partitioned
            :param r: end position of targeted array waiting to be partitioned
            :return: elements in range(p, r) will be partitioned by pivot with smaller before the pivot and larger after
            """
            pivot = nums[p]
            pivot_index = p
            for i in range(p + 1, r + 1):
                current = nums[i]
                if current < pivot:
                    nums.pop(i)
                    nums.insert(pivot_index, current)
                    pivot_index += 1
            return pivot_index

        if p < r:
            q = Partition(nums, p, r)
            self.QuickSort_inplace_1(nums, p, q - 1)
            self.QuickSort_inplace_1(nums, q + 1, r)

    def QuickSort_inplace_2(self, nums, p, r):
        """
        :intro: Quick Sort for n numbers (in place version 2: two pointers searching)
        :param nums: unsorted array
        :param p: start position of sorting any part of the whole array
        :param r: end position of sorting any part of the whole array
        :return: sorted array
        """
        def Partition(nums, p, r):
            """
            :intro: Partition for given array, by using two pointers to track adjusting pairs and swap
            :param nums: any array
            :param p: start position of targeted array waiting to be partitioned
            :param r: end position of targeted array waiting to be partitioned
            :return: elements in range(p, r) will be partitioned by pivot with smaller before the pivot and larger after
            """
            pivot = nums[p]
            while p < r:
                while p < r and nums[r] >= pivot:
                    r -= 1
                nums[p] = nums[r]
                while p < r and nums[p] <= pivot:
                    p += 1
                nums[r] = nums[p]
            nums[p] = pivot
            return p

        if p < r:
            q = Partition(nums, p, r)
            self.QuickSort_inplace_2(nums, p, q - 1)
            self.QuickSort_inplace_2(nums, q + 1, r)


sorting = Sort()
unsorted_nums = [1, 22, 1, 1, 2, -3, 5, -10, -2, 0, 7, 19, 4, 99, -3, -10, 0]
start = time.time()

print(sorting.InsertSort(unsorted_nums))
stop1 = time.time()
print((stop1 - start) * 1000)

print(sorting.MergeSort(unsorted_nums))
stop2 = time.time()
print((stop2 - stop1) * 1000)

# Heap sort is an in-place operation, so we need to rebuild the unsorted array below
print(sorting.HeapSort(unsorted_nums))
stop3 = time.time()
print((stop3 - stop2) * 1000)

unsorted_nums = [1, 22, 1, 1, 2, -3, 5, -10, -2, 0, 7, 19, 4, 99, -3, -10, 0]
print(sorting.CountingSort(unsorted_nums))
stop4 = time.time()
print((stop4 - stop3) * 1000)

print(sorting.RadixSort(unsorted_nums))
stop5 = time.time()
print((stop5 - stop4) * 1000)

# The extra space quick sort will delete the tail of original array, so we need to rebuild the unsorted array below
print(sorting.QuickSort(unsorted_nums))
stop6 = time.time()
print((stop6 - stop5) * 1000)

# The in-place quick sort do in-place operation, so we need to rebuild the unsorted array below
unsorted_nums = [1, 22, 1, 1, 2, -3, 5, -10, -2, 0, 7, 19, 4, 99, -3, -10, 0]
sorting.QuickSort_inplace_1(unsorted_nums, 0, len(unsorted_nums) - 1)
print(unsorted_nums)
stop7 = time.time()
print((stop7 - stop6) * 1000)

# The in-place quick sort do in-place operation, so we need to rebuild the unsorted array below
unsorted_nums = [1, 22, 1, 1, 2, -3, 5, -10, -2, 0, 7, 19, 4, 99, -3, -10, 0]
sorting.QuickSort_inplace_2(unsorted_nums, 0, len(unsorted_nums) - 1)
print(unsorted_nums)
stop8 = time.time()
print((stop8 - stop7) * 1000)

unsorted_nums = [1, 22, 1, 1, 2, -3, 5, -10, -2, 0, 7, 19, 4, 99, -3, -10, 0]
# Wait for next sort...

Search

import time


class Search:
    """
    Class for all searching algorithms implemented in Python 3
    """
    def BinarySearch(self, sorted_nums, start, end, target):
        """
        :intro: binary search for a given target in a sorted array
        :param sorted_nums: sorted array
        :param start: start index
        :param end: end index
        :param target: given number
        :return: index of given number
        """
        if start > end:
            return "No such target"
        mid = (start + end) // 2
        if target == sorted_nums[mid]:
            return mid
        elif target < sorted_nums[mid]:
            return self.BinarySearch(sorted_nums, start, mid - 1, target)
        elif target > sorted_nums[mid]:
            return self.BinarySearch(sorted_nums, mid + 1, end, target)

    def Search2nd(self, unsorted_nums):
        """
        :intro: find 2nd biggest number in an unsorted array
        :param unsorted_nums: unsorted array
        :return: 2nd biggest number
        """
        mmmone = unsorted_nums[-1]
        maxone = ma2one = 0
        n = len(unsorted_nums)
        kdict = {}
        while n > 1:
            next_nums = []
            for i in range(n // 2):
                maxone = max(unsorted_nums[2 * i], unsorted_nums[2 * i + 1])
                minone = min(unsorted_nums[2 * i], unsorted_nums[2 * i + 1])
                next_nums.append(maxone)
                if maxone in kdict:
                    kdict[maxone].append(minone)
                else:
                    kdict[maxone] = [minone]
            unsorted_nums = next_nums
            n = len(unsorted_nums)
        for c in kdict[maxone]:
            ma2one = max(ma2one, c)
        if len(unsorted_nums) % 2 == 0:
            pass
        else:
            if mmmone > maxone:
                return maxone
            elif mmmone > ma2one:
                return mmmone
            else:
                pass
        return ma2one

    def SearchK_deterministic(self, unsorted_nums, k):
        """
        :intro: find k-th smallest number in an unsorted and distinct array via deterministic pivot
        :param unsorted_nums: unsorted array
        :param k: k-th smallest index
        :return: k-th smallest number
        """
        group = 5
        length = len(unsorted_nums) // group
        ms = [sorted(unsorted_nums[group * i: group * i + group], reverse=True) for i in range(length)]  # 按五个分为一组
        ms.append(sorted(unsorted_nums[group * length:], reverse=True))  # 最后一组可以小于5
        mm = [s[len(s) // 2] for s in ms if s != []]  # 每组的中位数
        if len(mm) > 1:  # 中位数的中位数作为m，递归实现
            m = self.SearchK_deterministic(mm, len(mm) // 2)
        else:
            m = mm[0]
        s1 = []
        s2 = []
        for num in unsorted_nums:
            if num < m:
                s1.append(num)
            elif num > m:
                s2.append(num)
        length = len(s1)
        if length + 1 == k:
            return m
        elif length >= k:
            return self.SearchK_deterministic(s1, k)
        else:
            return self.SearchK_deterministic(s2, k - length - 1)

    def SearchK_randomized(self, unsorted_nums, k):
        """
        :intro: find k-th smallest number in an unsorted and distinct array via randomly pivot
        :param unsorted_nums: unsorted array
        :param k: k-th smallest index
        :return: k-th smallest number
        """
        from random import sample
        r = sample(range(len(unsorted_nums)), 1)[0]  # 随机选一个数
        s1 = []
        s2 = []
        for num in unsorted_nums:
            if num < unsorted_nums[r]:
                s1.append(num)
            elif num > unsorted_nums[r]:
                s2.append(num)
        length = len(s1)
        if length + 1 == k:
            return unsorted_nums[r]
        elif length >= k:
            return self.SearchK_randomized(s1, k)
        else:
            return self.SearchK_randomized(s2, k - length - 1)


search = Search()
sorted_nums = [-10, -10, -3, -3, -2, 0, 0, 1, 1, 1, 2, 4, 5, 7, 19, 22, 99]
unsorted_nums = [1, 22, 1, 1, 2, -3, 5, -10, -2, 0, 7, 19, 4, 99, -3, -10, 0]
unsorted_distinct_nums = [1, 22, 2, -3, 5, -10, -2, 0, 7, 19, 4, 99]
start = time.time()

print(search.BinarySearch(sorted_nums, 0, len(sorted_nums) - 1, 5))
stop1 = time.time()
print((stop1 - start) * 1000)

print(search.Search2nd(unsorted_nums))
stop2 = time.time()
print((stop2 - stop1) * 1000)

print(search.SearchK_deterministic(unsorted_distinct_nums, 10))
stop3 = time.time()
print((stop3 - stop2) * 1000)

print(search.SearchK_randomized(unsorted_distinct_nums, 10))
stop4 = time.time()
print((stop4 - stop3) * 1000)

Binary Search Tree

# 代码来自：https://blog.csdn.net/u010089444/article/details/70854510


class Node:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None


class BST:
    def __init__(self, node_list):
        self.root = Node(node_list[0])
        for data in node_list[1:]:
            self.insert(data)

    def search(self, node, parent, data):
        if node is None:
            return False, node, parent
        if node.data == data:
            return True, node, parent
        if node.data > data:
            return self.search(node.lchild, node, data)
        else:
            return self.search(node.rchild, node, data)

    def insert(self, data):
        flag, n, p = self.search(self.root, self.root, data)
        if not flag:
            new_node = Node(data)
            if data > p.data:
                p.rchild = new_node
            else:
                p.lchild = new_node

    def delete(self, data):
        flag, n, p = self.search(self.root, self.root, data)
        if flag is False:
            print("无该关键字，删除失败")
        else:
            if n.lchild is None:  # 如果右子树为空，直接往上继承
                if n == p.lchild:
                    p.lchild = n.rchild
                else:
                    p.rchild = n.rchild
                del n
            elif n.rchild is None:  # 如果左子树为空，直接往上继承
                if n == p.lchild:
                    p.lchild = n.lchild
                else:
                    p.rchild = n.lchild
                del n
            else:  # 左右子树均不为空
                pre = n.rchild
                if pre.lchild is None:
                    n.data = pre.data
                    n.rchild = pre.rchild
                    del pre
                else:
                    next = pre.lchild  # 往右一个节点，然后一直找到最左下角
                    while next.lchild is not None:
                        pre = next
                        next = next.lchild
                    n.data = next.data
                    pre.lchild = next.rchild  # 把next拿走后，因为next必定没有左孩子，故直接让上一层的左孩子继承next的右子树
                    del next

    def preOrderTraverse(self, node):
        if node is not None:
            print(node.data, end=", ")
            self.preOrderTraverse(node.lchild)
            self.preOrderTraverse(node.rchild)
        return "End"

    def inOrderTraverse(self, node):
        if node is not None:
            self.inOrderTraverse(node.lchild)
            print(node.data, end=", ")
            self.inOrderTraverse(node.rchild)
        return "End"

    def postOrderTraverse(self, node):
        if node is not None:
            self.postOrderTraverse(node.lchild)
            self.postOrderTraverse(node.rchild)
            print(node.data, end=", ")
        return "End"


a = [3, 1, 8, 4, 6, 5, 7]
bst = BST(a)  # 创建二叉查找树
print(bst.inOrderTraverse(bst.root))  # 中序遍历，等于排序
bst.delete(3)
print(bst.inOrderTraverse(bst.root))  # 中序遍历，等于排序

Graph

import time

graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D"],
    "F": ["D"]
}

DAG = {'1': ['2', '3'],
       '2': [],
       '3': ['2'],
       '4': ['1', '3', '5'],
       '5': [],
       }

weighted_graph = {
    0: [(1, 10), (2, 50)],
    1: [(0, 10), (2, 11), (3, 31)],
    2: [(0, 50), (1, 11), (3, 42), (4, 33), (5, 15)],
    3: [(1, 31), (2, 42), (4, 38), (5, 13)],
    4: [(2, 33), (3, 38), (5, 47)],
    5: [(2, 15), (3, 13), (4, 47)]
}

directed_weighted_graph = {
    0: [(1, 26), (2, 10)],
    1: [],
    2: [(3, 22), (4, 5), (8, 14), (9, 43), (10, 3), (11, 7)],
    3: [],
    4: [(5, 74), (6, 40), (7, 12)],
    5: [],
    6: [],
    7: [],
    8: [(9, 20)],
    9: [],
    10: [(11, 21)],
    11: [(9, 13), (12, 20), (13, 22)],
    12: [],
    13: [(12, 7), (14, 9)],
    14: []
}

DG = {
    1: [8, 10],
    2: [7],
    3: [11],
    4: [11],
    5: [6, 10],
    6: [],
    7: [],
    8: [2, 3],
    9: [1, 5, 4],
    10: [9],
    11: [7, 8]
}


def BFS(graph, start, end):
    """
    :intro: using BFS to find shortest path between two given points in a graph
    :param graph: the graph
    :param start: the start endpoint
    :param end: the destination endpoint
    :return: the path
    """
    if start not in graph or end not in graph:
        return "Wrong endpoints"
    else:
        seen = set(start)
        queue = graph[start][:]
        path = {v: start for v in queue}
        while queue:
            curr = queue.pop(0)
            seen.add(curr)
            if curr != end:
                queue += [e for e in graph[curr] if e not in seen]
                path.update({e: curr for e in graph[curr] if e not in path and e not in seen})
            else:
                break
        if end in path:
            track = end
            way = []
            while track in path:
                way.append(track)
                track = path[track]
            return [start] + way[::-1]
        else:
            return "No path"


def DFS(graph, start, end):
    """
    :intro: using DFS to find shortest path between two given points in a graph
    :param graph: the graph
    :param start: the start endpoint
    :param end: the destination endpoint
    :return: the path
    """
    if start not in graph or end not in graph:
        return "Wrong endpoints"
    else:
        seen = set(start)
        stack = graph[start][:]
        path = {v: start for v in stack}
        while stack:
            curr = stack.pop()
            seen.add(curr)
            if curr != end:
                stack += [e for e in graph[curr] if e not in seen]
                path.update({e: curr for e in graph[curr] if e not in path and e not in seen})
            else:
                break
        if end in path:
            track = end
            way = []
            while track in path:
                way.append(track)
                track = path[track]
            return [start] + way[::-1]
        else:
            return "No path"


def TopSort(graph):
    """
    :intro: topological sort for DAG by gradually delete nodes with 0 in-degree
    :param graph: a given DAG
    :return: one kind of topological sort
    """
    cnt = {u: 0 for u in graph.keys()}

    # 每个节点的入度
    for u in graph:
        for v in graph[u]:
            cnt[v] += 1

    queue = [u for u in cnt.keys() if cnt[u] == 0]  # 入度为0的起点集合
    seq = []
    while queue:
        curr = queue.pop(0)
        seq.append(curr)
        for u in graph[curr]:
            cnt[u] -= 1
            if cnt[u] == 0:
                queue.append(u)

    if len(seq) == len(graph.keys()):
        return seq
    else:
        return "Not a DAG"


def Kruskal(weighted_graph):
    """
    :intro: to find minimum spanning tree for a undirected reachable weighted graph by kruskal's algo, O(ElogV)
    :param weighted_graph: a given undirected weighted graph
    :return: the mst of the UWG
    """
    mst = {k: [] for k in weighted_graph.keys()}  # O(V)
    components_id = list(range(len(weighted_graph.keys())))
    edges = set()
    for vertex1 in weighted_graph:
        for vertex2 in weighted_graph[vertex1]:
            edges.add(tuple(sorted([vertex1, vertex2[0]]) + [vertex2[1]]))
    sorted_edges = sorted(edges, key=lambda x: x[2])  # O(ElogE) = O(E * logV^2) = O(ElogV), E <= V^2 for all (Vi, Vj)s
    for sorted_edge in sorted_edges:
        v1, v2, weight = sorted_edge[0], sorted_edge[1], sorted_edge[2]
        l1, l2 = components_id[v1], components_id[v2]
        if l1 != l2:  # add edge into mst if V1 and V2 are not in one component
            mst[v1].append((v2, weight))
            mst[v2].append((v1, weight))
            # merge small component into large component, merge less than logV time, O(VlogV) in total
            # O(VlogV) = O((E + 1) * logV) = O(ElogV), E >= V - 1 for any reachable graph
            if components_id.count(l1) < components_id.count(l2):
                for i in range(len(components_id)):
                    if components_id[i] == l1:
                        components_id[i] = l2
            else:
                for i in range(len(components_id)):
                    if components_id[i] == l2:
                        components_id[i] = l1
        if len(set(components_id)) == 1:
            break
    return mst


def Prim(weighted_graph, starting_vertex):
    """
    :intro: to find minimum spanning tree for a undirected reachable weighted graph by Prim's algo, O(ElogV)
    :param weighted_graph: a given undirected weighted graph
    :param starting_vertex: source vertex
    :return: the mst of the UWG
    """
    import heapq

    mst = {k: [] for k in weighted_graph.keys()}  # O(V)
    visited = set()
    visited.add(starting_vertex)
    # Initialize the heap, O(E) in worst case
    edges = [(cost, starting_vertex, to) for to, cost in weighted_graph[starting_vertex]]
    heapq.heapify(edges)

    while edges:  # O(V) rounds
        # for push root, adjust heap and add edges part, O(logV) + O(1) per round, O(VlogV) + O(V) in total
        cost, frm, to = heapq.heappop(edges)  # push root
        if to not in visited:
            visited.add(to)  # add nodes to visited set
            mst[frm].append((to, cost))  # add edge to MST
            mst[to].append((frm, cost))
            # for check part, O(degree(to)) * O(logV) per round, O(ElogV) in total
            for to_next, cost in weighted_graph[to]:  # check for potential unvisited nodes
                if to_next not in visited:
                    heapq.heappush(edges, (cost, to, to_next))

    return mst


def Dijkstra(directed_weighted_graph, starting_vertex):
    """
    :intro: to solve SSSP problem on a non-negative directed_weighted_graph by Dijkstra's algo, O(ElogV), very similar to Prim
    :param directed_weighted_graph: a given directed weighted graph
    :param starting_vertex: source vertex
    :return: the SSSP from starting vertex to any other nodes of the DWG, as well as the cost
    """
    import heapq

    sssp = {k: [] for k in directed_weighted_graph.keys()}  # O(V)
    visited = set()
    visited.add(starting_vertex)
    # Initialize the heap, O(E) in worst case
    edges = [(cost, starting_vertex, to) for to, cost in directed_weighted_graph[starting_vertex]]
    heapq.heapify(edges)

    while edges:  # O(V) rounds
        # for push root, adjust heap and add edges part, O(logV) + O(1) per round, O(VlogV) + O(V) in total
        cost, frm, to = heapq.heappop(edges)  # push root
        if to not in visited:
            visited.add(to)  # add nodes to visited set
            sssp[to] = sssp[frm] + [(to, cost)]  # add edge to sssp strategies
            # for check part, O(degree(to)) * O(logV) per round, O(ElogV) in total
            for to_next, cost in directed_weighted_graph[to]:  # check for potential unvisited nodes
                if to_next not in visited:
                    heapq.heappush(edges, (cost + sssp[to][-1][1], to, to_next))

    return sssp


def BellmanFord(directed_weighted_graph, starting_vertex):
    """
    :intro: to solve SSSP problem on a non-negative directed_weighted_graph by Bellman-Ford's algo, O(VE)
    :param directed_weighted_graph: a given directed weighted graph
    :param starting_vertex: source vertex
    :return: the SSSP from starting vertex to any other nodes of the DWG, as well as the cost
    """
    keys = directed_weighted_graph.keys()

    scores = {k: float("Inf") for k in keys}
    scores[starting_vertex] = 0
    parent = {k: [] for k in keys}
    for i in range(len(keys) - 1):  # O(V - 1) rounds
        for vertex, edges in directed_weighted_graph.items():  # O(E) rounds
            for edge in edges:
                if scores[vertex] + edge[1] < scores[edge[0]]:
                    scores[edge[0]] = scores[vertex] + edge[1]
                    parent[edge[0]] = parent[vertex] + [vertex]

    # if the scores can be improved after V - 1 rounds, then we have negative cycle
    for vertex, edges in directed_weighted_graph.items():
        for edge in edges:
            if scores[edge[0]] != float("Inf") and scores[vertex] + edge[1] < scores[edge[0]]:
                return "Graph contains negative weight cycle"

    return {k: [(e, scores[e]) for e in v[1:] + [k]] for k, v in parent.items()}


def SCC(G):
    """
    :intro: to find all scc in a directed graph, from https://www.jianshu.com/p/192ae0425917
    :param G: a given directed graph
    :return: sccs
    """
    # 获取翻转所有边的图
    def tr(G):
        # 初始化翻转边的图GT
        GT = dict()
        for u in G.keys():
            GT[u] = GT.get(u, set())
        # 翻转边
        for u in G.keys():
            for v in G[u]:
                GT[v].add(u)
        return GT

    # 获取按节点遍历完成时间递减排序的顺序
    def topoSort(G):
        res = []
        S = set()

        # dfs遍历图
        def dfs(G, u):
            if u in S:
                return
            S.add(u)
            for v in G[u]:
                if v in S:
                    continue
                dfs(G, v)
            res.append(u)

        # 检查是否有遗漏的节点
        for u in G.keys():
            dfs(G, u)
        # 返回拓扑排序后的节点列表
        res.reverse()
        return res

    # 通过给定的起始节点，获取单个连通量
    def walk(G, s, S=None):
        if S is None:
            s = set()
        Q = []
        P = dict()
        Q.append(s)
        P[s] = None
        while Q:
            u = Q.pop()
            for v in G[u]:
                if v in P.keys() or v in S:
                    continue
                Q.append(v)
                P[v] = P.get(v, u)
        # 返回强连通图
        return P

    # 记录强连通分量的节点
    seen = set()
    # 储存强强连通分量
    scc = []
    GT = tr(G)
    for u in topoSort(G):
        if u in seen:
            continue
        C = walk(GT, u, seen)
        seen.update(C)
        scc.append(sorted(list(C.keys())))

    return scc


stop1 = time.time()
print(BFS(graph, "E", "D"))
stop2 = time.time()
print((stop2 - stop1) * 1000)
print(DFS(graph, "E", "D"))
stop3 = time.time()
print((stop3 - stop2) * 1000)
print(TopSort(DAG))
stop4 = time.time()
print((stop4 - stop3) * 1000)
print(Kruskal(weighted_graph))
stop5 = time.time()
print((stop5 - stop4) * 1000)
print(Prim(weighted_graph, 0))
stop6 = time.time()
print((stop6 - stop5) * 1000)
print(Dijkstra(directed_weighted_graph, 0))
stop7 = time.time()
print((stop7 - stop6) * 1000)
print(BellmanFord(directed_weighted_graph, 0))
stop8 = time.time()
print((stop8 - stop7) * 1000)
print(SCC(DG))
stop9 = time.time()
print((stop9 - stop8) * 1000)