● 请问你对图论算法了解多少?(BFS,DFS,最短路径,最小生成树,最小割最大流...)平常有用过吗?
参考回答:
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.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; } } } } }