图的深度优先遍历和广度优先遍历代码实现

今天药忘吃喽~ 2022-08-09 18:58 265阅读 0赞

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <queue>
    
    using namespace std;
    
    typedef char TypeData; /* 数据类型 */
    #define MAXVEX 100   /* 最大顶点数 */
    #define INFINITY 65535   /* 用65535代表 正无穷 */
    
    /* 存储采用邻接矩阵 */
    typedef struct stGraph
    {
        TypeData vexs[MAXVEX];    /* 定点表 */
        int arc[MAXVEX][MAXVEX];  /* 邻接矩阵，可看作边表 */
        int numVertexes, numEdges;/* 图中当前的顶点数和边数 */
    }MGraph;
    
    
    /* 建立无向网图邻接矩阵表示 */
    void createMGraph(MGraph* G);
    
    /* 邻接矩阵的深度优先递归算法，针对每一个定点进行深度优先遍历 */
    void DFS(MGraph* G, int i);
    void DFSTraverse(MGraph* G);
    
    /* 邻接矩阵的广度优先遍历 */
    void BFSTraverse(MGraph* G);
    
    
    
    /* 建立无向网图邻接矩阵表示 */
    void createMGraph(MGraph* G)
    {
        int i = 0, j  = 0, k = 0, w = 0;
    
        cout << "请输入定点数和边数: ";
        cin >> G->numVertexes >> G->numEdges;
    
        /* 读入定点信息，建立定点表 */
        cout << "请输入图的节点" << endl;
        for(i = 0; i < G->numVertexes; i++)
        {
            cin >> G->vexs[i];
        }
    
        /* 初始化邻接矩阵 */
        for(i = 0; i < G->numVertexes; i++)
        {
            for(j = 0; j < G->numVertexes; j++)
            {
                G->arc[i][j] = INFINITY;
            }
        }
    
        /* 读入numEdges边信息 */
        for(k = 0; k < G->numEdges; k++)
        {
            cout << "输入边(vi,vj)上的下标，i,j和权值w" << endl;
            cin >> i >> j >> w;
            G->arc[i][j] = w;
    
            /* 因为是无向图，矩阵对称 */
            G->arc[j][i] = w;
        }
    }
    
    /* 邻接矩阵的深度优先遍历和广度优先遍历所用辅助数组
       记录图中的节点是否被访问过 */
    int visited[MAXVEX] = {0};
    
    /* 邻接矩阵的深度优先递归算法，针对每一个定点进行深度优先遍历 */
    void DFS(MGraph* G, int i)
    {
        int j = 0;
        visited[i] = 1;
    
        /* 打印定点的信息 */
        cout << G->vexs[i] << " ";
    
        for(j = 0; j < G->numVertexes; j++)
        {
            if(G->arc[i][j] != 65535 && visited[j] == 0 )
            {
                DFS(G,j);
            }
        }
    }
    
    void DFSTraverse(MGraph* G)
    {
        int i = 0;
    
        /* 把每一个定点都设为未访问过 */
        for(i = 0; i < G->numVertexes; i++)
        {
            visited[i] = 0;
        }
    
        /* 对未访问过的定点调用DFS */
        for(i = 0; i < G->numVertexes; i++)
        {
            if(visited[i] == 0)
            {
                DFS(G,i);
            }
        }
    }
    
    /* 邻接矩阵的广度优先遍历 */
    void BFSTraverse(MGraph* G)
    {
        int i = 0, j = 0;
        queue<int> myqueue;
    
        /* 初始化，把每一个定点都设为未访问过 */
        for(i = 0; i < G->numVertexes; i++)
        {
            visited[i] = 0;
        }
    
        /* 对每一个定点做循环 */
        for(i = 0; i < G->numVertexes; i++)
        {
            /* 如果节点没有被访问过 */
            if(visited[i] == 0)
            {
                /* 该节点设置为已经被访问 */
                visited[i] = 1;
    
                /* 打印出该节点,并把该节点入队列 */
                cout << G->vexs[i] << " ";
                myqueue.push(i);
    
                /* 若当前的队列不为空 */
                while(!myqueue.empty())
                {
                    i = myqueue.front();
                    myqueue.pop();
    
                    for(j = 0; j < G->numVertexes; j++)
                    {
                        /* 判断其他定点若与当前的定点存在边且未访问过 */
                        if(G->arc[i][j] != 65536 && visited[j] == 0)
                        {
                            visited[j] = 1;
                            cout << G->vexs[j] << " ";
                            myqueue.push(j);
                        }
                    }
                }
            }
        }
    
    }
    
    
    int main(void)
    {
        MGraph* pGraph = new MGraph;
        int i = 0, j = 0;
    
        /* 创建一个图 */
        createMGraph(pGraph);
    
        /* 深度优先遍历 */
      //  DFSTraverse(pGraph);
    
        /* 广度优先遍历 */
        BFSTraverse(pGraph);
    
        delete pGraph;
    
        return 0;
    }