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

参考回答：

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.arc[v][i] == 0 || g.arc[v][i] == 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;
}
}
}
}
}