第5章 第13节 图

推荐给朋友

● 请问你对图论算法了解多少?(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;
}
}
}
}
}