图论算法-求（有向）图中任意两点间所有路径

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

1建图：

     图类中包括如下信息：顶点集合，邻接矩阵。

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


图论算法-求（有向）图中任意两点间所有路径

  

图1


图论算法-求（有向）图中任意两点间所有路径

  

图2

 

2 算法思路

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

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

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

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

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

  F 重复执行B – E,直到栈中元素为空

 

 

Java代码  
  1. package util;  
  2.   
  3. public class Graph {  
  4.   
  5.     private Vertex vertexList[]; // list of vertices  
  6.     private int adjMat[][]; // adjacency matrix  
  7.   
  8.     private int nVerts;  
  9.     private static int MAX_VERTS = 7; // n个点  
  10.   
  11.     int i = 0;  
  12.     int j = 0;  
  13.   
  14.     public Vertex[] getVertexList() {  
  15.         return vertexList;  
  16.     }  
  17.   
  18.     public int[][] getAdjMat() {  
  19.         return adjMat;  
  20.     }  
  21.   
  22.     public int getN() {  
  23.         return MAX_VERTS;  
  24.     }  
  25.   
  26.     public Graph(int index) {  
  27.         adjMat = new int[MAX_VERTS][MAX_VERTS]; // 邻接矩阵  
  28.         vertexList = new Vertex[MAX_VERTS]; // 顶点数组  
  29.         nVerts = 0;  
  30.   
  31.         for (i = 0; i < MAX_VERTS; i++) {  
  32.             for (j = 0; j < MAX_VERTS; j++) {  
  33.                 adjMat[i][j] = 0;  
  34.             }  
  35.         }  
  36.   
  37.         addVertex('A');  
  38.         addVertex('B');  
  39.         addVertex('C');  
  40.         addVertex('D');  
  41.         addVertex('E');  
  42.         addVertex('F');  
  43.         addVertex('G');  
  44.   
  45.         addEdge(0, 1);  
  46.         addEdge(0, 2);  
  47.         addEdge(1, 4);  
  48.         addEdge(2, 0);  
  49.         addEdge(2, 5);  
  50.         addEdge(3, 0);  
  51.         addEdge(3, 2);  
  52.         addEdge(3, 3);  
  53.         addEdge(4, 1);  
  54.         addEdge(4, 2);  
  55.         addEdge(5, 6);  
  56.         addEdge(6, 3);  
  57.   
  58.         switch (index) {  
  59.         case 0:  
  60.             break;  
  61.         case 1:  
  62.             delEdge(4, 2);  
  63.             break;  
  64.         default:  
  65.             break;  
  66.         }  
  67.     }  
  68.   
  69.     private void delEdge(int start, int end) {  
  70.         adjMat[start][end] = 0;  
  71.     }  
  72.   
  73.     private void addEdge(int start, int end) {// 有向图，添加边  
  74.         adjMat[start][end] = 1;  
  75.         // adjMat[end][start] = 1;  
  76.     }  
  77.   
  78.     public void addVertex(char lab) {  
  79.         vertexList[nVerts++] = new Vertex(lab);// 添加点  
  80.     }  
  81.   
  82.     public char displayVertex(int i) {  
  83.         return vertexList[i].getLabel();  
  84.     }  
  85.   
  86.     public boolean displayVertexVisited(int i) {  
  87.         return vertexList[i].WasVisited();  
  88.     }  
  89.   
  90.     public void printGraph() {  
  91.         for (i = 0; i < MAX_VERTS; i++) {  
  92.             System.out.print("第" + displayVertex(i) + "个节点:" + " ");  
  93.   
  94.             for (j = 0; j < MAX_VERTS; j++) {  
  95.                 System.out.print(displayVertex(i) + "-" + displayVertex(j)  
  96.                         + "：" + adjMat[i][j] + " ");  
  97.             }  
  98.             System.out.println();  
  99.         }  
  100.   
  101.     }  
  102.   
  103. }  

 package util;

Java代码  
  1. import java.util.ArrayList;  
  2.   
  3. public class Vertex {  
  4.   
  5.     boolean wasVisited; // 是否遍历过  
  6.     public char label; // 节点名称  
  7.     ArrayList allVisitedList;// 节点已访问过的顶点  
  8.   
  9.     public void setAllVisitedList(ArrayList allVisitedList) {  
  10.         this.allVisitedList = allVisitedList;  
  11.     }  
  12.   
  13.     public ArrayList getAllVisitedList() {  
  14.         return allVisitedList;  
  15.     }  
  16.   
  17.     public boolean WasVisited() {  
  18.         return wasVisited;  
  19.     }  
  20.   
  21.     public void setWasVisited(boolean wasVisited) {  
  22.         this.wasVisited = wasVisited;  
  23.     }  
  24.   
  25.     public char getLabel() {  
  26.         return label;  
  27.     }  
  28.   
  29.     public void setLabel(char label) {  
  30.         this.label = label;  
  31.     }  
  32.   
  33.     public Vertex(char lab) // constructor  
  34.     {  
  35.         label = lab;  
  36.         wasVisited = false;  
  37.     }  
  38.   
  39.     public void setVisited(int j) {  
  40.         allVisitedList.set(j, 1);  
  41.   
  42.     }  
  43.   
  44. }  

 package util;

