基本图的算法

基本图的算法
G=(V,E)
表示法,邻接矩阵,邻接链表(稀松图)
邻接链表表示一个包含|V|条链表的数组Adj所构成,每个节点有一条链表。对于每个节点u 属于V,邻接链表Adj[u]包含所有与
结点u之间有边相连的结点v。
权重图,图中每条边带一个相关的权重。
权重函数w:E->R。
邻接链表缺陷是无法快速判断一条边(u,v)是否是图中的一条边。

 广度优先所搜
BFS(G,s)
    for(each vertex u ∈ G.V -{s})
        u.color = WHITE
        u.d = oo
        u.pi = nil
    s.coloar = GRAY
    s.d = 0
    s.pi = NIL
    Q= 0
    ENQUEUE(Q,s)
    while(Q != 0)
        u = DEQUEUE(Q)
        for each v ∈ G.Adj[u]
            if v.color == WHITE
                v.coloar = GRAY
                v.d = u.d + 1
                v.pi = u
                ENQUEUE(Q,v)
        u.color = BLACK

属性说明,

PI 是父节点parent

d是distance

原文地址:https://www.cnblogs.com/zhoug2020/p/6261648.html