算法-计算无向图中两个节点之间所有的路径

本文主要是介绍算法-计算无向图中两个节点之间所有的路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、深度优先遍历

1.1 深度优先遍历的定义

深度优先搜索（Depth_First Search）遍历类似于树的先根遍历，是树的先根遍历的推广。

假设给定图G，图中所有顶点未曾被访问过，则深度优先搜索可以从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。这是一个递归的过程。

1.2 图的深度优先遍历的过程

假设给定图G，设x 是当前被访问顶点，在对x 做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y 已访问过，则重新选择另一条从x 出发的未检测过的边，否则若顶点y未被访问过，沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y 出发的所有路径，即访问完所有从y 出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x 出发的未检测过的边。上述过程直至从x 出发的所有边都已检测过为止。此时，若x 不是源点，则回溯到在x 之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G 是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。

2、求两点间所有路径的算法

图1 连通图G

图2 G的邻接表存储结构

假设简单连通图如图1 所示，那么它的邻接表存储结构如图2 所示。假设我们要找出结点3到结点6的所有路径，那么，我们就设结点3为起点，结点6为终点。我们需要的存储结构有：一个保存路径的栈、一个保存已标记结点的数组，那么找到结点3到结点6的所有路径步骤如下：

（1）我们建立一个存储结点的栈结构，将起点3 入栈，将结点3 标记为入栈状态；

（2）从结点3 出发，找到结点3 的第一个非入栈状态的邻结点1，将结点1 标记为入栈状态；

（3）从结点1 出发，找到结点1 的第一个非入栈状态的邻结点0，将结点0 标记为入栈状态；

（4）从结点0 出发，找到结点0 的第一个非入栈状态的邻结点2，将结点2 标记为入栈状态；

（5）从结点2 出发，找到结点2 的第一个非入栈状态的邻结点5，将结点5 标记为入栈状态；

（6）从结点5 出发，找到结点5 的第一个非入栈状态的邻结点6，将结点6 标记为入栈状态；

（7）栈顶结点6 是终点，那么，我们就找到了一条起点到终点的路径，输出这条路径；

（8）从栈顶弹出结点6，将6 标记为非入栈状态；

（9）现在栈顶结点为5，结点5 没有除终点外的非入栈状态的结点，所以从栈顶将结点5 弹出；

（10）现在栈顶结点为2，结点2 除了刚出栈的结点5 之外，还有非入栈状态的结点6，那么我们将结点6 入栈；

（11）现在栈顶为结点6，即找到了第二条路径，输出整个栈，即为第二条路径；

（12）重复步骤2-11，就可以找到从起点3 到终点6 的所有路径；

（13）栈为空，算法结束。

#include <stack>

#include <iostream>
using namespace std;
#define NUM 10
#define MAX_PATH 100

struct Node
{
    int key;
    int flag;
    Node()
    {
        flag=0;
    }
};

class Graph
{
   public:
        //stack<int> searchStack;
        int resultPath[MAX_PATH][NUM];
        int result[NUM+1];//将result设为NUM+1，主要是为了避免发生B->D->B的事情

        Node headNode;//起始节点
        Node endNode;//终止节点
        stack<Node> tempStack;
        int pathNum;
        int nPos;
        bool Mark[NUM];

   public:
        Graph()
        {
            //将矩阵中的元素置为空
            for (int i=0;i<NUM;i++)
            {
                for (int j=0;j<MAX_PATH;j++)
                {
                    resultPath[i][j]=0;
                }
                result[i]=0;

                Mark[i]=false;
            }
            result[NUM]=0;
            pathNum=0;
            nPos=0;
        }

    void test()
    {
        //对应无向图的矩阵
        int Matrix[NUM][NUM]={
            {0,1,0,1,0}, //A
            {1,0,1,0,1}, //B
            {0,1,0,1,1}, //C
            {1,0,1,0,0}, //D
            {0,1,1,0,0}  //E
        };
        //开始节点
        headNode.key=1;
        headNode.flag=1;

        //结束节点
        endNode.key=5;

        FindAllPath(Matrix,headNode,endNode);
        cout<<"顶点"<<headNode.key<<"到顶点"<<endNode.key<<"路径数目为："<<pathNum<<endl;
        for (int i=0;i<pathNum;i++)
        {
            cout<<"第"<<i<<"条: ";
            for(int j=0;j<NUM;j++)
            {
                if (resultPath[i][j]==0)
                {
                    break;
                }
                cout<<resultPath[i][j]<<"  ";
            }
            cout<<endl;
        }
        int i=0;
    }

