图的几种常健算法的伪代码

几种常健算法的伪代码"/>

图的几种常健算法的伪代码

复习记忆

//无权图的单源最短路径算法
// T = O( |V| + |E| )
// BFS
void unWeighted(Vertex S)
{
    queue<int> q.push(S);
    while(!q.empty()){
        v=q.pop();
        for( V 的每个邻接点 W )
            if( dist[W]==-1 ){
                dist[W]=dist[V]+1;
                path[W]=V;//栈输出
                q.push(W);
            }
    }
}//有权图的单源最短路算法
dist[]=INFINITE;
path[]=-1
void Dijkstra(Vertex S)
{
    while(1){
        V=未收录顶点中disk最小者;
        if( 这样的 V 不存在 )
            break;
        collected[V]=true;
        for( V 的每个邻接点 W )
            if( collected[W]==false )
                if( dist[V] + E<V,W>  < dist[W] ){
                    dist[W] = dist[V] + E<V,W>;
                    path[W] = V;
                }
    }
}//Prim算法  稠密图划算
//让一棵小树长大
//T = O ( |V|² )
//城市铺电缆问题
void Prim()
{
    MST={s};
    while(1){
        V=未收录顶点中dist