Data Structurestackheapheap的实现索引堆tree并查集图 Graph

stack

heap

堆的基本性质: ①堆中的某一个节点总是不小于或不大于其父节点的值。 ②堆总是一棵完全二叉树 比较经典的堆有二叉堆,费波纳茨堆等等。如果一棵二叉树最下层上的结点都集中在该层最左边的若干位置上,而在最后一层上,右边的若干结点缺失的二叉树,则此二叉树成为完全二叉树。

比如这就是一棵完全二叉树,而且是最小堆,最大堆就是反着来即可。但是并不是层数越高,堆的值就越小(大)

比如13就是小于15的,这样并不会违反最大堆的定义。 i堆的实现可以使用类似二叉树做左节点右节点的实现,定义一个类,左子树右子树和数组。但是基于堆的特殊性质,我们可以使用数组实现

从图中可以得到每一个左节点都是父节点的2倍,右节点是2倍加1。

heap的实现

实现一个最大堆。用一个类作为容器。为了存取方便,第一个元素从索引1开始。

class maxheap(object):
    def __init__(self):
        self.__array = [0]
        self.__count = 0
        pass

    def size(self):
        return self.__count

    def isEmpty(self):
        return self.__count == 0

上面都是些基本操作,查看大小,判断是否为空。

insertHeap

插入一个元素直接把插入的元素放在最后,但是还要注意需要满足最大堆的任何一个节点都不大于父节点,所以要做一个shifup的上浮操作,如果当前节点是大于父节点,当前节点和它的父节点交换,以此类推,知道不大于为止。 上浮操作:

    def __shifUp(self, k):
        while k > 1 and (self.__array[int(k/2)] < self.__array[k]):
            swap(self.__array, int(k/2), k)
            k = int(k/2)
        pass

首先要判断这个节点是不是最大的了,k=1是最大的了,如果不是,那么这个节点必有一个父节点,因为数组是依次排序下来的,大于就交换。 实现插入操作:

    def insert(self, number):
        self.__array.append(number)
        self.__count += 1
        self.__shifUp(self.__count)
        pass

插入之后把最后新进的元素进行上浮shifup操作即可。

extractMax

出堆只能是出最大的元素,也就是索引为1的元素,出堆之后哪个元素作为最大的元素也是需要交换的,这个时候就需要shifdown了。

    def __shifDown(self, k):
        while 2*k <= self.__count:
            j = 2*k
            if j + 1 <= self.__count and (self.__array[j + 1] > self.__array[j]):
                j += 1
            if self.__array[k] >= self.__array[j]:
                break
            swap(self.__array, k, j)
            k = j
        pass

先看一下这个元素有没有子节点,如果右节点也有,那就要比较一下两边哪个大,最后还要看一下当前节点是不是小于子节点,小于才交换。

    def extractMax(self):
        maxNumber = self.__array[1]
        self.__array[1] = self.__array[self.__count]
        self.__count -= 1
        self.__shifDown(1)
        return maxNumber
        pass

这就是主要的出堆了,拿出第一个元素之后直接把这个元素和最后一个元素交换,直接赋值也可以,接着下浮操作即可。

if __name__ == '__main__':
    heap = maxheap()
    for i in range(13):
        heap.insert(np.random.randint(0, 200))
    heap.showHeap()
    for i in range(1):
        print(heap.extractMax())
    heap.showHeap()

测试一下:

索引堆

之前学过的堆:

经过heapify之后:

这样存在的许多的数据交换,会有一些局限性,如果数据的内容特别大,每一个节点都是一个几十万的字符串,那么这样的消耗是非常大的。另外,他还有一个弊端,如果是一些进程,每一个进程下面的数字就是优先级,比如第一张图片1号进程优先级是15,2号17。heapify之后如果想要改变某一个进程的优先级就有点难了,当然也可以开辟一个空间存储ID,但是麻烦了点。 所以比较好的方法就是每一个节点分配一个索引,用索引来建堆。

建堆的时候不使用原值,而是用一个索引。交换也就是交换索引了。

首先交换的复杂度不高,想改变某个值重新建堆也很方便。


tree

二叉搜索树

二叉搜索树首先要讲到二分查找法。

二分查找

