请问你对图论算法了解多少？（BFS,DFS,最短路径，最小生成树，最小割最大流...）平常有用过吗？

Answer 1

参考回答：

DFS：深度优先搜索算法思路：

从顶点V开始，访问这个顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径的相通的顶点都被访问了，如果此时还有顶点未被访问，则选择图中未被访问的那个顶点作为起点，重复上述动作。

void DFS_store_array(Graph_array g,int v,bool * & visit) {
	cout << g.infromation[v] << " ";
	visit[v] = true;
    for (int i = 0; i < g.vexnum; i++) {//找出下一个位被访问的顶点
        if (g.arcv == 0 || g.arcv == INT_MAX) { //如果两个顶点不存在边
            continue;
        }
        else if (!visit[i]) {//如果没有被访问，访问该结点
            DFS_store_array(g, i, visit);
        }
    }
}

 

BFS广度优先搜索思路就是：假设从图中的顶点V出，在访问了v之后，依次访问v的各个未被访问的邻接点，然后，分别从这些邻接点出发，依次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的邻接点”先被访问，直至图中所有的顶点都被访问到为止，防止出现非连通图的情况，我们需要最后遍历一遍，看是否所有的点都被访问了，如果有未被访问的点，那么就把该点作为一个新的起点。

void BFS_list(Graph_List g, int begin) {
	int i;
	bool * visit = new bool[g.vexnum];
    for (i = 0; i < g.vexnum; i++) {
   		 visit[i] = false;
    }
		cout << "图的BFS遍历结果：" << endl;
		queue<int>  q;
        for (int v = 0; v < g.vexnum; v++) {
            if (!visit[(begin - 1 + v) % g.vexnum])//注意起点不一定是v1
            {
                cout << g.node[(begin - 1 + v) % g.vexnum].data << " ";
                visit[(begin - 1 + v) % g.vexnum] = true;
                q.push((begin - 1 + v) % g.vexnum);//初始化我们的队列
                while (!q.empty())
                {
                    int u = q.front();
                    q.pop();
                    ArcNode * next;
                    next = g.node[u].firstarc;//获得依附在该顶点的第一条边的信息
                    while (next) {//遍历该链表上的所有的点
                        if (!visit[next->adfvex]) {
                        cout << g.node[next->adfvex].data << " ";
                        visit[next->adfvex] = true;
                        q.push(next->adfvex);
                    }
                    next = next->next;
                }
            }
        }
	}
}