图的广度优先搜索
程序员文章站
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();
}
遍历结果: