无向图的基本路径与简单路径径 1）求出无向图中从起点到终点的所有基本路径与简单路径径。其中起点和终点可以由用户自行设定。

点击联系发帖人 时间：2019-05-24 12:07

简单路径

//打印从i到j的所有回路 //因为图是按照序号的从小到大访问所以一旦有pop_node,必须从pop_node+1开始访问 //如果当前节点是j节点，则打印栈中的所有元素 //如果所有邻接的节点都被访问了 //将之前嘚所有邻接节点置为未访问 //注意避免出现访问环需要判断邻接点是否包含起始节点

}

求（有向）图中任意两点间所有蕗径

节点类中包括如下信息：是否被访问过节点的名称，从这个节点访问到下一个节点的集合

A 将始点设置为已访问将其入栈

B 查看栈顶節点V在图中，有没有可以到达、且没有入栈、且没有从这个节点V出发访问过的节点

C 如果有则将找到的这个节点入栈

D 如果没有，则将节点V訪问到下一个节点的集合中每个元素赋值为零V出栈

E 当栈顶元素为终点时，设置终点没有被访问过打印栈中元素，弹出栈顶节点

// 判断连個节点是否能连通 // 与节点v相邻并且这个节点没有被访问到，并且这个节点不在栈中 //第几张图有两张(0,1)，起点序号(0-6)终点序号(0-6)

}

给出一个无向图指定无向图中某个顶点作为源点。求出图中所有顶点到源点的最短路径

无向图的最短路径其实是源点到该顶点的最少边的数目。

本文假设图的信息保存在文件中通过读取文件来构造图。文件内容的格式参考

无向图的最短路径实现相对于带权的有向图最短路径实现要简单得多。

源点嘚最短路径距离为0从源点开始，采用广度优先的顺序首先将与源点邻接的顶点的路径求出，然后再依次求解图中其他顶点的最短路径

由于顶点的最短路径的求解顺序是一个广度优先的顺序，因此需要一个辅助队列初始时，将源点的最短路径距离设置为0将源点入队列。

然后在一个while循环中，从队列中弹出顶点遍历该顶点的邻接点，若该邻接点的距离未被更新过（表示该邻接点未被访问过）更新鄰接点的最短路径距离为该顶点的距离加上1，并将所有的邻接点入队列

三，最短路径算法的实现

感觉该算法的实现与有向图的都非常嘚相似。他们都采用了广度的思想在里面

广度优先的思想就是：处理完某个顶点后，去处理该顶点的所有邻接点处理完它的邻接点后，再去处理更远（更外层）的顶点

第11行while循环，每个顶点出队列一次第13行for循环，表示每条边被处理一次故算法的时间复杂度为O（V+E）

}