【数据结构】图的遍历及最小生成树
上一篇博客中讲了图的基本概念及如何存储,下面学习图的遍历及最小生成树的问题。 图的遍历广度优先搜索(Breadth First Search,BFS)举一个例子: //我们使用一个数组来区别一个顶点是否已经遍历过,遍历过的设置为true。
void BFS(const V& v)
{
queue<int> q;
vector<bool> visited(_v.size(),false);//遍历过的置为true,默认为false
size_t index = GetIndex(v);
q.push(index);
_BFS(q,visited);
for (size_t i = 0; i < _v.size(); i++)//为什么要这么写?
//假如我们的图中的一个顶点与其他的顶点没有关系,即两个顶点之间没有边,
//那么如果我们不这么写,就会漏掉这个顶点。
//因此,我们的处理方法是 先遍历一次,然后在看哪个点没有遍历,
//如果有点没遍历,那么将该点push到队列中遍历。
{
if (visited[i] == false)
{
q.push(i);
_BFS(q,visited);
}
}
cout << endl;
}
void _BFS(queue<int>& q,vector<bool>& visited)
{
while (!q.empty())
{
size_t index = q.front();
q.pop();
if (visited[index] == true)
continue;
cout << _v[index] << " ";
visited[index] = true;
pNode pCur = _linkEdges[index];
while (pCur)
{
if (visited[pCur->_dst] == false)
q.push(pCur->_dst);
pCur = pCur->_pNext;
}
}
}
深度优先搜索(Depth First Search)还是上面图中的两个图为例: void DFS(const V& v)
{
size_t index = GetIndex(v);
vector<bool> visited(_v.size(),false);
_DFS(index,visited);
for (size_t i = 0; i < _v.size(); i++)
{
if (visited[i] == false)
_DFS(i,visited);
}
cout << endl;
}
void _DFS(int index,vector<bool>& visited)
{
cout << _v[index] << " ";
visited[index] = true;
pNode pCur = _linkEdges[index];
while (pCur)
{
if (visited[pCur->_dst] == false)
_DFS(pCur->_dst,visited);
pCur = pCur->_pNext;
}
}
最小生成树连通图中的每一颗生成树,都是原图的一个极大无环子图,即:从其中删去任何一条边,生成树就不必再连通;反之,在其中假如一条边,就会形成回路。
构成最小生成树有两种算法:Kruskal算法和Prim算法。 Kruskal算法任给一个有n个顶点的连通网络N,首先构造一个有n个顶点组成,不含任何边的图G,其中,每个顶点自成一个连通分量,不断从N的边中找最小的一条,若该边的两个顶点来自不同的连通分量,则将此边假如到G中。如此重复,直至所有顶点在同一个连通分量上为止。
typedef Graph<V,W,IsDirect> Self;
typedef Node LinkEdge;
Self Kruskal()
{
Self g;
g._v = _v;//新建一个图
g._linkEdges.resize(_v.size());
vector<LinkEdge*> edges;
for (size_t i = 0; i < _v.size(); i++)
{
LinkEdge* pCur = _linkEdges[i];
while (pCur)
{
if (IsDirect || (!IsDirect && pCur->_src < pCur->_dst))//保存边的权值。
//无向图只需要保存一次,保存src<dst
edges.push_back(pCur);
pCur = pCur->_pNext;
}
}
class Compare
{
public:
bool operator()(const LinkEdge* left,const LinkEdge* right)
{
return left->_weight < right->_weight;
}
};
sort(edges.begin(),edges.end(),Compare());//将保存的边的权值,从小到大排序
size_t count = _v.size() - 1;//从前往后取n-1条边
UnionFind u(_v.size());
for (size_t i = 0; i < edges.size(); i++)
{
LinkEdge* pCur = edges[i];
size_t srcRoot = u.FindRoot(pCur->_src);
size_t dstRoot = u.FindRoot(pCur->_dst);
if (srcRoot != dstRoot)//若两个顶点不在同一个集合,才将边加上
{
g._Add(pCur->_src,pCur->_dst,pCur->_weight);
if (!IsDirect)//false为无向图
g._Add(pCur->_dst,pCur->_src,pCur->_weight);
u.Union(pCur->_src,pCur->_dst);//合并
count--;
if (count == 0)
break;
}
}
if (count > 0)
cout << "最小生成树非法" << endl;
return g;
}
Prime算法1. 给出一个只有顶点的空图; 2. 权值最小的10,将10加入到生成树中; 3. 原图中A,B相关联的边权值最小的是30,将30加入到生成树中; 4. 原图中A,B,E有关的边,权值最小的是30,将30加入到生成树中; 5. 以此类推,直至所有顶点连通。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |