遍历寻找给定两点之间的所有路径

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

直接入题,参加2017年华为竞赛的时候,需要输出路径,当时设了源点和汇点,是单源单汇的寻路径,那么问题就归为寻找给定两点之间的所有路径问题


一张盗别人的图

我们的老师一直教我们这些菜鸟们说,写程序一定要先在纸上写好考虑清楚,这次我觉得这个应该挺简单的,就没写,没想到出现了错误,难调,搞了好久,死循环。然后自己乖乖的关掉vs,乖乖写思路。
首先,确认目的,也就是输入,也就是我们题目的问题:寻找给定两点之间的所有路径,上个例子吧,好说也好顺思路:

假如我们需要找0->11之间所有路径,那么我们希望得到的输出结果应该就是:
路径1:0–>1–>2–>5–>7–>11
路径2: 0–>1–>2–>5–>8–>11
路径3: 0–>1–>2–>6–>9–>11
路径4:0–>1–>2–>6–>10–>11
路径5:0–>1–>3–>11
路径6: 0–>1–>4–>11
到此,程序输入输出确定:

  • 输入:带有节点和边的信息的邻接矩阵
  • 输出:就是上面的提到的路径

建立上图的邻接矩阵A,节点i->j之间有边,则A(i,j)==1
上图的邻接矩阵就是:

这里写图片描述

接下来就是怎么输出来路径,DFS,BFS都行,先想想如果自己去找路径,怎么搜?也好想,从源点“0”出发,由于编号是按顺序的,而且终点是编号最大的那个点,我就偷个懒,特殊情况特殊对待吧,还是画图最直观。
还是来看邻接矩阵:

这里写图片描述
这里写图片描述

首先将起点 0 入栈,设置入栈状态为1,从例图可以看出,与0相连的,最先开始搜到 1 ,即第0行第1列红色框,将节点1入栈,入栈状态设置为1,继续,从第1行开始搜,搜到第一个非零点,即第1行第2列的红色框,将节点2入栈,如此往复,知道找到终点 11 ,就得到了路径:0–>1–>2–>5–>7–>11。

接下来要搜索下一条路径,将节点 11 出栈,入栈状态设置为 0 ,在考虑是否要将节点7出栈,我们从例图可以看到,第7行我们一行都已经搜索完毕了,都搜索到终点 11 了,那么节点7就必须出栈,因为如果不出栈,从节点 7 搜索就会再一次搜索到节点 11,那么就陷入死循环了,所以必须将 7 出栈,而且应该从节点 7 之后的搜索,因为节点 7 之前要么是已经搜索过得,要么就是第一个搜索到的,所以需要记录终点之前的节点位置,那么接下来,可以看到节点 8 非零,那么从第 8 行开始搜索,检查搜到的节点的入栈状态,又搜索到终点 11 ,那么就搜到路径:0–>1–>2–>5–>8–>11,以便从其之后继续搜索路径,依次输出各个路径,直至栈内为空为止。
那么需要的变量应该是:邻接矩阵,入栈状态变量,存储path组的结构,以及存储单个path的vector, 存储寻找路径的栈,以及一个记录位置变量。

代码如下:

