欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图python(数据结果与算法)---遍历

程序员文章站 2022-07-15 08:58:19
...

图遍历是指:

从任意一个顶点出发对图中每个顶点访问且仅访问一次的过程。

因为图中可能存在回路,为了避免对一个顶点的重复访问可以增设一个辅助的数组visited[],全部初始化为0,一旦访问过,置位visited[i] = 1,:

图的遍历比较复杂,需要考虑:

  • 指定遍历的第一个顶点
  • 由于一个顶点和多个顶点的相邻,需要在多个邻接顶点间确定访问次序
  • 由于图中存在回路,必须对访问过的顶点做标记,防止出现重复访问同一顶点的情况。

图的遍历可分为:

  • 深度优先遍历
  • 广度优先遍历

1图的广度优先搜索算法(BFS,Breadth-First-Search)

遍历法则是利用队列和递归技巧来遍历的,也是从图的某一顶点开始遍历,被访问的顶点就做上已被访问过的记号。

bfs总是先访问完同一层的结点,然后才继续访问下一层结点,

下图来自:https://blog.csdn.net/qq_35733751/article/details/81095725?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522159127130019195265926756%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=159127130019195265926756&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-81095725.nonecase&utm_term=%E5%9B%BE%E7%9A%84%E9%81%8D%E5%8E%86

图python(数据结果与算法)---遍历

图python(数据结果与算法)---遍历

步骤

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出发继续进行类似的访问,直到所有的邻接节点都被访问,然后退到前一个被访问的顶点,看是否有其他未被访问的顶点,若有再进行类似的访问。若无继续回退,直到图中的所有顶点都被访问为止。

图python(数据结果与算法)---遍历

这种遍历的方法结合了递归和堆栈两种数据结构的技巧,由于此方法会造成无限的循环,因此必须加入 一个变量,判断该点是否遍历完毕。

下图找那个的列表是栈。

图python(数据结果与算法)---遍历

故深度优先遍历的顺序是:顶点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] 

总结:

可见,深度遍历和广度遍历的结果不是唯一的,只要满足相对应的条件即可。