Java代码  
  1. import java.util.ArrayList;  
  2. import java.util.Stack;  
  3.   
  4. public class AF {  
  5.   
  6.     boolean isAF = true;  
  7.     Graph graph;  
  8.     int n;  
  9.     int start, end;  
  10.     Stack theStack;  
  11.   
  12.     private ArrayList tempList;  
  13.     private String counterexample;  
  14.   
  15.     public AF(Graph graph, int start, int end) {  
  16.         this.graph = graph;  
  17.         this.start = start;  
  18.         this.end = end;  
  19.     }  
  20.   
  21.     public boolean getResult() {  
  22.         graph.printGraph();  
  23.         n = graph.getN();  
  24.         theStack = new Stack();  
  25.   
  26.         if (!isConnectable(start, end)) {  
  27.             isAF = false;  
  28.             counterexample = "节点之间没有通路";  
  29.         } else {  
  30.             for (int j = 0; j < n; j++) {  
  31.                 tempList = new ArrayList();  
  32.                 for (int i = 0; i < n; i++) {  
  33.                     tempList.add(0);  
  34.                 }  
  35.                 graph.getVertexList()[j].setAllVisitedList(tempList);  
  36.             }  
  37.   
  38.             isAF = af(start, end);  
  39.         }  
  40.         return isAF;  
  41.     }  
  42.   
  43.     private boolean af(int start, int end) {  
  44.         graph.getVertexList()[start].setWasVisited(true); // mark it  
  45.         theStack.push(start); // push it  
  46.   
  47.         while (!theStack.isEmpty()) {  
  48.             int v = getAdjUnvisitedVertex(theStack.peek());  
  49.             if (v == -1) // if no such vertex,  
  50.             {  
  51.                 tempList = new ArrayList();  
  52.                 for (int j = 0; j < n; j++) {  
  53.                     tempList.add(0);  
  54.                 }  
  55.                 graph.getVertexList()[theStack.peek()]  
  56.                         .setAllVisitedList(tempList);// 把栈顶节点访问过的节点链表清空  
  57.                 theStack.pop();  
  58.             } else // if it exists,  
  59.             {  
  60.                 theStack.push(v); // push it  
  61.             }  
  62.   
  63.             if (!theStack.isEmpty() && end == theStack.peek()) {  
  64.                 graph.getVertexList()[end].setWasVisited(false); // mark it  
  65.                 printTheStack(theStack);  
  66.                 System.out.println();  
  67.                 theStack.pop();  
  68.             }  
  69.         }  
  70.   
  71.         return isAF;  
  72.     }  
  73.   
  74.     // 判断连个节点是否能连通  
  75.     private boolean isConnectable(int start, int end) {  
  76.         ArrayList queue = new ArrayList();  
  77.         ArrayList visited = new ArrayList();  
  78.         queue.add(start);  
  79.         while (!queue.isEmpty()) {  
  80.             for (int j = 0; j < n; j++) {  
  81.                 if (graph.getAdjMat()[start][j] == 1 && !visited.contains(j)) {  
  82.                     queue.add(j);  
  83.                 }  
  84.             }  
  85.             if (queue.contains(end)) {  
  86.                 return true;  
  87.             } else {  
  88.                 visited.add(queue.get(0));  
  89.                 queue.remove(0);  
  90.                 if (!queue.isEmpty()) {  
  91.                     start = queue.get(0);  
  92.                 }  
  93.             }  
  94.         }  
  95.         return false;  
  96.     }  
  97.   
  98.     public String counterexample() {  
  99.         for (Integer integer : theStack) {  
  100.             counterexample += graph.displayVertex(integer);  
  101.             if (integer != theStack.peek()) {  
  102.                 counterexample += "-->";  
  103.             }  
  104.         }  
  105.   
  106.         return counterexample;  
  107.     }  
  108.   
  109.     // 与节点v相邻，并且这个节点没有被访问到，并且这个节点不在栈中  
  110.     public int getAdjUnvisitedVertex(int v) {  
  111.         ArrayList arrayList = graph.getVertexList()[v]  
  112.                 .getAllVisitedList();  
  113.         for (int j = 0; j < n; j++) {  
  114.             if (graph.getAdjMat()[v][j] == 1 && arrayList.get(j) == 0  
  115.                     && !theStack.contains(j)) {  
  116.                 graph.getVertexList()[v].setVisited(j);  
  117.                 return j;  
  118.             }  
  119.         }  
  120.         return -1;  
  121.     } // end getAdjUnvisitedVertex()  
  122.   
  123.     public void printTheStack(Stack theStack2) {  
  124.         for (Integer integer : theStack2) {  
  125.             System.out.print(graph.displayVertex(integer));  
  126.             if (integer != theStack2.peek()) {  
  127.                 System.out.print("-->");  
  128.             }  
  129.         }  
  130.     }  
  131.   
  132. }  

 import util.AF;

Java代码  
  1. import util.Graph;  
  2.   
  3. public class Main {    
  4.     public static void main(String[] args) {  
  5.         //第几张图，有两张(0,1)，起点序号(0-6)，终点序号(0-6)  
  6.         AF operation = new AF(new Graph(0), 3, 6);  
  7.         operation.getResult();  
  8.   
  9.     }  
  10. }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/luckForever/p/7254240.html