首先二分数据,查看中间的一个数据是不是要找的,如果不是就看是否大于,大于就查找右边,右边再次二分,小于查找左边,再次二分。这样不断迭代完即可。当然前提是这个数组要是有序的。

def binarySearch(array, n, target):
    '''
    :param array:order array
    :param n: the number of the array
    :param target: number which we search for
    :return: index of target
    '''
    l, r = 0, n-1
    while l <= r:
        mid = int((l + r)/2)
        #mid = int((l + (r-l))/2)
        if array[mid] == target:
            return (mid + 1)
        elif mid < target:
            l = mid + 1
        elif mid > target:
            r = mid - 1
    return -1

其实这里有一个bug,如果在求mid的时候,lr过大了,那么就容易出现溢出,这样就尴尬了。所以最后改进一下,既然是加法不行,那就来减法的,于是改进之后:

mid = int((l + (r-l))/2)

这样就可以了。

二分搜索树的优势

查找表:

如果键的值是整数,那么使用数组就可以达到目的。但如果像是字符串这些,就不能了,所以就出现了字典。实现查找表最基础的方式就是二分搜索树。

method

search

insert

delete

array

order array

binary tree

二分搜索树在插入查找删除方面都是很有效率的。

每一个节点的键值大于左孩子,小于右孩子,以左右孩子为子树的节点仍为二分搜索树。上面讲的二叉堆一定是要完全二叉树,但是是二分搜索树就不一定是完全二叉树了,只要满足键值大于左孩子小于右孩子即可。

二分搜索树的实现

定义一棵二叉树:

class BST(object):
    class _node(object):
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.left = None
            self.right = None
    def __init__(self):
        self.root = None
        self.count = 0

    def size(self):
        return self.count

    def isempty(self):
        return self.count == 0

定义一个节点,键值,对应的值,查找就是通过键值查找,而不是通过value查找。 插入: 插入就很简单了,递归选择左右子树插入,如果发现有重复的键值了,直接替换,没有就新建立一个。

    def insert(self, key, value):
        self.root = self.__insert(self.root, key, value)

    def __insert(self, node, key, value):
        if node == None:
            return self._node(key, value)
        elif key == node.key:
            node.value = value
        elif key < node.key:
            node.left = self.__insert(node.left, key, value)
        else:
            node.right = self.__insert(node.right, key, value)
        return node

是否包含: 和插入其实差不多,查找也是,都是那么几个判断:

    def contain(self, key):
        return self.__contain(self.root, key)

    def __contain(self, node, key):
        if node == None:
            return False
        elif node.key == key:
            return True
        elif key < node.key:
            return self.__contain(node.left, key)
        else:
            return self.__contain(node.right, key)

查找:

    def search(self, key):
        return self.__search(self.root, key)
        pass

    def __search(self, node, key):
        if node == None:
            return None
        elif node.key == key:
            return node.value
        elif node.key < key:
            return self.__search(node.right, key)
        else:
            return self.__search(node.left, key)
        pass

一言不合就递归。

二叉树的深度优先遍历

前序遍历:先访问当前节点,再依次递归访问左右子树。 中序遍历:先访问左子树,再访问自身节点,最后访问右子树。 后序遍历:先访问左右子树,最后再访问自身节点。

前序遍历:

中序遍历:

后序遍历:

二叉树每一个节点都会被访问三次,上面的三个点就代表了访问的三次,分别代表了前中后序,前序遍历就是只要到达了前序遍历的那个点才输出,中序遍历就是到达了中序遍历的那个点才输出,后序遍历也一样。 用递归处理其实很简单:

    def preOrder(self):
        self.__preOrder(self.root)
        pass

    def __preOrder(self, node):
        if node != None:
            print('key: ', node.key, ' value: ', node.value)
            self.__preOrder(node.left)
            self.__preOrder(node.right)

    def inOrder(self):
        self.__inOrder(self.root)
        pass

    def __inOrder(self, node):
        if node != None:
            self.__inOrder(node.left)
            print('key: ', node.key, ' value: ', node.value)
            self.__inOrder(node.right)
        pass

    def postOrder(self):
        self.__postOrder(self.root)
        pass

    def __postOrder(self, node):
        if node != None:
            self.__postOrder(node.left)
            self.__postOrder(node.right)
            print('key: ', node.key, ' value: ', node.value)

