图的两种遍历
何谓遍历：从图中某一顶点出发，访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程谓之图的遍历（Traversing Graph）
深度优先遍历（Depth First Search）
该方法相当于一根筋走到底，以图1左边为例。假设每次都选择右边的路口，当右边无路可走或者已经走过时，返回上一个节点，选择左边的路口。遍历路线为：
A-B-C-D-E-F-G-H-I
图1-DFS遍历过程
邻接矩阵
思路：
1.需要一个数组存储哪些顶点遍历过，哪些顶点没有遍历。visitied = []
2.其实是一个递归的过程，每次改变的只是“起始节点”
关注点：
1.dfsTravese()函数中，第一个for循环，可看成对邻接矩阵的行循环，避免一些“孤立”（在其他分支上）的点被遗漏，如图1-DFS遍历过程中的 I 节点。
2.每次调用dfs()函数时都需要检查一遍该节点是否已经被遍历过。
3.dfs(nodeIndex)函数中的for循环可看做是邻接矩阵中的列的循环
class adjacencyMatrix(object):
def __init__(self, nodeNum, edgeNum):
# 存储邻接矩阵中节点的个数
self.nodeNum = nodeNum
# 存储邻接矩阵中节点边的数量
self.edgeNum = edgeNum
# 在遍历时检查节点是够被使用过
self.visited = None
# 记录每个节点实际对应的名字
self.nodeNameList = ['v'+str(_) for _ in range(nodeNum)]
# 记录每个节点下标
self.NodeList = []
# 记录每条边的下标，（定位权重用的）
self.EdgeList = []
for i in range(nodeNum):
self.EdgeList.append([NULLFLAG] * edgeNum)
'''
使用邻接矩阵创建图的时候，其实就是构造一个长宽均为节点数量的正方形。
行和列的交汇点代表边的权重
通过 头结点和尾节点的下标，可以定位连接边的权重值。
'''
def createGraph(self, prevIndex, weight, nextIndex):
if prevIndex not in self.NodeList:
self.NodeList.append(prevIndex)
self.EdgeList[prevIndex][prevIndex] = 0
if nextIndex not in self.NodeList:
self.NodeList.append(nextIndex)
self.EdgeList[nextIndex][nextIndex] = 0
self.EdgeList[prevIndex][nextIndex] = weight
self.EdgeList[nextIndex][prevIndex] = weight
'''
递归调用节点：遍历行节点，然后递归调用行节点内对应的所有节点
需要记录遍历过程
'''
def dfsTravese(self):
self.visited = [False] * self.nodeNum
for inode in range(self.nodeNum):
if self.visited[inode] is False:
self.dfs(inode)
def dfs(self, nodeIndex):
print(self.nodeNameList[nodeIndex])
self.visited[nodeIndex] = True
for j in range(self.nodeNum):
if (self.EdgeList[nodeIndex][j] != NULLFLAG) and (self.visited[j] is False):
self.dfs(j)
邻接表
class AdjacencyList(object):
def __init__(self):
self.vertex = {}
self.visited = None
def createGraph(self, startIndex, weight, endIndex):
if startIndex not in self.vertex.keys():
vertex_node = VertexNode(startIndex, 'v' + str(startIndex), None)
self.vertex[startIndex] = vertex_node
if endIndex not in self.vertex.keys():
vertex_node = VertexNode(endIndex, 'v' + str(endIndex), None)
self.vertex[endIndex] = vertex_node
edgeNode = EdgeNode(endIndex, 'v' + str(endIndex), weight=weight, nextNode=None)
tmp = self.vertex[startIndex].firstEdge
edgeNode.nextNode = tmp
self.vertex[startIndex].firstEdge = edgeNode
def dfsTravese(self):
self.visited = [False]*len(self.vertex)
for i in range(len(self.vertex)):
if self.visited[i] == False:
self.dfs(i)
def dfs(self, i):
print("node name is ", self.vertex[i].name)
self.visited[i] = True
node = self.vertex[i].firstEdge
while node:
if self.visited[node.index] == False:
self.dfs(node.index)
node = node.nextNode
广度优先遍历
在广度优先遍历中，最直观的理解是：从第一行（邻接矩阵），依次遍历每一行对应的所有列，操作（可以为输出等）与该行对应的所有点。具体可参考树的层序遍历，与之不同的是，广度优先遍历借助了《队列》先进先出的思想来实现。
广度优先遍历
邻接矩阵
1、第一层循环：遍历举矩阵中的所有行，防止遗漏点，若改点没有被访问过，则加入队列中，并将改点标记为已经访问。
2、当对列不为空时，依次取出队列中的点，并将与该点相连的所有点进行检查，若无访问记录，则加入队列。
class adjacencyMatrix(object):
def __init__(self, nodeNum, edgeNum):
# 存储邻接矩阵中节点的个数
self.nodeNum = nodeNum
# 存储邻接矩阵中节点边的数量
self.edgeNum = edgeNum
# 在遍历时检查节点是够被使用过
self.visited = None
# 记录每个节点实际对应的名字
self.nodeNameList = ['v'+str(_) for _ in range(nodeNum)]
# 记录每个节点下标
self.NodeList = []
# 记录每条边的下标，（定位权重用的）
self.EdgeList = []
for i in range(nodeNum):
self.EdgeList.append([NULLFLAG] * edgeNum)
'''
借助了队列
把每一行对应的节点加入队列中，若队列空则下一行。
另外，需要遍历队列中的元素对应的行中的所有元素
'''
def bfsTravese(self):
q = Queue()
self.visited = [True] * self.nodeNum
for i in range(self.nodeNum):
if self.visited[i] is True:
q.put(i)
print('node name is ', self.nodeNameList[i])
self.visited[i] = False
while q:
if q.empty():
return
nodeIndex = q.get()
# print('node name is ', self.nodeNameList[nodeIndex])
for j in range(self.nodeNum):
if (self.visited[j] is True) and (self.EdgeList[nodeIndex][j] != NULLFLAG):
q.put(j)
self.visited[j] = False
print('node name is ', self.nodeNameList[j])
邻接表
class AdjacencyList(object):
def __init__(self):
self.vertex = {}
self.visited = None
def bfs(self):
self.visited = [0] * len(self.vertex)
q = Queue()
for i in range(len(self.vertex)):
if self.visited[i] == 0:
self.visited[i] = 1
q.put(self.vertex[i].index)
while q:
if q.empty():
break
visitIndex = q.get()
print(self.vertex[visitIndex].name)
edgeNode = self.vertex[visitIndex].firstEdge
while edgeNode is not None:
if self.visited[edgeNode.index] == 0:
self.visited[edgeNode.index] = 1
q.put(edgeNode.index)
edgeNode = edgeNode.nextNode
参考文献
- 《大话数据结构》