#include<iostream>
#include<vector>
#include<stack>
#define MAX_EDGE_NUM  500
#define MAX_LINE_LEN 200
using namespace std;
//读取文件的函数
int read_file(char ** const buff, const unsigned int spec, const char * const filename)
{
    FILE *fp = fopen(filename, "r");
    if (fp == NULL)
    {
        printf("Fail to open file %s, %s.\n", filename, strerror(errno));
        return 0;
    }
    printf("Open file %s OK.\n", filename);

    char line[MAX_LINE_LEN + 2];
    unsigned int cnt = 0;
    while ((cnt < spec) && !feof(fp))
    {
        line[0] = 0;
        if (fgets(line, MAX_LINE_LEN + 2, fp) == NULL)  continue;
        if (line[0] == 0)   continue;
        buff[cnt] = (char *)malloc(MAX_LINE_LEN + 2);
        strncpy(buff[cnt], line, MAX_LINE_LEN + 2 - 1);
        buff[cnt][MAX_LINE_LEN + 1] = 0;
        cnt++;
    }
    fclose(fp);
    printf("There are %d lines in file %s.\n", cnt, filename);

    return cnt;
}
//将每行的数据转换为int的函数
void  char2int(char* char_data, int *int_data, int int_length)
{
    char c[10];
    int num = 0;
    int count = 0;
    for (int i = 0; i < 10;)
    {
        count = 0;
        while (char_data[i] != ' ' && char_data[i] != '\n' && char_data[i] != '\r' && count <10)
        {
            c[count] = char_data[i];
            i++;
            count++;
        }
        int_data[num] = atoi(c);
        memset(c, 0, 10);
        ++num;
        if (num >= int_length)
        {
            return;
        }
        i++;
    }
}
int main(int argc, char *argv[])
{

    char *topo[MAX_EDGE_NUM];
    int line_num;
    //读取文件,需要在属性--配置属性--调试--命令参数,以及工作目录设置所读取的文件node.txt
    char *topo_file = argv[1];
    line_num = read_file(topo, MAX_EDGE_NUM, topo_file);


    printf("line num is :%d \n", line_num);
    if (line_num == 0)
    {
        printf("Please input valid topo file.\n");
        return -1;
    }
    //邻接矩阵
    int node_num = 11;
    short **adjcent_Matrix = new short*[node_num + 1]();//初始化邻接矩阵全为0
    for (int i = 0; i < node_num; i++)
    {
        adjcent_Matrix[i] = new short[node_num + 1]();
    }
    //按照例图填充邻接矩阵
    int start_node,end_node;
    int data2[2];
    for (int i = 0; i < line_num; i++)
    {
        char2int(topo[i], data2, 2);
        start_node = data2[0];
        end_node = data2[1];
        adjcent_Matrix[start_node][end_node] = 1;
    }
    bool* is_in_stack = new bool[node_num+1]();//入栈状态变量
    stack<int>node_stack;
    int c_position = 0;
    vector<vector<int>>paths;//存储所有路径
    vector<int>path;//存储单条路径

    //起点入栈
    node_stack.push(0);
    is_in_stack[0] = 1;//设置起点已入栈,1表示在栈中,0 表示不在
    int top_element;//记录栈顶元素
    int tmp;
    while (!node_stack.empty())
    {
        top_element = node_stack.top();//查看栈顶元素,判断是否已经到达终点
        if (top_element == node_num)//若到达终点,输出路径,弹出栈中两个点,设置出栈状态
        {
            while (!node_stack.empty())
            {
                tmp = node_stack.top();
                node_stack.pop();
                path.push_back(tmp);
            }
            paths.push_back(path);//将路径加入路径组
            for (vector<int>::reverse_iterator rit = path.rbegin(); rit != path.rend(); rit++)
            {
                node_stack.push(*rit);
            }
            path.clear();//清除单条路径

            node_stack.pop();
            is_in_stack[top_element] = 0;
            c_position = node_stack.top();//记录位置,以便从该位置之后进行搜索
            top_element = node_stack.top();
            node_stack.pop();
            is_in_stack[top_element] = 0; //cout << vis[top_element];
        }
        else
        {
            int i = 0;
            for (i = c_position + 1; i <node_num + 2; i++)
            {

                if (is_in_stack[i] == 0 && adjcent_Matrix[top_element][i] != 0)//未入栈,而且节点之间有边相连
                {

                    is_in_stack[i] = 1;//stack In
                    node_stack.push(i);//入栈
                    c_position = 0;//位置置零,是因为从记录的位置开始搜索完以后,在新的行上搜索,自然从零开始,以免漏掉节点
                    break;
                }
            }
            if (i == node_num + 2)
            {
                top_element = node_stack.top();
                is_in_stack[top_element] = 0;
                c_position = node_stack.top();
                node_stack.pop();
            }
        }
    }
    //========================  输出 ==========================
    //逆向
    for (int i = 0; i <paths.size(); i++)
    {
        cout << "路径" << i << ": ";
        for (int j = paths[i].size()-1; j >=0; j--)
        {
            if (j == 0)
            {
                cout << paths[i][j];
            }
            else
            {
                cout << paths[i][j] << "->";
            }

        }
        cout << endl;
    }
    //========================  输出 ==========================

    //删除内存
    for (int i = 0; i < node_num ; i++)
    {
        delete[] adjcent_Matrix[i];
    }
    delete[] adjcent_Matrix;
}

他强任他强!

点这里可以跳转到人工智能网站

发表评论