对于这些遍历的应用,一个就是释放元素的时候,在C++里面释放内存就可以使用后序遍历的方法了。

    def destory(self):
        self.__destory(self.root)
        pass

    def __destory(self, node):
        if node != None:
            self.__destory(node.left)
            self.__destory(node.right)
            del node

深度优先遍历是先以树的深度为准,左子树遍历完再遍历右子树。广度遍历是先以范围为准,先最大范围的遍历,层序遍历就是一个广度优先遍历。

二叉树的广度优先遍历

比如这么一棵二叉树,访问了28之后等于就是这一层完了,那么就要访问它的左右子叶,16,30。所以整个顺序就是

。实现这个操作需要一个队列,遍历到28的时候,把它的左右子树塞进队列里面,接着把队首的元素输出,把输出元素的左右子树右赛进去,这样循环直到队列没有元素为止。 按照上面的做法实现一下即可:

    def levelOrder(self):
        self.__levelOrder(self.root)

    def __levelOrder(self, node):
        q = queue.Queue()
        q.put(node)
        while(q.empty() == False):
            now = q.get()
            print(now.key, end=' ')
            if (now.left != None):
                q.put(now.left)
            if (now.right != None):
                q.put(now.right)
        pass

结果显示。四种遍历结果的显示。

删除最大值和最小值

寻找最小值其实就是不断的找左叶子的过程,选择最大值就是不断找右叶子的过程。

如果是这种情况,那么删除最小就很简单了,直接扔掉就好了,但如果是:

22有右孩子,那么直接把右孩子的那颗树拉上来就好了,因为任何一棵子树都是符合二叉树的性质,最大值也一样。这里是58,那么直接把子树拉上来就好了,最小值不可能有左子树,最大值不可能有右子树。 所以删除最大值和最小值就很简单了:

    def removeMin(self):
        if self.root != None:
            self.root = self.__removeMin(self.root)
            pass

    def __removeMin(self, node):
        if node.left == None:
            right = node.right
            del node
            self.count -= 1
            return right
        node.left = self.__removeMin(node.left)
        return node

    def removeMax(self):
        if self.root != None:
            self.root = self.__removeMax(self.root)
            pass

    def __removeMax(self, node):
        if node.right == None:
            left = node.left
            del node
            self.count -= 1
            return left
        node.right = self.__removeMax(node.right)
        return node
删除随便一个值

这个就和上面的有点不一样了,有三种情况,都有左右子叶,只有左子叶,只有右子叶,首先是如果有左右子叶:

要删除59,首先要从子树找一个可以替代的,右子树比左子树要大,所以肯定要从右子树选择,但是又要把右子树所以的元素都要小,所以要选择右子树最小的一个元素。就是59了。所以如果都有左右节点,那么就要找右子树最小的元素进行替代。如果是只有左子树或者是右子树,那就直接把左右子树拉上来就好了。

    def remove(self, key):
        self.__remove(self.root, key)
        pass

    def __remove(self, node, key):
        if node == None:
            return None
        elif node.key > key:
            node.left = self.__remove(node.left, key)
            return node
        elif node.key < key:
            node.right = self.__remove(node.right, key)
        else:
            if node.left == None:
                right = node.right
                del node
                self.count -= 1
                return right

            elif node.right == None:
                left = node.left
                del node
                self.count -= 1
                return left

            else:
                successor = copy.deepcopy(self.__minmum(node.right))
                successor.right = self.__removeMin(node.right)
                successor.left = node.left
                return successor

代码同样是很简单了,直接递归处理。

二叉树的总结

大多数情况下我们还是把二叉树当成是一种查找表来进行的,主要关注的任务主要就是如何查找一个key的value。 二叉树还有一个比较好的性质,它有一定的顺序性。首先就是最大值和最小值,已经实现过了,还有找前驱和后继的问题。还有一个,选择floor和ceil的问题,寻找最小上界最大下界,如果这个数是在二叉树里面存在的,那么就本身,如果不存在,如下:

二分搜索树的局限性,同一堆的数据,不同的插入顺序是会存在不同的二叉树的

