【数据结构】第6章图图的存储、DFS、BFS、关键路径

末蓝、 2022-11-29 05:54 143阅读 0赞

【图的存储、DFS、BFS、[关键路径][Link 1]】

--------------------

## 1、图的邻接矩阵存储 ##

#include <bits/stdc++.h>
    using namespace std;
    typedef int Status;
    #define OK 1;
    
    //----图的邻接矩阵储存表示----
    #define MaxInt 32767                        //表示极大值
    #define MVNum 100                           //最大顶点数
    typedef char VerTexType;                    //假设顶点的数据类型为字符型
    typedef int ArcType;                        //假设边的权值类型为整形
    int v1, v2, w;
    
    typedef struct 
    {
        
        VerTexType vexs[MVNum];                 //顶点表
        ArcType arcs[MVNum][MVNum];             //邻接矩阵
        int vexnum, arcnum;                     //图当前的点数和边数
    }AMGragh;                                   //邻接矩阵（Adjacency Matric）
    
    AMGragh G;
    
    Status LocateVex(AMGragh G, int v)         //返回顶点v在图G中的位置
    {
        
        for(int i = 0; i < G.vexnum; i++)
            if(v == G.vexs[i])
                return i;
    }
    
    Status CreateUDN(AMGragh &G)
    {
        //采用邻接矩阵表示法，创建无向图G
        cin>>G.vexnum>>G.arcnum;                //输入总顶点数，总边数
        for(int i = 0; i < G.vexnum; i++)
            cin>>G.vexs[i];                     //依次输入点的信息
        for(int i = 0; i <G.vexnum; i++)        //初始化邻接矩阵，边的权值均置为极大值MaxInt
            for(int j = 0; j <G.vexnum; j++)    
                G.arcs[i][j] = MaxInt;
        for(int k = 0; k < G.arcnum; k++)       //构造邻接矩阵
        {
        
            cin>>v1>>v2>>w;                     //输入一条边依附的顶点和权值
            int i = LocateVex(G, v1);           //确定v1和v2在G中的位置，即顶点数组的下标
            int j = LocateVex(G, v2);
            G.arcs[i][j] = w;                   //边<v1, v2>的权值置为w
            G.arcs[j][i] = w;                   //边<v1, v2>的对称边<v2, v1>的权值也置为w
        }
        return OK;
    }

## 2、图的邻接表存储 ##

#include <bits/stdc++.h>
    using namespace std;
    typedef int Status;
    #define OK 1;
    
    //-----图的邻接表的存储表示-----
    #define MaxInt 32767                        //表示极大值
    #define MVNum 100                           //最大顶点数
    typedef char VerTexType;                    //假设顶点的数据类型为字符型
    typedef int OtherInfo;                      //假设和边相关的信息的数据类型为整形
    int v1, v2, w;
    
    typedef struct ArcNode                      //边结点                    
    {
        
        int adjvex;                             //该边所指向的结点的位置
        struct ArcNode *nextarc;                //指向下一条边的指针
        OtherInfo info;                         //和边相关的其他信息
    }ArcNode;
    
    ArcNode *p1, *p2;
    
    typedef struct VNode                        //顶点信息
    {
        
        VerTexType data;                        //数据域，存放顶点vi的名称或其他有关信息
        ArcNode *firstarc;                      //指向第一条依附该顶点的边的指针
    }VNode, AdjList[MVNum];                     //AdjList表示邻接表的类型
    
    typedef struct 
    {
        
        AdjList vertices;
        int vexnum, arcnum;                     //图当前的顶点数和边数
    }ALGragh;                                   //邻接表（Adjacency List）
    
    ALGragh G;
    Status LocateVex(ALGragh G, int v)         //返回顶点v在图G中的位置
    {
        
        for(int i = 0; i < G.vexnum; i++)
            if(v1 == G.vertices[i].data)
                return i;
    }
    
    Status CreateUDG(ALGragh &G)
    {
        
        cin>>G.vexnum>>G.arcnum;                //输入总顶点数，总边数
        for(int i = 0; i < G.vexnum; i++)
        {
        
            cin>>G.vertices[i].data;            //输入顶点值
            G.vertices[i].firstarc = NULL;      //初始化标头结点的指针域为空
        }
        for(int k = 0; k < G.arcnum; k++)
        {
        
            cin>>v1>>v2;                        //输入一条边依附的两个顶点
            int i = LocateVex(G, v1);           //确定v1和v2在G中的位置，即顶点在G.vertices中的的序号
            int j = LocateVex(G, v2);
            p1 = new ArcNode;                   //生成一个新的边结点*p1;
            p1->adjvex = j;                     //邻接点序号为j
            p1->nextarc = G.vertices[i].firstarc;
            G.vertices[i].firstarc = p1;        //将新结点*p1插入顶点vj的边表头部
            p2 = new ArcNode;                   //生成另一个对称的新的边结点*p2;
            p2->adjvex = i;                     //邻接点序号为i
            p1->nextarc = G.vertices[j].firstarc;
            G.vertices[j].firstarc = p1;        //将新结点*p2插入顶点vi的边表头部
        }
        return OK;
    }

