欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的广度优先搜索

程序员文章站 2022-06-12 19:19:55
...

图的搜索方法有广度优先与深度优先搜索方法。这里给出广度优先搜索。
广度优先搜索即先遍历完同一层次的元素,然后再遍历下一层次的元素。用邻接表存储的图的广度优先遍历时间复杂度为O(e),使用邻接矩阵存储的图的广度优先方法时间复杂度为O(n^2)。
给出广度优先搜索代码:

void BFS()
    {
        size_t size = _v.size();
        if(size < 1)
            return;
        vector<bool> flags;
        flags.resize(size, false);
        queue<PNode> quep;
        for(size_t i = 0; i < size; i++)
            if(false == flags[i])
            {
                quep.push(&_map[i]);
                _BFS(quep, flags);
            }
        cout << endl;
    }
    void _BFS(queue<PNode>& quep, vector<bool>& flags)
    {
        while(!quep.empty())
        {
            PNode pCur = quep.front(); 
            if(false == flags[pCur->_value])
            {
                cout << _v[pCur->_value] << " ";
                flags[pCur->_value] = true;
            }
            quep.pop();
            while(pCur->_Next)
            {
                if(false == flags[pCur->_Next->_value])
                    quep.push(pCur->_Next);
                pCur = pCur->_Next;
            }
        }
    }

建立一个邻接表存储的图,并使用广度优先搜索遍历:

void test()
{
    Map<char, false> m("ABCDEFG");
    m.InsertEdge('A', 'B', 3);
    m.InsertEdge('A', 'D', 5);
    m.InsertEdge('C', 'B', 3);
    m.InsertEdge('C', 'G', 4);
    m.InsertEdge('D', 'F', 1);
    m.InsertEdge('G', 'E', 6);
    m.InsertEdge('F', 'C', 7);
    m.PrintMap();
    m.BFS();
}

遍历结果:
图的广度优先搜索

上一篇: 调虎离山

下一篇: 肋骨断了