这个时候,这个二叉树就会退化成一个链表,所以这时候就需要AVL树来调整了,比较经典的就是红黑树,而这棵树它的左右子树高度是不会超过1的。


并查集

首先是一个连接问题:

想知道相邻的两个点有没有连接,直接看有没有线就好了,但是如果我想找到左上角的点和右下角的点有没有连接,这就尴尬了。 所以并查集一个比较好的应用就是连接问题,网络之间的连接状态。比如用户之间形成的网络,看看这个用户能不能通过好友认识另外一个人。就是qq可能认识的人。

路径问题和连接问题 连接问题比路径问题要回答的问题少,连接问题只需要回答是不是连接的即可,而路径问题就要回答哪条路径是最短的。所以连接问题会比路径问题要快。对于排序也是一样,查找一个元素,二分查找是很快的,比顺序查找要快,因为顺序查找其实回答了更多的问题,比如这个元素排名第几,查找任意一个元素等等。选择问题也是一样,快排更块,因为它只是找了这个元素,其他回答的问题更多,所以时间更长。

并查集的构成和作用

并查集要支持的主要就是两个操作: union(p,q)连接两个节点pq find(p)查找p是哪个组的 isConnected(p,q)两个节点是否连接在一起的。 并查集可以用最简单的的一个方法表示,只用一个数组和下标表示:

0到4都是0,所以0到4着5个元素是互相连接的。5到9都是1那么就是互相联系的。

这样就是奇数互相联系,偶数互相联系。简单实现一些,union的version1:

class UnionFind(object):
    id = None
    count = 0

需要有一个数组,也就是id,需要一个数量count。

    def unionFind(self, n):
        self.count = n
        self.id = np.zeros(n)
        for i in range(n):
            self.id[i] = i

创建一个并查集

    def find(self, p):
        if p >= 0 and p < self.count:
            return self.id[p]

找到当前数字的id号是多少。

    def isConnected(self, p, q):
        return self.find(p) == self.find(q)
        pass

判断他们之间是否有联系。

    def union(self, p, q):
        pID = self.find(p)
        qID = self.find(q)
        if pID == qID:
            return
        for i in range(self.count):
            if self.id[i] == pID:
                self.id[i] = qID
            pass

两个元素拉上联系。这种方式实现的并查集查找方式很快,但是union的方法就会很慢。union是

并查集的另一种实现思路

上面一种的实现方式我们称为是quick find方法,查找方式是很快的,但是union操作就很慢,所以现在要实现一种比较高效的方法。 首先将每一个元素看成是一个节点,用一个数组的下标来存储和这个节点[图片上传中...(M}7EXC0KSP(N2})M%MD6P.png-89c85b-1534299092134-0)] 合并的另一个节点,所以一开始,每一个节点都是指向自己,因为没有其他节点和他一起:

现在如果想union(4, 3),那就要把4放在3下,因为3的下标就是指向了和他union的那个点:

有点像树的结构,后的union都是互相合并根节点即可。现在要union(3, 8),一般都是前一个指后面的一个,这样4也会跟着指过去:

同样union(6, 5):

如果合并的是(9, 4),那就是不是接4下面了,因为4下面有3了,所以如果是合并,接的是根节点,所以找4的根节点,4下面的是3,3下面的是8,8下面是8,所以8就是根节点,所以就要把9下面的9变成8了:

union(2, 1)

就是这样的合并方式。我们想找到两个节点是不是有联系的,只需要找到他们的根看看是不是一样的,所以现在简单实现一些代码:

class unionFind_version2(object):
    parent = None
    count = 0

    def unionFind_version2(self, count):
        self.parent = np.zeros(count)
        self.count = count
        for i in range(self.count):
            self.parent[i] = i

    def find(self, p):
        if p >= 0 and p < self.count:
            while p != self.parent[p]:
                p = int(self.parent[p])
            return p

    def isConnected(self, p, q):
        return self.find(p) == self.find(q)

    def union(self, p, q):
        pID = self.find(p)
        qID = self.find(q)
        if pID == qID:
            return
        self.parent[pID] = qID

代码实现也很简单了。

并查集version2版本的优化

