java搜索無向圖中兩點之間所有路徑的算法

更新時間：2019年01月17日 09:56:07 投稿：lijiao

這篇文章主要介紹了java搜索無向圖中兩點之間所有路徑的算法

參考 java查找無向連通圖中兩點間所有路徑的算法，對代碼進(jìn)行了部分修改，并編寫了測試用例。

算法要求：

1. 在一個無向連通圖中求出兩個給定點之間的所有路徑；
2. 在所得路徑上不能含有環(huán)路或重復(fù)的點；

算法思想描述：

1. 整理節(jié)點間的關(guān)系，為每個節(jié)點建立一個集合，該集合中保存所有與該節(jié)點直接相連的節(jié)點（不包括該節(jié)點自身）；

2. 定義兩點一個為起始節(jié)點，另一個為終點，求解兩者之間的所有路徑的問題可以被分解為如下所述的子問題：對每一個與起始節(jié)點直接相連的節(jié)點，求解它到終點的所有路徑（路徑上不包括起始節(jié)點）得到一個路徑集合，將這些路徑集合相加就可以得到起始節(jié)點到終點的所有路徑；依次類推就可以應(yīng)用遞歸的思想，層層遞歸直到終點，若發(fā)現(xiàn)希望得到的一條路徑，則轉(zhuǎn)儲并打印輸出；若發(fā)現(xiàn)環(huán)路，或發(fā)現(xiàn)死路，則停止尋路并返回；

3. 用棧保存當(dāng)前已經(jīng)尋到的路徑（不是完整路徑）上的節(jié)點，在每一次尋到完整路徑時彈出棧頂節(jié)點；而在遇到從棧頂節(jié)點無法繼續(xù)向下尋路時也彈出該棧頂節(jié)點，從而實現(xiàn)回溯。

實現(xiàn)代碼

1.Node.java

import java.util.ArrayList;
 
/* 表示一個節(jié)點以及和這個節(jié)點相連的所有節(jié)點 */
public class Node
{
 public String name = null;
 public ArrayList<Node> relationNodes = new ArrayList<Node>();
 
 public String getName() {
 return name;
 }
 
 public void setName(String name) {
 this.name = name;
 }
 
 public ArrayList<Node> getRelationNodes() {
 return relationNodes;
 }
 
 public void setRelationNodes(ArrayList<Node> relationNodes) {
 this.relationNodes = relationNodes;
 }
}

2.test.java

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;
 
 
public class test {
 /* 臨時保存路徑節(jié)點的棧 */
 public static Stack<Node> stack = new Stack<Node>();
 /* 存儲路徑的集合 */
 public static ArrayList<Object[]> sers = new ArrayList<Object[]>();
 
 /* 判斷節(jié)點是否在棧中 */
 public static boolean isNodeInStack(Node node)
 {
 Iterator<Node> it = stack.iterator();
 while (it.hasNext()) {
 Node node1 = (Node) it.next();
 if (node == node1)
 return true;
 }
 return false;
 }
 
 /* 此時棧中的節(jié)點組成一條所求路徑，轉(zhuǎn)儲并打印輸出 */
 public static void showAndSavePath()
 {
 Object[] o = stack.toArray();
 for (int i = 0; i < o.length; i++) {
 Node nNode = (Node) o[i];
 
 if(i < (o.length - 1))
 System.out.print(nNode.getName() + "->");
 else
 System.out.print(nNode.getName());
 }
 sers.add(o); /* 轉(zhuǎn)儲 */
 System.out.println("\n");
 }
 
 /*
 * 尋找路徑的方法 
 * cNode: 當(dāng)前的起始節(jié)點currentNode
 * pNode: 當(dāng)前起始節(jié)點的上一節(jié)點previousNode
 * sNode: 最初的起始節(jié)點startNode
 * eNode: 終點endNode
 */
 public static boolean getPaths(Node cNode, Node pNode, Node sNode, Node eNode) {
 Node nNode = null;
 /* 如果符合條件判斷說明出現(xiàn)環(huán)路，不能再順著該路徑繼續(xù)尋路，返回false */
 if (cNode != null && pNode != null && cNode == pNode)
 return false;
 
 if (cNode != null) {
 int i = 0;
 /* 起始節(jié)點入棧 */
 stack.push(cNode);
 /* 如果該起始節(jié)點就是終點，說明找到一條路徑 */
 if (cNode == eNode)
 {
 /* 轉(zhuǎn)儲并打印輸出該路徑，返回true */
 showAndSavePath();
 return true;
 }
 /* 如果不是,繼續(xù)尋路 */
 else
 {
 /* 
  * 從與當(dāng)前起始節(jié)點cNode有連接關(guān)系的節(jié)點集中按順序遍歷得到一個節(jié)點
  * 作為下一次遞歸尋路時的起始節(jié)點 
  */
 nNode = cNode.getRelationNodes().get(i);
 while (nNode != null) {
  /*
  * 如果nNode是最初的起始節(jié)點或者nNode就是cNode的上一節(jié)點或者nNode已經(jīng)在棧中 ， 
  * 說明產(chǎn)生環(huán)路 ，應(yīng)重新在與當(dāng)前起始節(jié)點有連接關(guān)系的節(jié)點集中尋找nNode
  */
  if (pNode != null
  && (nNode == sNode || nNode == pNode || isNodeInStack(nNode))) {
  i++;
  if (i >= cNode.getRelationNodes().size())
  nNode = null;
  else
  nNode = cNode.getRelationNodes().get(i);
  continue;
  }
  /* 以nNode為新的起始節(jié)點，當(dāng)前起始節(jié)點cNode為上一節(jié)點，遞歸調(diào)用尋路方法 */
  if (getPaths(nNode, cNode, sNode, eNode))/* 遞歸調(diào)用 */
  {
  /* 如果找到一條路徑，則彈出棧頂節(jié)點 */
  stack.pop();
  }
  /* 繼續(xù)在與cNode有連接關(guān)系的節(jié)點集中測試nNode */
  i++;
  if (i >= cNode.getRelationNodes().size())
  nNode = null;
  else
  nNode = cNode.getRelationNodes().get(i);
 }
 /* 
  * 當(dāng)遍歷完所有與cNode有連接關(guān)系的節(jié)點后，
  * 說明在以cNode為起始節(jié)點到終點的路徑已經(jīng)全部找到 
  */
 stack.pop();
 return false;
 }
 } else
 return false;
 }
 
 public static void main(String[] args) {
 /* 定義節(jié)點關(guān)系 */
 int nodeRalation[][] =
 {
 {1},  //0
 {0,5,2,3},//1
 {1,4}, //2
 {1,4}, //3
 {2,3,5}, //4
 {1,4}  //5
 };
 
 /* 定義節(jié)點數(shù)組 */
 Node[] node = new Node[nodeRalation.length];
 
 for(int i=0;i<nodeRalation.length;i++)
 {
   node[i] = new Node();
 node[i].setName("node" + i);
 }
 
 /* 定義與節(jié)點相關(guān)聯(lián)的節(jié)點集合 */
 for(int i=0;i<nodeRalation.length;i++)
 {
 ArrayList<Node> List = new ArrayList<Node>();
 
 for(int j=0;j<nodeRalation[i].length;j++)
 {
 List.add(node[nodeRalation[i][j]]);
 }
 node[i].setRelationNodes(List);
 List = null; //釋放內(nèi)存
 }
 
 /* 開始搜索所有路徑 */
 getPaths(node[0], null, node[0], node[4]);
 }
}

輸出：