## 3、有向图的十字链表存储 ##

#include <bits/stdc++.h>
    using namespace std;
    typedef int Status;
    #define OK 1;
    
    //----有向图的十字链表储存表示----
    #define MAX_VERTEX_NUM 20
    typedef char VerTexType;
    typedef int InfoType;
    typedef struct ArcBox
    {
        
        int tailvex, headvex;                   //该弧的头尾和头顶点的位置
        struct ArcBox *hlink, *tlink;            //分别为弧头相同和弧尾相同的链域
        InfoType *info;                         //该弧相关信息的指针
    }ArcBox;
    
    typedef struct VexNode
    {
        
        VerTexType data;
        ArcBox *firstin, *firstout;             //分别指向该顶点的第一项入弧和出弧
    }VexNode;
    
    typedef struct 
    {
        
        VexNode xlist[MAX_VERTEX_NUM];          //表头向量
        int vexnum, arcnum;                     //有向图的当前顶点数和弧数
    }OLGraph;                                   //十字链表（Orthogonal List）

## 4、无向图的邻接多重表存储 ##

#include <bits/stdc++.h>
    using namespace std;
    typedef int Status;
    #define OK 1;
    
    //----无向图的邻接多重表储存表示----
    #define MAX_VERTEX_NUM 20
    typedef char VerTexType;
    typedef int InfoType;
    
    typedef enum
    {
        
        unvisited, visited                     //枚举unvisited是0，visited是1，注意没有分号
    }VisitIf;
    
    typedef struct EBox
    {
        
        VisitIf mark;                           //访问标记
        int ivex, jvex;                         //该边依附的两个顶点的位置
        struct EBox *ilink, *jlink;             //分别指向依附这两个顶点的下一条边
        InfoType *info;                         //该边的信息指针
    }EBox;
    
    typedef struct VexBox
    {
        
        VerTexType data;
        EBox *firstedge;                        //指向第一条依附该顶点的边
    }VexBox;
    
    typedef struct 
    {
        
        VexBox adjmulist[MAX_VERTEX_NUM];
        int vexnum, arcnum;                     //无向图当前的顶点数和边数
    }AMLGraph;                                  //邻接多重表(Adjacency Multilist)

## 5、DFS ##

//----任意图的DFS遍历----
    bool visited[MVNum];                                                    //访问标志数组，其初值为false
    
    void DFS(Graph G, int v)                                     
    {
        //图G的储存类型待定，下面分类讨论
        cout<<v;
        visited[v] = true;                                                  //访问第v个顶点，并置访问标志数组相应分量值为true
        for(int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))     //FirstAdjVex(G, v)表示v的第一个邻接点，NextAdjVex(G, v, w)表示v相对于w的下一个邻接点
            if(!visited[w])                                                 //依次检查v的所有邻接点w，由于不同储存结构此处操作不同，下面函数再具体展开
                DFS(G, w);                                                  //对v的尚未访问的邻接顶点w递归调用DFS
    }
    
    void DFSTraverse(Gragh G)
    {
        //图G的储存类型任意，对非连通图G做深度优先遍历
        for(int v = 0; v < G.vexnum; v++)                                   //访问标志数组初始化
            visited[v] = false;
        for(int v = 0; v < G.vexnum; v++)                                   //循环调用DFS
            if(!visited[v])
                DFS(G, v);                                               //对尚未访问的顶点调用DFS
    }
    
    
    //----邻接矩阵的DFS遍历----
    bool visited[MVNum];                                                    //访问标志数组，其初值为false
    
    void DFS_AM(AMGragh G, int v)               
    {
        //图G为邻接矩阵类型，从第v个顶点出发深度优先搜索遍历图G
        cout<<v;                                                            //访问第v个顶点，并置访问标志数组相应分量值为true
        visited[v] = true;
        for(int w = 0; w < G.vexnum; w++)                                   //依次检查邻接矩阵v所在的行
            if((G.arcs[v][w] != 0) && (!visited[w]))                        //G.arcs[v][w] != 0表示w是v的邻接点，!visited[w]表示未访问到
                DFS_AM(G, w);                                               //递归调用DFS_AM
    }
    
    void DFSTraverse(AMGragh G)
    {
        //图G的储存类型任意，对非连通图G做深度优先遍历
        for(int v = 0; v < G.vexnum; v++)                                   //访问标志数组初始化
            visited[v] = false;
        for(int v = 0; v < G.vexnum; v++)                                   //循环调用DFS
            if(!visited[v])
                DFS_AM(G, v);                                               //对尚未访问的顶点调用DFS
    }
    
    
    //----邻接表的DFS遍历----
    bool visited[MVNum];                                                    //访问标志数组，其初值为false
    
    void DFS_AL(ALGragh G, int v)               
    {
        //图G为邻接表类型，从从第v个顶点出发深度优先搜索遍历图G
        cout<<v;                                                            //访问第v个顶点，并置访问标志数组相应分量值为true
        visited[v] = true;
        ArcNode *p;                                                         
        p = G.vertices[v].firstarc;                                         //p指向v的边链表的第一个边结点
        while(p != NULL)
        {
        
           int w = p->adjvex;                                               //w是v的邻接点
            if(!visited[w])                                                 //如果w未访问
                DFS_AL(G, w);                                               //递归调用DFS_AL
            p = p->nextarc;                                                 //p指向下一个结点
        }
    }
    
    void DFSTraverse(ALGragh G)
    {
        //图G的储存类型任意，对非连通图G做深度优先遍历
        for(int v = 0; v < G.vexnum; v++)                                   //访问标志数组初始化
            visited[v] = false;
        for(int v = 0; v < G.vexnum; v++)                                   //循环调用DFS
            if(!visited[v])
                DFS_AL(G, v);                                                  //对尚未访问的顶点调用DFS
    }

