[C++][数据结构][图][中][图的遍历][最小生成树]详细讲解

1.图的遍历

• 给定一个图g和其中任意一个顶点$v_0$，从$v_0$出发，沿着图中各边访问图中的所有顶点，且每个顶 点仅被遍历一次
  • “遍历”：对结点进行某种操作的意思

1.广度优先遍历

• **例如：**现在要找东西，假设有三个抽屉，东西在哪个抽屉不清楚，现在要将其找到，广度优先遍历的做法是：

  1. 先将三个抽屉打开，在最外层找一遍
  2. 将每个抽屉中红色的盒子打开，再找一遍
  3. 将红色盒子中绿色盒子打开，再找一遍
  4. 直到找完所有的盒子
     • 注意：每个盒子只能找一次，不能重复找
       

• 思考：如何防止节点被重复遍历？

  • 增加一个数组，用于标记是否入过队列，这样可以防止重复遍历

void bfs(const v& src)
{
	size_t srci = getvertexindex(src);

	queue<int> q;
	vector<bool> visited(_vertexs.size(), false); // 标记数组

	q.push(srci);
	visited[srci] = true;
	int levelsize = 1; // 控制每层出的数量

	while (!q.empty())
	{
		// 一层一层出
		for (size_t i = 0; i < levelsize; i++)
		{
			int front = q.front();
			q.pop();
			cout << front << ":" << _vertexs[front] << " ";

			// 把front的邻接顶点入队列
			for (size_t j = 0; j < _vertexs.size(); j++)
			{
				if (_matrix[front][j] != max_w && visited[j] == false)
				{
					q.push(j);
					visited[j] = true;
				}
			}
		}
		cout << endl;

		levelsize = q.size();
	}
}

2.深度优先遍历

• **例如：**现在要找东西，假设有三个抽屉，东西在哪个抽屉不清楚，现在要将其找到，深度优先遍历的做法是：
  1. 先将第一个抽屉打开，在最外层找一遍
  2. 将第一个抽屉中红盒子打开，在红盒子中找一遍
  3. 将红盒子中绿盒子打开，在绿盒子中找一遍
  4. 递归查找剩余的两个盒子
  • **深度优先遍历：**将一个抽屉一次性遍历完(包括该抽屉中包含的小盒子)，再去递归遍历其他盒子
• 如果给的图不是连通图，以某个顶点为起点没有遍历完成，怎么保证遍历完剩下的顶点？
  • 在visited数组中找没有遍历过的顶点，再次进行遍历

void _dfs(size_t srci, vector<bool>& visited)
{
	cout << srci << ":" << _vertexs[srci] << endl;
	visited[srci] = true;

	for (size_t i = 0; i < _vertexs.size(); i++)
	{
		if (_matrix[i] != max_w && visited[i] == false)
		{
			_dfs(i, visited);
		}
	}
}

void dfs(const v& src)
{
	size_t srci = getvertexindex(src);
	vector<bool> visited(_vertexs.size(), false);
	_dfs(srci, visited);

	// 处理存在不连通的情况
	for (size_t i = 0; i < _vertexs.size(); i++)
	{
		if (!visited[i])
		{
			_dfs(i, visited);
		}
	}
}

2.最小生成树

• 连通图中的每一棵生成树，都是原图的一个极大无环子图，即：
  • 从其中删去任何一条边，生成树就不在连通
  • 反之，在其中引入任何一条新边，都会形成一条回路
• 若连通图由n个顶点组成，则其生成树必含n个顶点和n-1条边，因此构造最小生成树的准则有三条：
  • 只能使用图中权值最小的边来构造最小生成树
    • 最小的成本让着n个顶点连通
  • 只能使用恰好n-1条边来连接图中的n个顶点
  • 选用的n-1条边不能构成回路
• 构造最小生成树的方法：kruskal算法和prim算法，这两个算法都采用了逐步求解的贪心策略
• 贪心算法：
  • 指在问题求解时，总是做出当前看起来最好的选择
    • 即：贪心算法做出的不是整体最优的的选择，而是某种意义上的局部最优解
  • 贪心算法不是对所有的问题都能得到整体最优解

1.kruskal算法

• 任给一个有n个顶点的连通网络 n = { v , e } n=\{v,e\} n={v,e}
  • 首先构造一个由这n个顶点组成、不含任何边的图 g = { v , n u l l } g=\{v,null\} g={v,null}，其中每个顶点自成一个连通分量
  • 其次不断从e中取出权值最小的一条边(若有多条任取其一)，若该边的两个顶点来自不同的连通分量，则将此边加入到g中
    • 如此重复，直到所有顶点在同一个连通分量上为止
  • 核心：每次迭代时，选出一条具有最小权值，且两端点不在同一连通分量上的边，加入生成树
    • kruskal算法是一种全局贪心的算法