    void FindAllPath(int Matrix[NUM][NUM],Node startNodeKey,Node endNodeKey)
    {
        result[nPos]=startNodeKey.key;  //将当前元素放入结果集中
        Mark[startNodeKey.key-1]=true;  //将访问标记为已访问
        nPos++;  //结果集索引加1
        while(nPos!=0)
        {
            int tempVal=result[nPos-1];//获取到最前面的元素
            if (tempVal==endNodeKey.key)  //若当前元素为目标节点
            {
                for (int j=0;j<nPos;j++)
                {
                    resultPath[pathNum][j]=result[j];  //将结果集复制于最后的路径矩阵中
                }
                nPos--;  //回溯至上一个节点
                result[nPos]=0;  //结果集对应索引置为空
                pathNum++;  //路径数目加1
                Mark[endNodeKey.key-1]=false;
                break;
            }
            while(startNodeKey.flag<NUM)//利用flag来指示每次的元素的索引
            {
                if (Matrix[tempVal-1][startNodeKey.flag]==1)
                {
                    if (Mark[startNodeKey.flag]==false)//利用Mark来判断是否已经访问过该节点
                    {
                        Node tempNode;
                        tempNode.key=startNodeKey.flag+1;
                        FindAllPath(Matrix,tempNode,endNodeKey);//深度优先遍历算法，
                    }
                }
                startNodeKey.flag++;//索引值相应的加一
            }

            if (startNodeKey.flag==NUM)//如果已经是到最后的邻居，说明访问结束，
            {                           //将对应的值置为空
                nPos--;  //再次向上回溯
                startNodeKey.flag=0;  //将节点的索引置为空
                result[nPos]=0;  //将结果集中对应的索引置为空
                Mark[startNodeKey.key-1]=false;  //访问之后标记为未访问。因为下面的元素已经访问结束，便于下次的访问
                break;
            }
        }
    }
};

int main()
{
    Graph G;
   G.test();
    return 0;
}

private Set<Integer> nodes;
private Map<Integer, LinkedList<Integer>> links;
private Map<Link, Weight> weights;
nodes用于存储所有节点，不重复；links为邻接表；weights为边上的权值。

1、两点间最短路径（dijkstra算法）

实现代码为：

public Path shortestPath(int a_node, int b_node)
   {
       //从a_node到其他节点的代价,有序排列
       Map<Integer, Path> cost = new HashMap<Integer, Path>();
       //sNodes初始为空
       LinkedList<Integer> sNodes = new LinkedList<Integer>();
       //qNodes初始为整个节点集
       LinkedList<Integer> qNodes = new LinkedList<Integer>();
       for (int node : nodes)
       {
           qNodes.add(node);
           cost.put(node, new Path(new Weight(Float.MAX_VALUE)));
       }
       cost.put(a_node, new Path(new Link(a_node, a_node), new Weight(0.0f)));
       //每次迭代qNodes集中被选中的节点
       int uNode;
       while (!qNodes.isEmpty())
       {
           uNode = extractMin(qNodes, cost);
           sNodes.add(uNode);
           if (uNode == b_node)//已经找到到b_node的最短路径
               break;
           for (int vNode : adjNodes(uNode))//代表qNodes集合中的某一节点
           {
               relax(cost, uNode, vNode);
           }
       }

       return cost.get(b_node);
   }
其中extractMin函数从qNodes集合中选取从源点出发代价最小的点。relax函数使用到了松弛（relaxation）技术。对于每个顶点v ∈ V，都设置一个属性d[v]，用来描述从源点s到v的最短路径上权值的上界，称为最短路径估计（shortest-path estimate）。在松弛一条边（u，v）的过程中，要测试是否可以通过u，对迄今找到的到v的最短路径进行改进；如果可以，就更新。一次松弛操作可以减小最短路径估计的值。（摘自《算法导论》）
     如果只要找出源点到特定点的最短路径，可以提前跳出循环，如代码中所示。

2、两点间所有路径

实现代码如下：

public LinkedList<Path> allPath(int a_node, int b_node, Weight max)
   {
       LinkedList<Path> apath = new LinkedList<Path>();
       int top_node; //即栈顶节点
       int cur_node;//当前的临接节点
       int next_node;//下一个入栈节点
       //遍历过程中使用的栈
       LinkedList<Integer> stack = new LinkedList<Integer>();
       //标记节点是否在栈内，避免回路
       Map<Integer, Integer> states = new HashMap<Integer, Integer>();
       //记录栈中路径长度
       Weight weight;
       for (int node : nodes)
       {
           states.put(node, 0);//0表示不在栈内
       }
       //初始化变量
       stack.add(a_node);
       weight = new Weight();//初始化为0
       states.put(a_node, 1);
       cur_node = -1; //定义为第一个临接节点的前一个
       while (!stack.isEmpty())
       {
           top_node = stack.getLast();
           weight = calWeight(stack);
           //路径是否超出最大权值
           if (weight.compareTo(max) > 0)
           {
               cur_node = stack.removeLast();
               states.put(cur_node, 0);
               continue;
           }
           //找到一条路径
           if (top_node == b_node)
           {
               apath.add(genPath(stack, weight));
               cur_node = stack.removeLast();
               states.put(cur_node, 0);
           }
           else
           {
               next_node = nextNode(top_node, cur_node, states);
               if (next_node < Integer.MAX_VALUE)
               {
                   stack.add(next_node);
                   states.put(next_node, 1);
                   cur_node = -1; //新节点入栈，要从头遍历它的所有临接节点
               }
               else
               {
                   cur_node = stack.removeLast();
                   states.put(cur_node, 0);
               }
           }

       }
       return apath;

   }