## 6、BFS ##

//----任意图的BFS遍历----
    bool visited[MVNum];                                                    //访问标志数组，其初值为false
    int u;
    void BFS(Gragh G, int v)
    {
        //按广度优先非递归遍历连通图G，图G的储存类型待定，下面分类讨论
        cout<<v;
        visited[v] = true;                                                  //访问第v个顶点，并置访问标志数组相应分量值为true
        InitQueue(Q);                                                       //辅助队列初始化，置空
        EnQueue(Q, v);                                                      //v进队
       int u;
        while(!QueueEmpty(Q))
        {
        
            DeQueue(Q, u);                                                  //队头元素出队并置为u
            for(int w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
                if(!visited[w])                                             //w为u的尚未访问的邻接顶点
                {
        
                    cout<<w;
                    visited[w] = true;                                      //访问w，并置访问标志数组相应分量值为true
                    EnQueue(Q, w);                                          //w进队
                }
        }
    }
    
    //----邻接矩阵的BFS遍历----
    void BFS_AM(AMGragh G, int v)
    {
        //按广度优先非递归遍历连通图G
        cout<<v;
        visited[v] = true;                                                  //访问第v个顶点，并置访问标志数组相应分量值为true
        InitQueue(Q);                                                       //辅助队列初始化，置空
        EnQueue(Q, v);                                                      //v进队
        while(!QueueEmpty(Q))
        {
        
            u = DeQueue(Q);                                                 //队头元素出队并置为u
            for(int w = 0; w < G.vexnum; w++)
                if((G.arcs[u][w] != 0) && (!visited[w]))                    //G.arcs[v][w] != 0表示w是v的邻接点，!visited[w]表示未访问到                                            //w为u的尚未访问的邻接顶点
                {
        
                    cout<<w;
                    visited[w] = true;                                      //访问w，并置访问标志数组相应分量值为true
                    EnQueue(Q, w);                                          //w进队
                }
        }
    }
    
    //----邻接表的BFS遍历----
    void BFS_AL(ALGragh G, int v)
    {
        //按广度优先非递归遍历连通图G
        cout<<v;
        visited[v] = true;                                                  //访问第v个顶点，并置访问标志数组相应分量值为true
        ArcNode *p;    
        InitQueue(Q);                                                       //辅助队列初始化，置空
        EnQueue(Q, v);                                                      //v进队
        while(!QueueEmpty(Q))
        {
        
            u = DeQueue(Q);                                                 //队头元素出队并置为u
            p = G.vertices[u].firstarc;                                     //p指向v的边链表的第一个边结点
            while(p != NULL)
            {
        
                int w = p->adjvex;                                          //w是v的邻接点
                if(!visited[w])                                             //如果w未访问
                    EnQueue(Q, w);                                          //w入队
                p = p->nextarc;                                             //p指向下一个结点
            }
        }
    }

[Link 1]: https://www.bilibili.com/video/BV1PW41187vc