有一个特殊的情况,事实上union(9, 4)和union(4, 9)是一样的,但是有时候会出现极端的情况:

如果是(4, 9)

如果是(9, 4)

明显是第二种好,链太长对于两个元素的查找都会消耗很大的时间。所以可以改进一下,增加一个size数组,然后合并前看看哪个元素对应的树是最小的,最小的哪个就合并过来。

class unionFind_version3(object):
    parent = None
    size = None
    count = 0

    def unionFind_version3(self, count):
        self.parent = np.zeros(count)
        self.size = np.zeros(count)
        self.count = count
        for i in range(self.count):
            self.parent[i] = i
            self.size[i] = 1

    def find(self, p):
        if p >= 0 and p < self.count:
            while p != self.parent[p]:
                p = int(self.parent[p])
            return p

    def isConnected(self, p, q):
        return self.find(p) == self.find(q)

    def union(self, p, q):
        pID = self.find(p)
        qID = self.find(q)
        if pID == qID:
            return
        if self.size[pID] < self.size[qID]:
            self.parent[pID] = qID
            self.size[qID] += self.size[pID]
        else:
            self.parent[qID] = pID
            self.size[pID] += self.size[qID]

再次优化

事实上还是存在着极端的情况:

如果是合并,那么就会出现:

事实上:

这样才是比较好的合并方式,所以合并到哪一个并不应该通过数量来判断,而是通过树的高度来判断,也就是rank。

代码实现:

class unionFind_version4(object):
    parent = None
    rank = None
    count = 0

    def unionFind_version4(self, count):
        self.parent = np.zeros(count)
        self.rank = np.zeros(count)
        self.count = count
        for i in range(self.count):
            self.parent[i] = i
            self.rank[i] = 1

    def find(self, p):
        if p >= 0 and p < self.count:
            while p != self.parent[p]:
                p = int(self.parent[p])
            return p

    def isConnected(self, p, q):
        return self.find(p) == self.find(q)

    def union(self, p, q):
        pID = self.find(p)
        qID = self.find(q)
        if pID == qID:
            return
        if self.rank[pID] < self.rank[qID]:
            self.parent[pID] = qID
        elif self.rank[qID] < self.rank[pID]:
            self.parent[qID] = pID
        else:
            self.parent[pID] = qID
            self.rank[qID] += 1

要注意的其实就是最后一个union操作了,如果是小于的话改变不需要改变,因为合并之后还是高度不变,如果都是一样的,那么无论是合并到那一课树上都会存在rank+=1的情况。

路径压缩 Path Compression

之前的union合并可能会出现这样一种情况:

这样明显是不好的,没一次查找就相当于是遍历,所以可以考虑把4节点往上拉一下:

再往上拉一下:

把当前节点连上他parent节点的parent节点上,所以只需要修改一下find:

        if p >= 0 and p < self.count:
            while p != self.parent[p]:
                self.parent[p] = int(self.parent[int(self.parent[p])])
                p = int(self.parent[p])
            return p

刚刚那种形式还可以再压缩,因为如果可以直接接到根节点的话查找是更加快的。

压缩成这种形式,查找的速度更加快,再次优化:

        if p >= 0 and p < self.count:
            if p != int(self.parent[p]):
                self.parent[p] = int(self.find(int(self.parent[p])))
            return int(self.parent[p])

通过递归处理,如果当前节点不是,那就让它的节点等于它的根。而在递归回去的时候把经过的节点都处理了。


图 Graph

图一般就是用于解决以上结构的一种数据结构。图主要由两部分构成,节点Vertex和边Edge。 图也分两类,无向图和有向图。

无向图

有向图

下面所讲的算法都将是围绕无向图展开,但是事实上这些算法也是同样适用于有向图,因为无向图也是一种特殊的有向图:

根据权重,图也可以分为有权图和无权图。如果每一条边都是没有权值的,单单就是一条边,那么就是无权图了。 图的连通性:

这三个图就是不连通的。 简单图:就是有自环边和平行边。

事实上这两个边没有意义的,自环边是没有用的,平行边在最小路径的时候,只要选择最小的那条边就好了。

图的表示方法

1.比较简单的方法就是邻接矩阵了,用一个矩阵来表示一个图。

