Data Structurestackheapheap的实现索引堆tree并查集图 Graph
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,16,30,13,22,29,42]](https://ask.qcloudimg.com/http-save/yehe-1169332/pk04w0e8gw.svg)
。实现这个操作需要一个队列，遍历到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，下面的路径就是最短路径了。