graph-trace

发表于

用dfs来记录从起始点到终点的路径。

  • 当没有环的时候，我们不需要记录哪个顶点没有被访问过，这样也不会导致死循环。
  • 而当有环的时候，则必须记录哪个顶点有被访问过，在本次寻找的过程中不能再访问他，防止死循环。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    #include <iostream>
    #include <stdio.h>
    #include <vector>
    #include <string.h>
    using namespace std;
    vector<int> mstack;
    int road[6][6];
    bool visit[6];
    void dfs(int start){
        if (start == 5){
            mstack.push_back(5);
            for (int i = 0; i < mstack.size(); ++i) {
                cout<<mstack[i]<<" ";
            }
            mstack.pop_back();
            cout<<endl;
            return;
        }
        for (int i = 1; i <= 5; ++i) {
            if (road[start][i]&&!visit[i]){
                mstack.push_back(start);
                visit[i] = true;
                dfs(i);
                visit[i] =false;
                mstack.pop_back();
            }
        }
    }
    int main(){
        memset(road,0,sizeof(road));
        memset(visit,0,sizeof(visit));
        road[1][3] = 1;
        road[1][2] = 1;
        road[2][4] = 1;
        road[2][3] = 1;
        road[3][4] = 1;
        road[3][5] = 1;
        road[4][5] = 1;
        road[4][3] = 1;
        visit[1] = true;
        dfs(1);
        visit[1] = false;
    }

代码用到的图