可以使用一个矩阵来表示,01相连,那么0到1和1到0就是1了,因为是无向图,所以是左右对称的,当然这个图也是可以变成有向图表示的,无向图的话是对称,symmetrical。有向图不是对称的就是了。

2.邻接表的表示方法

首先是用一个数组来表示所以的节点,如果是有链接那么就再和有链接的节点下面用一个链表连上即可。首先邻接表肯定是比邻接矩阵的空间要小,而且邻接矩阵可能会是一个稀疏矩阵,浪费很多空间。所以,邻接矩阵适合表示一个稀疏矩阵,邻接表适合表示稠密矩阵。

图的实现

邻接矩阵的实现
class DenseGraph(object):
    n, m = None, None
    directed = None
    __g = None
    def __init__(self, n, directed):
        self.n = n
        self.m = 0
        self.directed = directed
        self.__g = np.array((n, n))
    def v(self):
        return self.n

    def e(self):
        return self.m

    def addEdge(self, v, w):
        if self.hasEdge(v, w) == 1:
            return
        if v >= 0 and v < self.n:
            if w >= 0 and w < self.n:
                self.__g[v][w] = 1
                if self.directed != True:
                    self.__g[w][v] = 1
                self.m += 1
        pass

    def hasEdge(self, v, w):
        if v >= 0 and v < self.n:
            if w >= 0 and w < self.n:
                return self.__g[v][w]
邻接表的实现
class SparseGraph(object):
    n, m = None, None
    directed = None

    def __init__(self, n, directed):
        self.n = n
        self.directed = directed
        self.__g = list()
        for i in range(n):
            self.__g.append(list())

    def v(self):
        return self.n

    def e(self):
        return self.m

    def addEdge(self, v, w):
        if v >= 0 and v < self.n:
            if w >= 0 and w < self.n:
                self.__g[v].append(w)
                if v != w and self.directed != True:
                    self.__g[w].append(v)
                self.m += 1

    def hasEdge(self, v, w):
        if v >= 0 and v < self.n:
            if w >= 0 and w < self.n:
                for i in range(len(self.__g[v])):
                    if self.__g[v][i] == w:
                        return True
                return False

图的遍历

遍历邻边

这是一种比较简单的遍历方式,遍历每一个节点和他相连的节点:

如果是邻接矩阵的形式,那么就需要遍历每一行,看看哪一个是1,是1的就拿出来。所以邻接矩阵的复杂度是

;换成邻接表就很简单了,因为每一个节点下面链接的就是和他链接的节点,直接遍历就好了,所以是

。 常规实现就是遍历,不按套路出牌,实现一个迭代器来进行迭代处理。邻接矩阵的迭代器实现:

    class FormIterator(object):
        G = None
        __g = None
        v = None
        index = None

        def __init__(self, G, v):
            self.G = G
            self.__g = G._DenseGraph__g
            self.v = v
            self.index = -1
            pass

        def begin(self):
            self.index = -1
            return self.next()

        def next(self):
            for self.index in range(self.index + 1, self.G.v()):
                if self.__g[self.v][self.index] == 1:
                    return self.index
            return -1

        def end(self):
            if self.index == self.G.v()-1:
                self.index += 1
                return True
            return self.index < self.G.v()

起始,下一个,结束,结束条件有多加了判断,因为源代码是C plus plus写的,for循环有些不一致,翻译成python代码就有点问题,所以多加了一个判断。 邻接表:

    class MatrixIterator(object):
        __g = None
        v = 0
        index = 0
        def __init__(self, G, v):
            self.__g = G._SparseGraph__g
            self.v = v
            self.index = 0
            pass

        def begin(self):
            self.index = 0
            if len(self.__g[self.v]) > 0:
                return self.__g[self.v][self.index]
            return -1

        def next(self):
            self.index += 1
            if self.index < len(self.__g[self.v]):
                return self.__g[self.v][self.index]
            return -1

        def end(self):
            return self.index >= len(self.__g[self.v])

这个也是一样。

深度优先遍历

和树的遍历其实差不多,都是先往深处走再回来。图的节点是需要一个标记来知道有没有被访问了的。

