网站 › 『编程语言区』 › 【c++】【笔记】 <无向图的储存结构以及DFS和BFS>

false_554 发表于 2020-11-21 16:08

【c++】【笔记】 <无向图的储存结构以及DFS和BFS>

这几天把无向图的DFS和BFS练习了一下，目前仅限于实现，对于复杂度还没有进行更深层次的探究~
对于这些笔记，仅仅为记录自己学习情况，有某些地方可能不能很好地说清楚。对于表达不清楚的地方欢迎大家讨论与大佬指正{:1_932:}


先上图的储存结构：
```
//图的定义
template<class T>
struct MatrixGraph {
        int edge_num;        //边数
        int vertex_num;        //顶点数
        int EdgeMatrix;        //邻接矩阵
        T vertex_;        //顶点值(要加下划线，不然重名)
};
```

生成图的代码：
```
template<class T>
MatrixGraph<T> CreatUndigraph(int vertex[]) {//顶点值,vertex储存了数组长度
        MatrixGraph<T> undigraph;
        undigraph.edge_num = 0;//初始化边数
        undigraph.vertex_num = vertex;//初始化顶点数
        int i, j;
        //初始化顶点值
        for (int i = 0; i <= undigraph.vertex_num; i++) {
                undigraph.vertex_ = vertex;
        }
        //初始化矩阵
        for (int i = 1; i <= undigraph.vertex_num; i++) {
                for (int j = i; j <= undigraph.vertex_num; j++) {
                        undigraph.EdgeMatrix = 0;
                        undigraph.EdgeMatrix = 0;
                }
        }
        //修改边矩阵
        while (1) {
                cout << "输入存在边的顶点1（输入0结束）:";
                        cin >> i;
                cout << "输入存在边的顶点2（输入0结束）:";
                        cin >> j;
                if (i == 0 || j == 0) break;//修改边结束
                undigraph.EdgeMatrix = 1;
                undigraph.EdgeMatrix = 1;//对称
                undigraph.edge_num++;//存在边，边数+1
        }
        cout << "创建图成功!" << endl;
        return undigraph;
}
```

逻辑上删除顶点（把顶点值修改为-1）的代码：
```
template<class T>
bool DeleteUndiGrahVex(MatrixGraph<T> &undigraph) {
        int k;
        cout << "请输入你想要删除的节点（编号）：";
        cin >> k;
        if (k > undigraph.vertex_num) {
                cout << "节点不存在！" << endl;
                return false;
        }
        else {
                undigraph.vertex_ = 0;//把待删除节点值变成-1（逻辑上删除，不移动元素）
                for (int i = 1; i <= undigraph.vertex_num; i++) {
                        undigraph.EdgeMatrix = 0;
                        undigraph.EdgeMatrix = 0;//对称矩阵上以k为横、纵坐标的元素置为0
                        undigraph.edge_num--;//边数-1
                }
                undigraph.vertex_num--;//顶点数-1
                return true;
        }
}
```

DFS与DFS的实现：
先建立一个全局数组，记录顶点访问记录：

`int visit;//记录顶点的访问记录，1已访问，0未访问`

DFS：
//DFS入口
template<class T>
void DFSTraverse(MatrixGraph<T>& graph) {
        //把顶点访问状态重置
        for (int i = 1; i <= graph.vertex_num; i++) {
                visit = 0;
        }
        cout << "深度遍历：";
        //把每个未被访问过的顶点作为起点进行深度遍历，避免有顶点没访问到
        for (int i = 1; i <= graph.vertex_num; i++) {
                if (visit != 1 && graph.vertex_!=-1) {//如果顶点未被访问且顶点在逻辑上不存在
                        DFS(graph, i);
                }
        }
}

template<class T>
void DFS(MatrixGraph<T> &graph, int vertex_i) {        //顶点下标
        cout <<vertex_i<< "\t";//访问v节点
        visit = 1;//标记已访问
        for (int w = 1; w <= graph.vertex_num; w++) {
                if (graph.EdgeMatrix == 1 && visit != 1 && graph.vertex_ != -1) DFS(graph, w);        //访问与v节点相连的的相邻节点（逻辑上没被删除的节点）
       }
}

