啊哈算法（5）——图的遍历

桃扇骨 2022-05-15 04:20 226阅读 0赞

**图的深度优先遍历和广度优先遍历**  
1、深度优先遍历

#include<iostream>
    
    using namespace std;
    
    
    int e[101][101];//使用邻接矩阵来存储一个图
    int book[101];
    int sum, n;
    
    void dfs(int pos)
    {
        cout << pos << " ";
        sum++;
        if (sum == n)
            return;
        for (int i = 1; i <= n; ++i)
        {
            if (e[pos][i] == 1 && book[i] == 0)
            {
                book[i] = 1;
                dfs(i);
            }
        }
    }
    int main()
    {
        cin >> n;//图中节点的个数
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (i == j)
                    e[i][j] = 0;            
                else
                    e[i][j] = INT_MAX;        //没有边连接的记为最大
    
    
        int a, b;
        for (int i = 1; i <= n; ++i)
        {
            cin >> a >> b;
            e[a][b] = 1;
            e[b][a] = 1;     //由于为无向图 所以双向的
        }
        book[1] = 1;
        dfs(1);
        system("pause");
    }

2、广度优先遍历

#include<iostream>
    
    using namespace std;
    
    
    int e[101][101];//使用邻接矩阵来存储一个图
    int book[101];
    int sum, n;
    int que[10001];
    int main()
    {
        cin >> n;//图中节点的个数
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (i == j)
                    e[i][j] = 0;
                else
                    e[i][j] = INT_MAX;
    
    
        int a, b;
        for (int i = 1; i <= n; ++i)
        {
            cin >> a >> b;
            e[a][b] = 1;
            e[b][a] = 1;     //由于为无向图 所以双向的
        }
        int head=1, tail=1;
        que[head] = 1;
        book[1] = 1;
        tail++;
        while (head<tail)
        {
            int pos = que[head];
            cout << pos << " ";
            for (int i = 1; i <= n; ++i)
            {
                if (e[pos][i] == 1 && book[i] == 0)
                {
                    book[i] = 1;
                    que[tail] = i;
                    tail++;
                }
            }
            head++;
        }
        system("pause");
    }

**图遍历的应用**  
例1：城市地图，第一行给出n个城市（城市编号1~n），和m条公路。接下来每一行类似“a b c”这样的数据，表示有一条路可以从城市a到城市b，并且路程为c公里。公路都是单向的，求1到n的最短路径。

#include<iostream>
    
    using namespace std;
    
    
    int e[101][101];//使用邻接矩阵来存储一个图
    int book[101];
    int sum, n,m,min=INT_MAX;
    
    void dfs(int pos, int dis)
    {
        if (dis > min)
            return;
        if (pos == n)
        {
            min = dis;
            return;
        }   
        for (int i = 1; i <= n; ++i)
        {
            if (e[pos][i] != INT_MAX&&book[i] == 0)
            {
                book[i] = 1;
                dfs(i, dis + e[pos][i]);
                book[i] = 0;
            }
        }
    }
    int main()
    {
        cin >> n>>m;//图中节点的个数
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (i == j)
                    e[i][j] = 0;
                else
                    e[i][j] = INT_MAX;
    
    
        int a, b,c;
        for (int i = 1; i <= m; ++i)
        {
            cin >> a >> b>>c;
            e[a][b] = c;
            //e[b][a] = c;     //由于为无向图 所以双向的
        }
    
        book[1] = 1;
        dfs(1, 0);
        cout << min << endl;
        system("pause");
    }

例2：最少转机，第一行给出n个城市（城市编号1~n），和m条航线。以及起点城市a,和目标城市 ，接下来的m行表示两个城市之间可达，求最少的从起点城市到目标城市最少的转机次数。

#include<iostream>
    
    using namespace std;
    
    int e[101][101];  //用来存储地图
    int book[101];    //标记
    
    struct note
    {
        int x;//城市编号
        int s;//转机数目
    };
    int main()
    {
        struct note que[10001];//扩展队列 地图大小100*100
        int flag = 0;//用来标记到达目标城市
        int n, m, start, end;
        cin >> n >> m;
        cin >> start >> end;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (i == j)
                    e[i][j] = 0;
                else
                    e[i][j] = INT_MAX;
            }
        }
    
        int a, b;
        for (int i = 1; i <= m; ++i)
        {
            cin >> a >> b;
            e[a][b] = 1;
            e[b][a] = 1;
        }
    
        int head = 1, tail = 1;
        que[tail].x = start;
        que[tail].s = 0;
        tail++;
        book[start] = 1;
        while (head<tail)
        {
            int cur = que[head].x;
            for (int i = 1; i <= n; ++i)
            {
                if (e[cur][i] == 1 && book[i] == 0)
                {
                    que[tail].x = i;
                    que[tail].s = que[head].s + 1;
                    tail++;
                    book[i] = 1;
                }
    
                if (que[tail-1].x == end)
                {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1)
                break;
            head++;
        }
        cout << que[tail - 1].s << endl;
        system("pause");
    }

**note：当然这里也可以使用DFS，但是对于权值相同的情况，使用BFS更快**