首先是0号节点,0号节点下面有两个,1和2,。先看看1。

1下面有0,0访问过了,于是退回0,0又跑到2,2下面也是0,所以又退回到0,12都看了,然后看5,5下面0看过了,看3,3又看4,4又看3,3看过了看5,5也看过了所以看6,6只有04,两个都看过了,所以退回4,4又退回3,3又退回5,5又退回0,完成遍历。 这种遍历方式有一个很重要的应用,求连通分量。

上图三个图之间没有联系那么这就有三个连通分量。 用一个TXT文件来存储图:

第一行表示点和边的数量。

class ReadGraph(object):
    isVisited = None
    count = 0
    def ReadGraph(self, filename, G):
        df = pd.read_csv(filename, names=['point'])
        total = df.iloc[0].values[0].split(' ')
        V = int(total[0])
        E = int(total[1])
        if G.v() != V:
            print('error with edge!')
            return
        for i in range(E):
            ab = df.iloc[i+1].values[0].split(' ')
            a = int(ab[0])
            b = int(ab[1])
            if a >= 0 and a < V:
                if b >= 0 and b < V:
                    G.addEdge(a, b)

使用ReadGraph这个类来包装一下。使用一个求连通分量的应用来实现深度优先遍历。

    def Component(self, G):
        self.count = 0
        self.isVisited = np.arange(G.v())
        for i in range(G.v()):
            self.isVisited[i] = False
        for i in range(G.v()):
            if self.isVisited[i] == False:
                self.BFS(G, i)
                self.count += 1

    def BFS(self, G, v):
        self.isVisited[v] = True
        iter = G.Iterator(G, v)
        w = iter.begin()
        while iter.end() == True:
            if w != -1:
                if self.isVisited[w] == False:
                    self.BFS(G, w)
            w = iter.next()

    def vount(self):
        return self.count

其实不复杂,就是简单的递归一下,首先是要遍历一下所有的点了,如果当前这个点没有被遍历过,那么就从这个点进行BFS,往下看,用对应的迭代器查看,如果找到了下一个元素,而且这个元素没有被访问过,那么就可以从这个元素开始BFS。 python实现数据结构确实有点不方便,这个for循环封装的太好了,迭代器都只能用while来替换。

寻路问题

既然有了深度优先变量,可以知道遍历过哪一个节点了,那么就可以知道到底经过了哪一个节点了。 其实和上一个节点是一样的,和之前的一样,首先要准备一个isVisited数组看看是否这个节点被访问了,还要准备一个from数组用来存储是哪一个节点到哪一个节点。

class Path(object):
    G = None
    s = 0
    isVisited = None
    Pfrom = None
    paths = []

    def BFS(self, G, v):
        self.isVisited[v] = True
        iter = G.Iterator(G, v)
        w = iter.begin()
        while iter.end() == True:
            if w != -1:
                if self.isVisited[w] == False:
                    self.Pfrom[w] = v
                    self.BFS(G, w)
            w = iter.next()

其实就是复制之前的BFS,然后在前面加上Pfrom[w] = v,意思就是从w可以到v。

    def hasPath(self, w):
        return self.isVisited[w]

    def path(self, w):
        stack = []
        p = w
        print(self.Pfrom)
        while p != -1:
            stack.append(p)
            p = self.Pfrom[p]
        for i in range(len(stack)):
            self.paths.append(stack.pop(0))

    def show(self):
        for i in range(len(self.paths)):
            print(self.paths[i], end = '')
            if i != len(self.paths) - 1:
                print('->', end='')
            else:
                print()
            pass

    def __init__(self, G, s):
        self.isVisited = np.arange(G.v())
        self.Pfrom = np.arange(G.v())
        for i in range(G.v()):
            self.isVisited[i] = False
            self.Pfrom[i] = -1
        self.s = s

这样就完成了。

    p = Path.Path(G1, 0)
    p.BFS(G, 6)
    p.path(2)
    p.show()

以起点为0建立一条从0到其他节点的路径信息。

还是很正常的打印。这里没有考虑平行边的问题,如果有平行边,那就只需要考虑那条路更近替换就好了,也就是权值对比。 深度优先遍历邻接表的复杂度是

,邻接矩阵就是

