求(有向)图中任意两点间所有路径
1建图:
图类中包括如下信息:顶点集合,邻接矩阵。
节点类中包括如下信息:是否被访问过,节点的名称,从这个节点访问到下一个节点的集合
<!--[endif]-->
图1
<!--[endif]-->
图2
2 算法思路
A 将始点设置为已访问,将其入栈
B 查看栈顶节点V在图中,有没有可以到达、且没有入栈、且没有从这个节点V出发访问过的节点
C 如果有,则将找到的这个节点入栈
D 如果没有,则将节点V访问到下一个节点的集合中每个元素赋值为零,V出栈
E 当栈顶元素为终点时,设置终点没有被访问过,打印栈中元素,弹出栈顶节点
F 重复执行B – E,直到栈中元素为空
package util;
public class Graph {
private Vertex vertexList[]; // list of vertices
private int adjMat[][]; // adjacency matrix
private int nVerts;
private static int MAX_VERTS = 7; // n个点
int i = 0;
int j = 0;
public Vertex[] getVertexList() {
return vertexList;
}
public int[][] getAdjMat() {
return adjMat;
}
public int getN() {
return MAX_VERTS;
}
public Graph(int index) {
adjMat = new int[MAX_VERTS][MAX_VERTS]; // 邻接矩阵
vertexList = new Vertex[MAX_VERTS]; // 顶点数组
nVerts = 0;
for (i = 0; i < MAX_VERTS; i++) {
for (j = 0; j < MAX_VERTS; j++) {
adjMat[i][j] = 0;
}
}
addVertex('A');
addVertex('B');
addVertex('C');
addVertex('D');
addVertex('E');
addVertex('F');
addVertex('G');
addEdge(0, 1);
addEdge(0, 2);
addEdge(1, 4);
addEdge(2, 0);
addEdge(2, 5);
addEdge(3, 0);
addEdge(3, 2);
addEdge(3, 3);
addEdge(4, 1);
addEdge(4, 2);
addEdge(5, 6);
addEdge(6, 3);
switch (index) {
case 0:
break;
case 1:
delEdge(4, 2);
break;
default:
break;
}
}
private void delEdge(int start, int end) {
adjMat[start][end] = 0;
}
private void addEdge(int start, int end) {// 有向图,添加边
adjMat[start][end] = 1;
// adjMat[end][start] = 1;
}
public void addVertex(char lab) {
vertexList[nVerts++] = new Vertex(lab);// 添加点
}
public char displayVertex(int i) {
return vertexList[i].getLabel();
}
public boolean displayVertexVisited(int i) {
return vertexList[i].WasVisited();
}
public void printGraph() {
for (i = 0; i < MAX_VERTS; i++) {
System.out.print("第" + displayVertex(i) + "个节点:" + " ");
for (j = 0; j < MAX_VERTS; j++) {
System.out.print(displayVertex(i) + "-" + displayVertex(j)
+ ":" + adjMat[i][j] + " ");
}
System.out.println();
}
}
}
package util;
import java.util.ArrayList;
public class Vertex {
boolean wasVisited; // 是否遍历过
public char label; // 节点名称
ArrayList<Integer> allVisitedList;// 节点已访问过的顶点
public void setAllVisitedList(ArrayList<Integer> allVisitedList) {
this.allVisitedList = allVisitedList;
}
public ArrayList<Integer> getAllVisitedList() {
return allVisitedList;
}
public boolean WasVisited() {
return wasVisited;
}
public void setWasVisited(boolean wasVisited) {
this.wasVisited = wasVisited;
}
public char getLabel() {
return label;
}
public void setLabel(char label) {
this.label = label;
}
public Vertex(char lab) // constructor
{
label = lab;
wasVisited = false;
}
public void setVisited(int j) {
allVisitedList.set(j, 1);
}
}
package util;
import java.util.ArrayList;
import java.util.Stack;
public class AF {
boolean isAF = true;
Graph graph;
int n;
int start, end;
Stack<Integer> theStack;
private ArrayList<Integer> tempList;
private String counterexample;
public AF(Graph graph, int start, int end) {
this.graph = graph;
this.start = start;
this.end = end;
}
public boolean getResult() {
graph.printGraph();
n = graph.getN();
theStack = new Stack<Integer>();
if (!isConnectable(start, end)) {
isAF = false;
counterexample = "节点之间没有通路";
} else {
for (int j = 0; j < n; j++) {
tempList = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
tempList.add(0);
}
graph.getVertexList()[j].setAllVisitedList(tempList);
}
isAF = af(start, end);
}
return isAF;
}
private boolean af(int start, int end) {
graph.getVertexList()[start].setWasVisited(true); // mark it
theStack.push(start); // push it
while (!theStack.isEmpty()) {
int v = getAdjUnvisitedVertex(theStack.peek());
if (v == -1) // if no such vertex,
{
tempList = new ArrayList<Integer>();
for (int j = 0; j < n; j++) {
tempList.add(0);
}
graph.getVertexList()[theStack.peek()]
.setAllVisitedList(tempList);// 把栈顶节点访问过的节点链表清空
theStack.pop();
} else // if it exists,
{
theStack.push(v); // push it
}
if (!theStack.isEmpty() && end == theStack.peek()) {
graph.getVertexList()[end].setWasVisited(false); // mark it
printTheStack(theStack);
System.out.println();
theStack.pop();
}
}
return isAF;
}
// 判断连个节点是否能连通
private boolean isConnectable(int start, int end) {
ArrayList<Integer> queue = new ArrayList<Integer>();
ArrayList<Integer> visited = new ArrayList<Integer>();
queue.add(start);
while (!queue.isEmpty()) {
for (int j = 0; j < n; j++) {
if (graph.getAdjMat()[start][j] == 1 && !visited.contains(j)) {
queue.add(j);
}
}
if (queue.contains(end)) {
return true;
} else {
visited.add(queue.get(0));
queue.remove(0);
if (!queue.isEmpty()) {
start = queue.get(0);
}
}
}
return false;
}
public String counterexample() {
for (Integer integer : theStack) {
counterexample += graph.displayVertex(integer);
if (integer != theStack.peek()) {
counterexample += "-->";
}
}
return counterexample;
}
// 与节点v相邻,并且这个节点没有被访问到,并且这个节点不在栈中
public int getAdjUnvisitedVertex(int v) {
ArrayList<Integer> arrayList = graph.getVertexList()[v]
.getAllVisitedList();
for (int j = 0; j < n; j++) {
if (graph.getAdjMat()[v][j] == 1 && arrayList.get(j) == 0
&& !theStack.contains(j)) {
graph.getVertexList()[v].setVisited(j);
return j;
}
}
return -1;
} // end getAdjUnvisitedVertex()
public void printTheStack(Stack<Integer> theStack2) {
for (Integer integer : theStack2) {
System.out.print(graph.displayVertex(integer));
if (integer != theStack2.peek()) {
System.out.print("-->");
}
}
}
}
import util.AF;
import util.Graph;
public class Main {
public static void main(String[] args) {
//第几张图,有两张(0,1),起点序号(0-6),终点序号(0-6)
AF operation = new AF(new Graph(0), 3, 6);
operation.getResult();
}
}
- 大小: 12.4 KB
- 大小: 12.9 KB
分享到:
相关推荐
图论算法-求(有向)图中任意两点间所有路径
算法中将一条线视为一个结点,采用广度优先搜索,利用树结构存储搜索结果,算法效率高,在武汉地铁11条线路190余个站点的线网图中测试,任意两点间的所有路径平均耗时0.2秒。只要对算法中的费用矩阵做调整,即可适用...
图论中求任意两点间的最短距离matlab程序实现
Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。通常可以在任何图中使用,包括有向图、带负权边的图。
含有各种障碍物的,水平面两点间最短的距离算法。就相当于计算你从一个地方走到另一个地方,最短的路径。 注意:不是图论!不是节点!不是Dijkstra!不是Floyd!
如果任意两个顶点之间有两条顶点不相交的路径,则无向图称为双连通图。在双连通图中,有一个通过任意两个顶点的简单循环。 按照约定,由边连接的两个节点构成双连通图,但这并不验证上述属性。对于具有两个以上顶点...
该算法实现在有向图中任意两点间的最短路径问题。 知识点5:表 table_node 和表 table_firstpath 创建一个记录顶点信息的表 table_node 和表 table_firstpath,表 table_node 记录了有向图所有节点的有关信息,如...
该算法可以找到从图中的任意顶点到其他所有顶点的最短路径。Floyd算法的时间复杂度为O(n^3),空间复杂度为O(n^2),其中n为图中的顶点数。 在本实现中,Floyd算法用于计算从任意站点到其他所有站点的最短路径。通过...
"图论中最短路问题的MATLAB...Dijkstra算法和Floyd算法都是解决图论中最短路问题的重要算法,MATLAB程序可以实现这两种算法,并且可以用于计算从起点到达所有点的最短路径的权和和路径,以及任意两点之间的最短路径长。
结点之间的距离定义为:设 u,v 为无向图 G 中任意两个顶点,若 u ~ v,称 u,v 之间长度最短的通路为 u,v 之间的短程线,短程线的长度称为 u,v 之间的距离,记作 d(u,v)。当 u,v 不连通时,规定 d(u,v) = ∞...
二、图论算法 1.最小生成树 A.Prim算法: B.Kruskal算法:(贪心) 2.最短路径 A.标号法求解单源点最短路径: B.Floyed算法求解所有顶点对之间的最短路径: C. Dijkstra 算法: 3.计算图的传递闭包 4.无向图的连通...
有向图的最小路径覆盖 0 / 1矩阵的最小覆盖 完备匹配(OK) 最优匹配(OK) 稳定婚姻 网络流问题 网络流模型的简单特征和与线性规划的关系 最大流最小割定理 最大流问题(OK) 有上下界的最大流问题 ...
4.Floyd算法求每对节点间最短路径 排序/查找: 1.快速排序 2.希尔排序 3.选择法排序 4.二分查找 数据结构: 1.顺序队列 2.顺序栈 3.链表 4.链栈 5.二叉树 ...
目录 一.数论 4 ...4.Floyd算法求每对节点间最短路径 排序/查找: 1.快速排序 2.希尔排序 3.选择法排序 4.二分查找 数据结构: 1.顺序队列 2.顺序栈 3.链表 4.链栈 5.二叉树
本文讨论的是动物园道路设计最优化问题,即在动物园的任意入口之间的最短道路径不大于两点连线的1.5倍的前提下,使得新修路的总路程最短,并绘出相应的道路设计图。 问题一给定了四个固定的道路交叉点,问题二则在...
两点距离(2D、 3D) 5.射向法判断点是否在 多边形内部 6.判断点是否在线段上 7.判断两线段是否相交 8. 相交判断线段与直线是否 9.点到线段最短距离 10.求两直线的交点 11.判断一个封闭图形是 凹集还是凸集 12....
奇偶点图上作业法是将奇点配成对,每一对奇点之间必有一条链,把这条链的所有边作为重复边加到图中去,新图中必无奇点。最小二分匹配法是将图分为两个部分,每个部分包含一个奇点,然后使用二分匹配算法来找到最小...
4.Floyd算法求每对节点间最短路径 5.解欧拉图 排序/查找: 1.快速排序 2.希尔排序 3.选择法排序 4.二分查找 高精度运算专题: 1.本专题公共函数说明 2.高精度比较 3.高精度加法 4.高精度...