void unweighted(Vertex s){
    Queue<Vertex> q = new Queue<Vertex>();
    //把每個頂點的距離設為無窮大
    for each Vertex v
        v.dist = INFINITY
    //將起點的距離設為0
    s.dist = 0;
    //起點入隊，作為算法的開始
    q.enqueue(s);
    //只要隊列不為空，便繼續(xù)循環(huán)
    while( !q.isEmpty() ){
        //獲得出隊頂點
        Vertex v = q.dequeue();
        //對與v鄰接的每個頂點進行處理
        for each Vertex w adjacent to v
            if(w.dist == INFINITY){
                w.dist = v.dist + 1;
                w.path = v;//代表w的上一個經過的頂點為v
                //完成操作后，便入隊，以用來接著分析與w鄰接的頂點們
                q.enqueue( w );
            }
    }
}

from queue import Queue
class Vertex:
    #頂點類
    def __init__(self,vid,outList):
        self.vid = vid#出邊
        self.outList = outList#出邊指向的頂點id的列表，也可以理解為鄰接表
        self.know = False#默認為假
        self.dist = float('inf')#s到該點的距離,默認為無窮大
        self.prev = 0#上一個頂點的id，默認為0

#創(chuàng)建頂點對象
v1=Vertex(1,[2,4])
v2=Vertex(2,[4,5])
v3=Vertex(3,[1,6])
v4=Vertex(4,[3,5,6,7])
v5=Vertex(5,[7])
v6=Vertex(6,[])
v7=Vertex(7,[6])
#創(chuàng)建一個長度為8的數組，來存儲頂點，0索引元素不存
vlist = [False,v1,v2,v3,v4,v5,v6,v7]
def unweighted():
    #起點為v3
    vlist[3].dist = 0
    q = Queue()
    q.put(vlist[3])
    while(not q.empty()):
        v = q.get()#返回并刪除隊列頭部元素
        for w in v.outList:
            if(vlist[w].dist == float('inf')):
                vlist[w].dist = v.dist + 1
                vlist[w].prev = v.vid
                q.put(vlist[w])

unweighted()
print('v1.prev:',v1.prev,'v1.dist',v1.dist)
print('v2.prev:',v2.prev,'v2.dist',v2.dist)
print('v3.prev:',v3.prev,'v3.dist',v3.dist)
print('v4.prev:',v4.prev,'v4.dist',v4.dist)
print('v5.prev:',v5.prev,'v5.dist',v5.dist)
print('v6.prev:',v6.prev,'v6.dist',v6.dist)
print('v7.prev:',v7.prev,'v7.dist',v7.dist)

traj_list = [3]#v3是起點直接加上

def print_traj(dist):
    last = traj_list[-1]
    print(traj_list,'該路徑的長度為：',vlist[last].dist)
    temp_list = []#存儲下一步的選項
    for i in range(1,len(vlist)):
        v = vlist[i]
        if((v.dist==dist) and (v.prev==last)):
            temp_list.append(i)
    if(len(temp_list)==0):
        return#終點
    #遞歸每個選項
    for i in temp_list:#i為頂點的索引
        traj_list.append(i)
        print_traj(dist+1)
        traj_list.pop()


print_traj(1)