广度优先遍历

广度优先那自然就是凹求有一个队列了,首先先要把这个根节点扔进队列里面,每一次就看看这个队列是不是空的,如果不是空的就把这个队列的第一个元素丢出来,再把丢出来的这个元素的邻接节点都扔进队列里面,不断重复上诉步骤。和树的广度优先遍历是差不多一致的。 还是用刚刚上图的例子:

广度优先遍历是可以知道遍历出来的这个点到原点的距离是多少的,所以可以用来求最短路径。 使用最短路径的例子来实现广度优先遍历。

    def __init__(self, G, s):
        self.G = G
        self.s = s
        self.visited = np.arange(self.G.v())
        self.Pfrom = np.arange(self.G.v())
        self.ord = np.arange(self.G.v())
        for i in range(G.v()):
            self.visited[i] = False
            self.ord[i] = -1
            self.Pfrom[i] = -1

        q = list()
        q.append(s)
        self.visited[s] = True
        self.ord[s] = 0
        while len(q) != 0:
            v = q.pop(0)
            iter = G.Iterator(G, v)
            w = iter.begin()
            while iter.end() == True:
                if w != -1:
                    if self.visited[w] == False:
                        q.append(w)
                        self.visited[w] = True
                        self.Pfrom[w] = v
                        self.ord[w] = self.ord[v] + 1
                w = iter.next()

ord数组就是距离,表示当前点到原点的距离,from就是从哪个点到哪个点。当把这个点扔进队列里面的时候,就意味着这个元素就要被访问的了,所以设计已经被访问,距离就是上一个点的距离加1了。 其他的函数都是一样的,使用栈往回找即可。

    def hasPath(self, w):
        return self.visited[w]

    def path(self, w):
        stack = []
        p = w
        print(self.Pfrom)
        while p != -1:
            stack.append(p)
            p = self.Pfrom[p]
        for i in range(len(stack)):
            self.paths.append(stack.pop(-1))

    def show(self):
        for i in range(len(self.paths)):
            print(self.paths[i], end = '')
            if i != len(self.paths) - 1:
                print('->', end='')
            else:
                print()
            pass

上面的BFS下面是DFS,下面的路径就是最短路径了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏JAVA高级架构

Java数据结构与算法解析——2-3树

二叉查找树对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率,...

40570
来自专栏电光石火

HashSet/HashMap详解

HashMap和HashSet是Java Collection接口两个重要的成员,其中HashMap是Map接口常用的实现类,HashSet是Set接口常用...

240100
来自专栏腾讯IVWEB团队的专栏

ES6 中的 Set

ES6 新增了几种集合类型,本文主要介绍Set以及其使用。Set对象是值的集合,你可以按照插入的顺序迭代它的元素。 Set中的元素只会出现一次,即 Set 中的...

84800
来自专栏大闲人柴毛毛

贪心算法(五)——迪杰斯特拉算法

问题描述 给一个有向无环带权图,并给一个起点,求出该原点到所有顶点的最短路径。 ? 数据结构 dis: Map<String,Integer> dis; ...

41790
来自专栏用户画像

7.7.5 最佳归并树

文件经过置换-选择排序之后,得到的是长度不等的初始归并段。下面讨论如何组织初始归并段的归并顺序,使I/O访问次数最少。

9110
来自专栏Android机动车

数据结构学习笔记——线性表(中)

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着,这些数据元素可以存在内存未被占用的...

9430
来自专栏机器学习实践二三事

leetcode之-题19

题目 [图片] Given a linked list, remove the nth node from the end of list and re...

20570
来自专栏海天一树

二叉树的分层遍历

给定一棵二叉树,要求从上到下从左到右分层输出该二叉树的节点值。 ? bitree.png 一、递归法 二叉树本身就带有递归属性,通常我们可以用递归方法解决。假设...

29370
来自专栏码匠的流水账

聊聊storm nimbus的mkAssignments

storm-2.0.0/storm-server/src/main/java/org/apache/storm/daemon/nimbus/Nimbus.jav...

13420
来自专栏用户3030674的专栏

Java 工具类—日期获得,随机数,系统命令,数据类型转换

15410

扫码关注云+社区

领取腾讯云代金券