基本图的算法

基本图的算法

基本图的算法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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。