图_邻接矩阵_DFS_BFS

忘是亡心i 2022-08-04 16:54 181阅读 0赞

图（Graph）由顶点的 有穷非空集合 和 顶点之间边的集合 组成。  
表示为：**G（V，E），G：图，V：图G中 顶点的集合，E：图G中 边的集合**  
图的**邻接矩阵**存储结构表述如下：

#define VEX_MAX 100              /*最大顶点数*/
    typedef char Vtype;              /*顶点类型*/
    typedef int Etype;               /*边的类型*/
    typedef struct{
        Vtype vex[VEX_MAX];          /*顶点表*/
        Etype arc[VEX_MAX][VEX_MAX]; /*边表*/
        int Vex_num,Edg_num;         /*顶点数和边数*/
    }Graph;                          /*图的结构体：邻接矩阵表示法*/

**创建无向图**：

void Creatgraph(Graph *g)        /*创建无向图*/
    {
        int i,j,k;
        cout << "创建无向图:" << endl;
        cout << "Please input the Vex_num and Edg_num:" << endl;
        cin >> g->Vex_num >> g->Edg_num;
    
        cout << "输入顶点:" << endl;   /*初始化图结构体中第一个数组：顶点数组*/
        for(i = 0;i < g->Vex_num;i++)
            cin >> g->vex[i];
    
        cout << "输入各边情况:" << endl;/*初始化第二个数组：边数组，两点之间存在边的置为1，无边置为0*/
        for(i = 0;i < g->Vex_num;i++)
            for(j = 0;j < g->Vex_num;j++)
            {
                g->arc[i][j] = 0;
            }
        for(k = 0;k < g->Edg_num;k++)
        {
            cout << "please input the (vi,vi):" << endl;
            cin >> i >> j;
            g->arc[i][j] = 1;
            g->arc[j][i] = g->arc[i][j];
        }
    }

**DFS(Depth\_First\_Search，深度优先遍历)：类似树的前序遍历。**  
初始化时，图中各顶点均未被访问，从图中某个顶点(设为V0)出发，访问V0,然后搜索V0的一个邻接点Vi,若Vi未被访问，则访问之，再搜索Vi的一个邻接点(深度优先)  
若某顶点的邻接点全部访问完毕，则回溯(Backtracking)到它的上一顶点，然后再从此顶点又按深度优先的方法搜索下去，…，直到能访问的顶点都访问完毕为止。  
代码如下：

int visit[VEX_MAX];   /*visit数组由两个函数公有，需要放在外部*/
                         /*visit数组，标记该点是否被访问，已访问标1，未访问标0*/
    void dfs(Graph *g,int i) /*DFS递归算法*/
    {
        int j;
        cout << "被访问的点:" << i << ' ' << g->vex[i] << endl;
        visit[i] = 1;
        for(j = 0;j < g->Vex_num;j++)
        {
            if(g->arc[i][j] != 0 && visit[j] == 0)
                dfs(g,j);
        }
    }
    
    void DFS(Graph *g)   /*DFS遍历操作*/
    {
        int i;
        //int visit[g->Vex_num]; // 容易犯错的地方
        for(i = 0;i < g->Vex_num;i++)
            visit[i] = 0;
        for(i = 0;i < g->Vex_num;i++)
        {
            if(visit[i] == 0) /*若未被访问，进行搜索*/
                dfs(g,i);
        }
    }

**BFS(Breadth\_First\_Search，广度优先遍历):类似树的按层次遍历。**  
初始时，图中各顶点均未被访问，从图中某顶点(V0)出发，访问V0,并依次访问V0的各邻接点(广度优先)。  
然后，分别从这些被访问过的顶点出发，扔仍按照广度优先的策略搜索其它顶点,….,直到能访问的顶点都访问完毕为止。  
代码如下：

int visit2[VEX_MAX];
    void bfs(Graph *g,int i)   /*BFS递归算法*/
    {
        int j,k;
        cout << "被访问的点:" << i << ' ' << g->vex[i] << endl;
        visit2[i] = 1;     /*已访问过的赋1*/
        queue<int> q;      /*定义一个队列q*/
        q.push(i);         /*将传递进来的值i入栈*/
        while(!q.empty())  /*若队列非空，q.empty()函数判定队列是否为空，为空则返回真*/
        {
            j = q.front(); /*返回队列头部数据，赋给j*/
            q.pop();       /*将队列中头部数据出队列*/
            for(k = 0;k < g->Vex_num;k++)
            {
                if(visit2[k] == 0 && g->arc[j][k] != 0)
                {
                    cout << "被访问的点:" << k << ' ' << g->vex[k] << endl;
                    visit2[k] = 1;
                    q.push(k);
                }
            }
        }
    
    }
    void BFS(Graph *g)    /*BFS遍历操作，和DFS遍历操作类似*/
    {
        int i;
        for(i = 0;i < g->Vex_num;i++)
            visit2[i] = 0;
        for(i = 0;i < g->Vex_num;i++)
        {
            if(visit2[i] == 0)
                bfs(g,i);
        }
    }

总代码如下：

