DS图遍历-深度优先搜索 - 全栈程序员必看

DS图遍历–深度优先搜索

全栈程序员-用户IM • 2021年6月19日下午6:00 • 未分类

DS图遍历–深度优先搜索

题目描述

给出一个图的邻接矩阵，对图进行深度优先搜索，从顶点0开始

注意：图n个顶点编号从0到n-1

代码框架如下：

DS图遍历--深度优先搜索

输入

第一行输入t，表示有t个测试实例

第二行输入n，表示第1个图有n个结点

第三行起，每行输入邻接矩阵的一行，以此类推输入n行

第i个结点与其他结点如果相连则为1，无连接则为0，数据之间用空格隔开

以此类推输入下一个示例

输出

每行输出一个图的深度优先搜索结果，结点编号之间用空格隔开

样例输入

0 0 1 1

1 1 0 1

1 1 1 0

0 0 0 1 1

0 0 1 0 0

0 1 0 1 1

1 0 1 0 0

样例输出

0 2 1 3

0 3 2 1 4

#include<iostream>
#include<string>
using namespace std;
const int MaxLen = 20;
class Map {
private:
    bool vist[MaxLen];
    int matrix[MaxLen][MaxLen];
    int vexnum;
    void DFS(int v);
public:
    void setmatrix(int vnum, int mx[MaxLen][MaxLen]);
    void DFSTraverse();
};
void Map::setmatrix(int vnum, int mx[MaxLen][MaxLen]){
    int i, j;
    vexnum = vnum;
    for (i = 0; i < MaxLen; i++)
        for (j = 0; j < MaxLen; j++)
            matrix[i][j] = 0;
    for (i = 0; i < vexnum; i++)
        for (j = 0; j < vexnum; j++)
            matrix[i][j] = mx[i][j];
}
void Map::DFSTraverse(){
    for (int i = 0; i < MaxLen; i++)
        vist[i] = false;
    for (int i = 0; i < vexnum; i++)
        if (!vist[i])
            DFS(i);
}
void Map::DFS(int v){
    int w, i, k;
    cout << v << " ";
    vist[v] = true;
    int *adjvex = new int[vexnum];
    for (i = 0; i < vexnum; i++)
        adjvex[i] = -1;
    k = 0;
    for (i = 0; i < vexnum; i++)
        if (matrix[v][i] == 1)
            adjvex[k++] = i;
    i = 0;
    for (w=adjvex[i]; w >=0;w=adjvex[++i])
    {
        if (!vist[w])
            DFS(w);
    }
    delete[]adjvex;
}
int main(){
    int t;
    cin >> t;
    while (t--){
        int n;
        cin >> n;
        int a[MaxLen][MaxLen];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> a[i][j];
        Map map;
        map.setmatrix(n, a);
        map.DFSTraverse();
        cout << endl;
    }
}