• 如何判断是否形成环？
  • 并查集
• 在下图执行kruskal算法的过程
  • 加了阴影的边属于不断增长的森林a
  • 该算法按照边的权重大小依次进行考虑，箭头指向的边是算法每一步考察的边
    • 如果该条边将两颗不同的树连接起来，它就被加入到森林里，从而完成对两棵树的合并
      

w kruskal(self& mintree)
{
	size_t n = _vertexs.size();

	// 初始化mintree
	mintree._vertexs = _vertexs;
	mintree._indexmap = _indexmap;
	mintree._matrix.resize(n);
	for (size_t i = 0; i < n; i++)
	{
		mintree._matrix[i].resize(n, max_w);
	}

	priority_queue<edge, vector<edge>, greater<edge>> minqueue;

	// 建堆排序
	for (size_t i = 0; i < n; i++)
	{
		for (size_t j = 0; j < n; j++)
		{
			if (i < j && _matrix[i][j] != max_w)
			{
				minqueue.push(edge(i, j, _matrix[i][j]));
			}
		}
	}

	// 选出n-1条边
	size_t size = 0;
	w totalw = w();
	unionfindset ufs(n);
	while (!minqueue.empty())
	{
		edge min = minqueue.top();
		minqueue.pop();

		// 判环 -> 并查集
		if (!ufs.insameset(min._srci, min._dsti))
		{
			cout << _vertexs[min._srci] << "->" \
				<< _vertexs[min._dsti] << ":" << min._w << endl;
			
			mintree._addedge(min._srci, min._dsti, min._w);
			ufs.union(min._srci, min._dsti); // 入集
			
			size++;
			totalw += min._w;
		}
		else
		{
			cout << "forming ring: ";
			cout << _vertexs[min._srci] << "->" \
				<< _vertexs[min._dsti] << ":" << min._w << endl;
		}
	}

	if (size == n - 1)
	{
		return totalw;
	}
	else
	{
		return w();
	}
}

2.prim算法

• prim算法的一个性质是集合a中的边总是构成一棵树，这棵树从一个任意的根节点r开始，一直长大到覆盖v中的所有结点时为止
  • prim算法思路天然避环
  • 算法每一步在连续集合a和a之外的结点的所有边中，选择一条轻量级边加入到a中
  • 本策略也属于贪心策略，因为每一步所加入的边都必须是使树的总权重增加量最小的边
    • prim算法是一种局部贪心算法
• 在下图执行prim算法的过程
  • 初始的根节点为a，加阴影的边和黑色的结点都属于树a
  • 在算法的每一步，树中的结点就决定了图的一个切割，横跨该切割的一条轻量级边被加入到树中
  • **例如：**在途中第二步，该算法可以选择将边$(b,c)$加入到树中，也可以将边$(a,h)$加入到树中，因为这两条边都是横跨该切割的轻量级边
    

w prim(self& mintree, const w& src)
{
    size_t srci = getvertexindex(src);
    size_t n = _vertexs.size();

    // 初始化mintree
    mintree._vertexs = _vertexs;
    mintree._indexmap = _indexmap;
    mintree._matrix.resize(n);
    for (size_t i = 0; i < n; i++)
    {
        mintree._matrix[i].resize(n, max_w);
    }

    // true & false表示该元素是否在该集合内
    vector<bool> x(n, false);
    vector<bool> y(n, true);
    x[srci] = true;
    y[srci] = false;

    // 从x->y集合中连接的边里面选出最小的边
    priority_queue<edge, vector<edge>, greater<edge>> minqueue;

    // 先把srci连接的边添加到队列中
    for (size_t i = 0; i < n; i++)
    {
        if (_matrix[srci][i] != max_w)
        {
            minqueue.push(edge(srci, i, _matrix[srci][i]));
        }
    }

    size_t size = 0;
    w totalw = w();
    while (!minqueue.empty())
    {
        edge min = minqueue.top();
        minqueue.pop();

        // 最小边的目标也在x集合，则构成环
        if (x[min._dsti])
        {
            cout << "forming ring:";
            cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
        }
        else
        {
            cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;

            mintree._addedge(min._srci, min._dsti, min._w);
            x[min._dsti] = true;
            y[min._dsti] = false;

            size++;
            totalw += min._w;

            // 可能最小生成树已经生成，但是多了很多成环边，无须继续遍历
            if (size == n - 1)
            {
                break;
            }

            // 将目标顶点连接的边加入到队列中
            for (size_t i = 0; i < n; i++)
            {
                if (_matrix[min._dsti][i] != max_w && y[i])
                {
                    minqueue.push(edge(min._dsti, i, _matrix[min._dsti][i]));
                }
            }
        }
    }

    // 实际不一定存在最小生成树
    if (size == n - 1)
    {
        return totalw;
    }
    else
    {
        return w();
    }
}