74_图的遍历（BFS）

关键词：MatrixGraph和ListGraph的选择方式、图的遍历概念、广度优先（BFS）、深度优先（DFS）

0. MatrixGraph和ListGraph如何选择？

时间复杂度的对比分析

• MatrixGraph适用于内存资源富足的场合（性能较好）
• ListGraph适用于内存资源受限的场合（节省空间）

1. 图的遍历

从图中的某一顶点出发，沿着一些边访问图中的其他顶点，使得每个顶点最多被访问一次。

注意：从某个顶点出发进行遍历，不一定能够访问到图中的所有顶点。

2. 图的遍历方式

• 广度优先（Breath First Search）：以二叉树层次遍历的思想对图进行遍历
• 深度优先（Depth First Search）：以二叉树先序遍历的思想对图进行遍历

3. 广度优先（BFS）

广度优先遍历示意图

• 原料：class LinkQueue<T>
• 步骤：
  1. 将起始顶点压入队列中
  2. 队头顶点v弹出，判断是否已经标记（标记：转2，未标记：转3）
  3. 标记顶点v，并将顶点v的邻接顶点压入队列中

  4. 判断队列是否为空（非空：转2，空：结束）

     
     

BFS算法示例 BFS算法流程图

    template < typename T >
    DynamicArray<T>* toArray(LinkQueue<T>& queue)
    {
        DynamicArray<T>* ret = new DynamicArray<T>(queue.length());

        if( ret != NULL )
        {
            for(int i=0; i<ret->length(); ++i, queue.remove())
            {
                ret->set(i, queue.front());
            }
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to create a ret object ... ");
        }

        return ret;
    }

    SharedPointer< Array<int> > BFS(int i)
    {
        DynamicArray<int>* ret = NULL;

        if( (i <= 0) && (i < vCount()) )
        {
            LinkQueue<int> q;
            LinkQueue<int> r;
            DynamicArray<bool> visted(vCount());

            // 初始化设置，标记数组中的每一个都没有被访问
            for(int j=0; j<visted.length(); ++j)
            {
                visted[j] = false;
            }

            q.add(i);

            while( q.length() > 0 )
            {
                int v = q.front();      // 拿出队列头部的顶点

                q.remove();

                if( !visted[v] )        // 判断是否被访问
                {
                    SharedPointer< Array<int> > aj = getAdjacent(v);

                    for(int j=0; j<aj->length(); ++j)
                    {
                        q.add((*aj)[j]);
                    }

                    r.add(v);
                    visted[v] = true;
                }
            }

            ret = toArray(r);
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterExcetion, "Index i is invalid ... ");
        }

        return ret;
    }

4. 小结

• MatrixGraph适用于资源富足的场合
• ListGraph适用于资源受限的场合
• 广度优先按照层次的方式对顶点进行访问
• 广度优先算法的核心是队列的使用

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4