图python(数据结果与算法)---遍历
图遍历是指:
从任意一个顶点出发对图中每个顶点访问且仅访问一次的过程。
因为图中可能存在回路,为了避免对一个顶点的重复访问可以增设一个辅助的数组visited[],全部初始化为0,一旦访问过,置位visited[i] = 1,:
图的遍历比较复杂,需要考虑:
- 指定遍历的第一个顶点
- 由于一个顶点和多个顶点的相邻,需要在多个邻接顶点间确定访问次序
- 由于图中存在回路,必须对访问过的顶点做标记,防止出现重复访问同一顶点的情况。
图的遍历可分为:
- 深度优先遍历
- 广度优先遍历
1图的广度优先搜索算法(BFS,Breadth-First-Search)
遍历法则是利用队列和递归技巧来遍历的,也是从图的某一顶点开始遍历,被访问的顶点就做上已被访问过的记号。
bfs总是先访问完同一层的结点,然后才继续访问下一层结点,
步骤
1 创建一个队列,遍历的起始点放入队列
2 从队列中取出一个元素,打印它,并将其未访问过的子结点放到队列中
3 重复2,直至队列空
时间复杂度:基本与图的规模成线性关系
故广度优先遍历的顺序是:顶点1,顶点2,顶点5,顶点3,顶点4,
其遵循“先被访问的顶点,其邻接点先被访问”规则,
(1)若访问的是无向图:则依次访问顶点v邻接到的未被访问的邻接点,再依次访问这些邻接点未被访问的邻接点,直到所有与顶点v连通的顶点都被访问。
若是有向图:则依次访问顶点v邻接到的未被访问的邻接点,再依次访问这些邻接点未被访问的邻接点,直到从顶点v出发到达所有顶点都被访问。
(2)若图中还有未被访问的顶点,则从中选择一个顶点并重复执行(1).
MAXSIZE=10 #定义队列的最大容量
front=-1 #指向队列的前端
rear=-1 #指向队列的末尾
class Node:
def __init__(self,x):
self.x=x #顶点数据
self.next=None #指向下一个顶点的指针
class GraphLink:
def __init__(self):
self.first=None
self.last=None
def my_print(self):
current=self.first
while current!=None:
print('[%d]' %current.x,end='')
current=current.next
print()
def insert(self,x):
newNode=Node(x)
if self.first==None:
self.first=newNode
self.last=newNode
else:
self.last.next=newNode
self.last=newNode
#队列数据的存入
def enqueue(value):
global MAXSIZE
global rear
global queue
if rear>=MAXSIZE:
return
rear+=1
queue[rear]=value
#队列数据的取出
def dequeue():
global front
global queue
if front==rear:
return -1
front+=1
return queue[front]
#广度优先查找法
def bfs(current):
global front
global rear
global Head
global run
enqueue(current) #将第一个顶点存入队列
run[current]=1 #将遍历过的顶点设置为1
print('[%d]' %current, end='') #打印出该遍历过的顶点
while front!=rear: #判断当前的队伍是否为空
current=dequeue() #将顶点从队列中取出
tempnode=Head[current].first #先记录当前顶点的位置
while tempnode!=None:
if run[tempnode.x]==0:
enqueue(tempnode.x)
run[tempnode.x]=1 #记录已遍历过
print('[%d]' %tempnode.x,end='')
tempnode=tempnode.next
#声明图的边线数组
Data=[[0]*2 for row in range(20)]
Data =[[1,2],[2,1],[1,3],[3,1],[2,4], \
[4,2],[2,5],[5,2],[3,6],[6,3], \
[3,7],[7,3],[4,5],[5,4],[6,7],[7,6],[5,8],[8,5],[6,8],[8,6]]
run=[0]*9 #用来记录各顶点是否遍历过
queue=[0]*MAXSIZE
Head=[GraphLink]*9
print('图的邻接表内容:') #打印图的邻接表内容
for i in range(1,9): #共有8个顶点
run[i]=0 #把所有顶点设置成尚未遍历过
print('顶点%d=>' %i,end='')
Head[i]=GraphLink()
for j in range(20):
if Data[j][0]==i: #如果起点和链表头相等,则把顶点加入链表
DataNum = Data[j][1]
Head[i].insert(DataNum)
Head[i].my_print() #打印图的邻接标内容
print('广度优先遍历的顶点:') #打印广度优先遍历的顶点
bfs(1)
print()
图的邻接表内容:
顶点1=>[2][3]
顶点2=>[1][4][5]
顶点3=>[1][6][7]
顶点4=>[2][5]
顶点5=>[2][4][8]
顶点6=>[3][7][8]
顶点7=>[3][6]
顶点8=>[5][6]
广度优先遍历的顶点:
[1][2][3][4][5][6][7][8]
2图的深度优先遍历(DFS,Deep-First-Search )
深度优先遍历算法dfs通俗的说就是“顺着起点往下走,直到无路可走就退回去找下一条路径,直到走完所有的结点”。这里的“往下走”主是优先遍历结点的子结点。
类似于树的先序遍历,一个顶点u为起始点访问其邻接点v0,再访问v0的未被访问的邻接点v1,然后从v1出发继续进行类似的访问,直到所有的邻接节点都被访问,然后退到前一个被访问的顶点,看是否有其他未被访问的顶点,若有再进行类似的访问。若无继续回退,直到图中的所有顶点都被访问为止。
这种遍历的方法结合了递归和堆栈两种数据结构的技巧,由于此方法会造成无限的循环,因此必须加入 一个变量,判断该点是否遍历完毕。
下图找那个的列表是栈。
故深度优先遍历的顺序是:顶点1,顶点2,顶点3,顶点4,顶点5
class list_node:
def __init__(self):
self.val=0
self.next=None
head=[list_node()]*9 #声明一个节点类型的链表数组
run=[0]*9
def dfs(current): #深度优先函数
run[current]=1
print('[%d] ' %current, end='')
ptr=head[current].next
while ptr!=None:
if run[ptr.val]==0: #如果顶点尚未遍历,
dfs(ptr.val) #就进行dfs的递归调用
ptr=ptr.next
#声明图的边线数组
data=[[1,2],[2,1],[1,3],[3,1], \
[2,4],[4,2],[2,5],[5,2], \
[3,6],[6,3],[3,7],[7,3], \
[4,8],[8,4],[5,8],[8,5], \
[6,8],[8,6],[8,7],[7,8]]
for i in range(1,9): #共有八个顶点
run[i]=0 #把所有顶点设置成尚未遍历过
head[i]=list_node()
head[i].val=i #设置各个链表头的初值
head[i].next=None
ptr=head[i] #设置指针指向链表头
for j in range(20): #二十条边线
if data[j][0]==i: #如果起点和链表头相等,则把顶点加入链表
newnode=list_node()
newnode.val=data[j][1]
newnode.next=None
while True:
ptr.next=newnode #加入新节点
ptr=ptr.next
if ptr.next==None:
break
print('图的邻接表内容:') #打印图的邻接表内容
for i in range(1,9):
ptr=head[i]
print('顶点 %d=> ' %i,end='')
ptr =ptr.next
while ptr!=None:
print('[%d] ' %ptr.val,end='')
ptr=ptr.next
print()
print('深度优先遍历的顶点:') #打印深度优先遍历的顶点
dfs(1)
print()
图的邻接表内容:
顶点 1=> [2] [3]
顶点 2=> [1] [4] [5]
顶点 3=> [1] [6] [7]
顶点 4=> [2] [8]
顶点 5=> [2] [8]
顶点 6=> [3] [8]
顶点 7=> [3] [8]
顶点 8=> [4] [5] [6] [7]
深度优先遍历的顶点:
[1] [2] [4] [8] [5] [6] [3] [7]
总结:
可见,深度遍历和广度遍历的结果不是唯一的,只要满足相对应的条件即可。
下一篇: 数字字符串转int数组