BFS：
```
//BFS入口
template<class T>
void BFSTraverse(MatrixGraph<T> &graph) {
        //把顶点访问状态重置
        for (int i = 1; i <= graph.vertex_num; i++) {
                visit = 0;
        }
        cout << "广度遍历：";
        queue<T> queue = InitQueue<T>(30);        //初始化队列
        //把每个未被访问过的顶点作为起点进行广度遍历，避免有顶点没访问到
        for (int i = 1; i <= graph.vertex_num; i++) {
                if (visit != 1 && graph.vertex_!=-1) {        //未被访问且逻辑上存在（没被删除）
                        QueueIn(queue, i);//        先把一个元素入队,储存的是顶点在数组的下标
                        visit = 1;//只要进入队列就相当于访问了
                        BFS(graph, i, queue);
                }
        }

}

template<class T>
void BFS(MatrixGraph<T> &graph, int vertex_i,queue<T> &queue) {        //顶点下标
        while (!QueueIsEmpty<T>(queue)) {
                int k = 0;
                QueueOut(queue, k);
                cout << k << "\t";//先访问该节点
                //再将与该节点存在边且未被访问的节点入队
                for (int i = 1; i <= graph.vertex_num; i++) {
                        if (graph.EdgeMatrix != 0 && visit != 1 && graph.vertex_!=-1) {//graph.vertex_!=-1即是该节点在逻辑上不存在（被删除了）
                                QueueIn(queue, i);
                                visit = 1;//只要进入队列就相当于访问了
                        }
                }
        }
}
```

下面是程序调用：
```
int main(){
                int a[] = { 10,2,5,3,4,6,8,11,34,1,1};
                MatrixGraph<int> undigraph = CreatUndigraph<int>(a);
                DFSTraverse<int>(undigraph);
                cout << endl;
                BFSTraverse<int>(undigraph);
}
```

生成的图：


程序调试结果：


写在最后：原本敲了半个多小时的代码思路，但是一不小心点了别的按钮，再返回编辑的时候提示恢复数据，但是恢复的竟然只有几行数据，这...编辑器不讲武德。:curse:

鸭子咯咯哒~ 发表于 2020-11-21 17:00

楼主用的啥编辑器

gms 发表于 2020-11-21 17:12

感谢分享，刚好在学图

无名氏wyw 发表于 2020-11-21 17:16

仅限于遍历的话，链式前向星除了删点慢点以外再怎么样都比邻接矩阵适用范围广吧？

false_554 发表于 2020-11-21 17:33

无名氏wyw 发表于 2020-11-21 17:16
仅限于遍历的话，链式前向星除了删点慢点以外再怎么样都比邻接矩阵适用范围广吧？

你想说用邻接表储存吗，如果是的话目前还没复习到~
还有“链式前向星”这里没看懂{:1_893:}

false_554 发表于 2020-11-21 17:35

鸭子咯咯哒~ 发表于 2020-11-21 17:00
楼主用的啥编辑器

vs2017，不过我就用来敲c++，大一被老师带入的坑

false_554 发表于 2020-11-21 17:36

gms 发表于 2020-11-21 17:12
感谢分享，刚好在学图

{:1_893:}共勉哈~

无名氏wyw 发表于 2020-11-21 19:45

false_554 发表于 2020-11-21 17:33
你想说用邻接表储存吗，如果是的话目前还没复习到~
还有“链式前向星”这里没看懂

//图的定义
template<class T>
struct MatrixGraph {
    int edge_num;   //边数
    int vertex_num; //顶点数
    int EdgeMatrix;   //邻接矩阵
    T vertex_; //顶点值(要加下划线，不然重名)
};
你的代码里不就是邻接矩阵么。。这还要复习
至于链式前向星，你考虑下上万个点能不能用邻接表存就知道它的重要性了

false_554 发表于 2020-11-22 07:56

无名氏wyw 发表于 2020-11-21 19:45
//图的定义
template
struct MatrixGraph {


我代码里的是邻接矩阵，不是邻接链表额

false_554 发表于 2020-11-22 08:02

无名氏wyw 发表于 2020-11-21 19:45
//图的定义
template
struct MatrixGraph {


刚才百度了一下，发现你说的链式前向星是介乎与邻接矩阵和邻接链表之间的数据结构:keai
是一个我没听说过的新东西{:1_932:}

查看完整版本: 【c++】【笔记】 <无向图的储存结构以及DFS和BFS>