哈夫曼编码树,最小生成树(Kruskal,Prim),图的遍历(BFS,DFS),图的拓扑排序

xiaoxiao2021-02-28  5

Huffman codes(优化编码树):

     问题描述:将具有不同出现频率的结点生成二叉树,使得总的查找次数最小

     算法描述:先从所有结点中选择频数最小的作为左节点,并将此结点移出,再选择最小的节点作为右结点并移出,生成一个新结点并加入结点集中,循环此操作,直至结点集中没有结点为止。

       伪代码:

            Huffman(C,Q)=            

               n=|C|//节点的个数

              For(i=1:n-1)

                  z=Allocate-Node();

                  x=left(z)=extract-min(Q);//选择频数最小的节点加入其中,并移出

                  y=right(z)=extract-min(Q);// 选择频数最小的节点加入其中,并移出

                   z.left()=x;z.right()=y;//x,y分别接入z的左右结点

                  insert(Q,z)//将生成的z结点加入Q中     

五.最小生成树问题:

      描述:输入无向连通图G=(V,E),权函数W,求最小的生成树

Kruskal算法:

思想描述:

      While(选择图中权值最小的边)

             If(

Prim算法:

    确定一个根节点加入已访问的集合A中,选择与集合A相连的边中权值最小并且另一端的节点不在集合A中的节点v加入集合中,如果更新Pai[v]为与v相连的A中节点,更新key[v]为当前的权值,重复此操作直至将所有结点都加入A中

     伪代码:

    Pai[v]存储节点v的父结点,key[]存储该结点与父节点的距离

        Prim();

         For(v在 V[G]中)

              Key[v]=max//初始化为无穷大

              Pai[v]=null;

      Key[r]=0;//选中根结点

        While()

             u=min(Q)//选择与当前A相连权值最小且另一端节点不在A中的边

             for(v在u结点的相连结点中)

                  if(v不在加入的集合A中,且w(u,v)<key[v])

                        Pai[v]=u;//更新父结点

                        Key[v]=w(u,v)//更新与父结点的距离

图论算法:

1.     广度优先搜索(BFS)

      自然语言描述:    先根结点开始,再一次访问其子结点,再依次选择子节点并进行上面的操作。

如上图:A先进入队列,再依次让A的邻节点进入队列即BCD,再从B开始依次让其没有访问到的邻结点加入队列…,不断的标记已经访问的结点,直至所有节点都访问过

 BFS(G,s)

       L0=空队列:

       将s插入队列中

       将S标记为visted

       i=0;

while(L[i]不为空)

      L[i+1]=空队列

      Foreach v属于 L[i]

          For each (v,u)在图中

              If(v,u).tag==unexplore

                   If(u.tag==unvisited)

                      (v,u).tag=explore

                        u.tag=visited

                        u插入L[i+1]

                    else

                        (v,u).tag=cross

        i++;

下图为队列L的变化,箭头表示i的位置

2.     深度优先遍历:

描述:选中出发顶点S并访问,选中S的第一个邻节点并访问,重复此操作直至前节点没有未被访问的邻节点,然后依次返回,选择该结点未被访问过的邻节点直至末尾,直到回到出发顶点则深度遍历结束----回溯法

如此图:A->B->C->D  此时D没有找到未被访问的邻节点则返回C,继续

              ->E    此时E也没有,依次返回E->C->B->A结束

伪代码:

     DFS(G,s)

        s.tag=visited;

        for( each (s,u)∈E(G)

         if(   (s,u).tag==unexplore)

            if( u.tag==unvisited)

               (s,u).tag=explore;

               u,tag=visited;

               DFS(G,u);

            Else

               (s,u)..tag=back

3.拓扑排序:

      1.在有向图中选择一个没有前驱的顶点并输出

      2.在图中删除该顶点和所有以它为尾的弧(删除所有和它有关的边)

      3.重复上述两步,直至所有的顶点输出,或者当前图中不存在无前驱的顶点为止,如果不存在无前驱的顶点则说明该图是有环的,因此,也可以通过拓扑排序来判断一个图是否有环。

如上图:先去掉无前驱的1,再是6,4,3,2,5,即是拓扑排序

转载请注明原文地址: https://www.6miu.com/read-1950196.html

最新回复(0)