#include <iostream>
    #include <queue>
    
    using namespace std;
    
    #define VEX_MAX 100              /*最大顶点数*/
    typedef char Vtype;              /*顶点类型*/
    typedef int Etype;               /*边的类型*/
    typedef struct{
        Vtype vex[VEX_MAX];          /*顶点表*/
        Etype arc[VEX_MAX][VEX_MAX]; /*边表*/
        int Vex_num,Edg_num;         /*顶点数和边数*/
    }Graph;                          /*图的结构体：邻接矩阵表示法*/
    /*******************************************************************/
    void Creatgraph(Graph *g)        /*创建无向图*/
    {
        int i,j,k;
        cout << "创建无向图:" << endl;
        cout << "Please input the Vex_num and Edg_num:" << endl;
        cin >> g->Vex_num >> g->Edg_num;
    
        cout << "输入顶点:" << endl;       /*初始化图结构体中第一个数组：顶点数组*/
        for(i = 0;i < g->Vex_num;i++)
            cin >> g->vex[i];
    
        cout << "输入各边情况:" << endl;   /*初始化第二个数组：边数组，两点之间存在边的置为1，无边置为0*/
        for(i = 0;i < g->Vex_num;i++)
            for(j = 0;j < g->Vex_num;j++)
            {
                g->arc[i][j] = 0;
            }
        for(k = 0;k < g->Edg_num;k++)
        {
            cout << "please input the (vi,vi):" << endl;
            cin >> i >> j;
            g->arc[i][j] = 1;
            g->arc[j][i] = g->arc[i][j];
        }
    }
    
    void Printarc(Graph *g)    /*输出顶点数组and邻接矩阵*/
    {
        int i,j;
        cout << "The vex[]:" << endl;
        for(i = 0;i < g->Vex_num;i++)
            cout << g->vex[i] << ' ';
        cout << '\n';
        cout << "The arc[][]:" << endl;
        for(i = 0;i < g->Vex_num;i++)
        {
            for(j = 0;j < g->Vex_num;j++)
            {
                cout << g->arc[i][j] << ' ';
            }
            cout << '\n';
        }
        cout << '\n';
    }
    /*******************************************************************/
    /*DFS(Depth_First_Search)：类似树的前序遍历。*/
    int visit[VEX_MAX];   /*visit数组由两个函数公有，需要放在外部*/
                         /*visit数组，标记该点是否被访问，已访问标1，未访问标0*/
    void dfs(Graph *g,int i) /*DFS递归算法*/
    {
        int j;
        cout << "被访问的点:" << i << ' ' << g->vex[i] << endl;
        visit[i] = 1;
        for(j = 0;j < g->Vex_num;j++)
        {
            if(g->arc[i][j] != 0 && visit[j] == 0)
                dfs(g,j);
        }
    }
    
    void DFS(Graph *g)   /*DFS遍历操作*/
    {
        int i;
        //int visit[g->Vex_num];
        for(i = 0;i < g->Vex_num;i++)
            visit[i] = 0;
        for(i = 0;i < g->Vex_num;i++)
        {
            if(visit[i] == 0) /*若未被访问，进行搜索*/
                dfs(g,i);
        }
    }
    /*******************************************************************/
    /*BFS(Breadth_First_Search):类似树的按层次遍历。*/
    int visit2[VEX_MAX];
    void bfs(Graph *g,int i)   /*BFS递归算法*/
    {
        int j,k;
        cout << "被访问的点:" << i << ' ' << g->vex[i] << endl;
        visit2[i] = 1;     /*已访问过的赋1*/
        queue<int> q;      /*定义一个队列q*/
        q.push(i);         /*将传递进来的值i入栈*/
        while(!q.empty())  /*若队列非空，q.empty()函数判定队列是否为空，为空则返回真*/
        {
            j = q.front(); /*返回队列头部数据，赋给j*/
            q.pop();       /*将队列中头部数据出队列*/
            for(k = 0;k < g->Vex_num;k++)
            {
                if(visit2[k] == 0 && g->arc[j][k] != 0)
                {
                    cout << "被访问的点:" << k << ' ' << g->vex[k] << endl;
                    visit2[k] = 1;
                    q.push(k);
                }
            }
        }
    
    }
    void BFS(Graph *g)    /*BFS遍历操作，和DFS遍历操作类似*/
    {
        int i;
        for(i = 0;i < g->Vex_num;i++)
            visit2[i] = 0;
        for(i = 0;i < g->Vex_num;i++)
        {
            if(visit2[i] == 0)
                bfs(g,i);
        }
    }
    /*******************************************************************/
    int main()
    {
        Graph *g;
        g = new(Graph);
        Creatgraph(g);
        Printarc(g);
        cout << "DFS:" << endl;
        DFS(g);
        cout << "BFS:" << endl;
        BFS(g);
        delete g;  /*注意：new和delete不需要头文件，它不同于malloc和free*/
        return 0;
    }

结果如下：  
![这里写图片描述][20150523214927520]  
![这里写图片描述][20150523214953369]  
/*点滴积累，我的一小步O(∩\_∩)O~*/

[20150523214927520]: /images/20220805/430a213df4d84808978c32b7da2c6f48.png
[20150523214953369]: /images/20220805/5482b9912b62445d88320407fd7e5e2b.png