2022 年考研数据结构_6 图

你的名字 2022-12-31 05:23 238阅读 0赞

https://gitee.com/fakerlove/Data-Structure

### 文章目录 ###

*  6. 图
 *   *  6.1 概念
     *  6.2 图的存储
     *   *  6.2.1 邻接表
         *  6.2.2 邻接矩阵
     *  6.3 图的遍历
     *   *  6.3.1 深度优先遍历
         *  6.3.2 广度优先遍历
     *  6.4 应用
     *   *  6.4.1 最小生成树
         *   *  1) Prim 算法 (普里姆算法)
             *   *  样例1
                 *  样例2
                 *  样例3
             *  2) 克鲁斯卡尔算法
         *  6.4.2 最短路径
         *   *  迪杰特斯拉算法
             *  Floyd 算法
         *  6.4.3 拓扑排序,关键路径
         *   *  \*\*1. AOV网络\*\*
             *  \*\*2. 拓扑排序\*\*
             *   *  1) 概念
                 *  2) 算法步骤
                 *  3) 算法图解
                 *  4) 代码
                 *  5) 应用
             *  \*\*3. AOE网络\*\*
             *  \*\*4. 有向无环图——描述表达式\*\*

# 6. 图 #

## 6.1 概念 ##

如果路径上的各顶点均不互相重复，称这样的路径为**简单路径**。如果路径上的第一个顶点与最后一个顶点重合，这样的路径称为**回路**(cycle)或**环**或**圈**。

回路不是简单路径

> 无向图连通至少需要 n-1
> 
> 有向图连通至少需要n
> 
> 无向图任何情况下连通至少 (n-1)(n-2)/2+1
> 
> 有向图任何情况下连通

## 6.2 图的存储 ##

### 6.2.1 邻接表 ###

### 6.2.2 邻接矩阵 ###

## 6.3 图的遍历 ##

### 6.3.1 深度优先遍历 ###

### 6.3.2 广度优先遍历 ###

## 6.4 应用 ##

通过前面的学习，对于含有 n 个顶点的连通图来说可能包含有多种生成树，例如图 1 所示：

![img][]  
图 1 连通图的生成树

图 1 中的连通图和它相对应的生成树，可以用于解决实际生活中的问题：假设A、B、C 和 D 为 4 座城市，为了方便生产生活，要为这 4 座城市建立通信。对于 4 个城市来讲，本着节约经费的原则，只需要建立 3 个通信线路即可，就如图 1（b）中的任意一种方式。

在具体选择采用（b）中哪一种方式时，需要综合考虑城市之间间隔的距离，建设通信线路的难度等各种因素，将这些因素综合起来用一个数值表示，当作这条线路的权值。

![img][img 1]  
图 2 无向网

假设通过综合分析，城市之间的权值如图 2（a）所示，对于（b）的方案中，选择权值总和为 7 的两种方案最节约经费。

这就是本节要讨论的最小生成树的问题，简单得理解就是给定一个带有权值的连通图（连通网），如何从众多的生成树中筛选出权值总和最小的生成树，即为该图的最小生成树。

### 6.4.1 最小生成树 ###

#### 1) Prim 算法 (普里姆算法) ####

普里姆算法在找最小生成树时，将顶点分为两类，一类是在查找的过程中已经包含在树中的（假设为 A 类），剩下的是另一类（假设为 B 类）。

*  对于给定的连通网，起始状态全部顶点都归为 B 类。
 *  在找最小生成树时，选定任意一个顶点作为起始点，并将之从 B 类移至 A 类；
 *  然后找出 B 类中到 A 类中的顶点之间权值最小的顶点，将之从 B 类移至 A 类，如此重复，直到 B 类中没有顶点为止。
 *  所走过的顶点和边就是该连通图的最小生成树。

##### 样例1 #####

例如，通过普里姆算法查找的最小生成树的步骤为：

假如从顶点A出发，顶点 B、C、D 到顶点 A 的权值分别为 2、4、2，所以，对于顶点 A 来说，顶点 B 和顶点 D 到 A 的权值最小，假设先找到的顶点 B：

![img][img 2]

继续分析顶点 C 和 D，顶点 C 到 B 的权值为 3，到 A 的权值为 4；顶点 D 到 A 的权值为 2，到 B 的权值为无穷大（如果之间没有直接通路，设定权值为无穷大）。所以顶点 D 到 A 的权值最小：

![img][img 3]

最后，只剩下顶点 C，到 A 的权值为 4，到 B 的权值和到 D 的权值一样大，为 3。所以该连通图有两个最小生成树：

![img][img 4]

具体实现代码为：

#include <stdio.h>
    #include <stdlib.h>
    #define VertexType int
    #define VRType int
    #define MAX_VERtEX_NUM 20
    #define InfoType char   
    #define INFINITY 65535
    typedef struct {
        VRType adj;                             //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
        InfoType * info;                        //弧额外含有的信息指针
    }ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];
    
    typedef struct {
        VertexType vexs[MAX_VERtEX_NUM];        //存储图中顶点数据
        AdjMatrix arcs;                         //二维数组，记录顶点之间的关系
        int vexnum,arcnum;                      //记录图的顶点数和弧（边）数
    }MGraph;
    
    //根据顶点本身数据，判断出顶点在二维数组中的位置
    int LocateVex(MGraph G,VertexType v){
        int i=0;
        //遍历一维数组，找到变量v
        for (; i<G.vexnum; i++) {
            if (G.vexs[i]==v) {
                return i;
            }
        }
        return -1;
    }
    //构造无向网
    void CreateUDN(MGraph* G){
        scanf("%d,%d",&(G->vexnum),&(G->arcnum));
        for (int i=0; i<G->vexnum; i++) {
            scanf("%d",&(G->vexs[i]));
        }
        for (int i=0; i<G->vexnum; i++) {
            for (int j=0; j<G->vexnum; j++) {
                G->arcs[i][j].adj=INFINITY;
                G->arcs[i][j].info=NULL;
            }
        }
        for (int i=0; i<G->arcnum; i++) {
            int v1,v2,w;
            scanf("%d,%d,%d",&v1,&v2,&w);
            int m=LocateVex(*G, v1);
            int n=LocateVex(*G, v2);
            if (m==-1 ||n==-1) {
                printf("no this vertex\n");
                return;
            }
            G->arcs[n][m].adj=w;
            G->arcs[m][n].adj=w;
        }
    }
    
    //辅助数组，用于每次筛选出权值最小的边的邻接点
    typedef struct {
        VertexType adjvex;//记录权值最小的边的起始点
        VRType lowcost;//记录该边的权值
    }closedge[MAX_VERtEX_NUM];
    closedge theclose;//创建一个全局数组，因为每个函数中都会使用到
    //在辅助数组中找出权值最小的边的数组下标，就可以间接找到此边的终点顶点。
    int minimun(MGraph G,closedge close){
        int min=INFINITY;
        int min_i=-1;
        for (int i=0; i<G.vexnum; i++) {
            //权值为0，说明顶点已经归入最小生成树中；然后每次和min变量进行比较，最后找出最小的。
            if (close[i].lowcost>0 && close[i].lowcost < min) {
                min=close[i].lowcost;
                min_i=i;
            }
        }
        //返回最小权值所在的数组下标
        return min_i;
    }
    //普里姆算法函数，G为无向网，u为在网中选择的任意顶点作为起始点
    void miniSpanTreePrim(MGraph G,VertexType u){
        //找到该起始点在顶点数组中的位置下标
        int k=LocateVex(G, u);
        //首先将与该起始点相关的所有边的信息：边的起始点和权值，存入辅助数组中相应的位置，例如（1，2）边，adjvex为0，lowcost为6，存入theclose[1]中，辅助数组的下标表示该边的顶点2
        for (int i=0; i<G.vexnum; i++) {
            if (i !=k) {
                theclose[i].adjvex=k;
                theclose[i].lowcost=G.arcs[k][i].adj;
            }
        }
        //由于起始点已经归为最小生成树，所以辅助数组对应位置的权值为0，这样，遍历时就不会被选中
        theclose[k].lowcost=0;
        //选择下一个点，并更新辅助数组中的信息
        for (int i=1; i<G.vexnum; i++) {
            //找出权值最小的边所在数组下标
            k=minimun(G, theclose);
            //输出选择的路径
            printf("v%d v%d\n",G.vexs[theclose[k].adjvex],G.vexs[k]);
            //归入最小生成树的顶点的辅助数组中的权值设为0
            theclose[k].lowcost=0;
            //信息辅助数组中存储的信息，由于此时树中新加入了一个顶点，需要判断，由此顶点出发，到达其它各顶点的权值是否比之前记录的权值还要小，如果还小，则更新
            for (int j=0; j<G.vexnum; j++) {
                if (G.arcs[k][j].adj<theclose[j].lowcost) {
                    theclose[j].adjvex=k;
                    theclose[j].lowcost=G.arcs[k][j].adj;
                }
            }
        }
        printf("\n");
    }
    
    int main(){
        MGraph G;
        CreateUDN(&G);
        miniSpanTreePrim(G, 1);
    }

##### 样例2 #####

![img][img 5]

使用普里姆算法找图 3 所示无向网的最小生成树的测试数据为：

6,10
    1
    2
    3
    4
    5
    6
    1,2,6
    1,3,1
    1,4,5
    2,3,5
    2,5,3
    3,4,5
    3,5,6
    3,6,4
    4,6,2
    5,6,6
    运行结果为：
    v1 v3
    v3 v6
    v6 v4
    v3 v2
    v2 v5

##### 样例3 #####

![format_png][]

普里姆算法的运行效率只与连通网中包含的顶点数相关，而和网所含的边数无关。所以普里姆算法适合于解决边稠密的网，该算法运行的

时间复杂度

为：`O(n2)`

#### 2) 克鲁斯卡尔算法 ####

> 1.  将图中的所有边都去掉；
> 2.  将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环 ；
> 3.  重复上一步直到连接所有顶点，此时就生成了最小生成树。这是一种贪心策略。

#include <bits/stdc++.h>
    using namespace std;
    
    struct edge//纪录边的信息
    {
        int start;
        int end;
        int weight;
    };
    
    //克鲁斯卡尔算法
    void Kruskal(int data[10][3])
    {
        int data2[10][2] = {0};
        multiset<int> st1;
        vector<edge> vec;//存储所有边的信息
        edge temp;
        for (int j = 0; j < 10; ++j)//初始化所有边的信息
        {
            temp.start = data[j][0];
            temp.end = data[j][1];
            temp.weight = data[j][2];
            vec.push_back(temp);
        }
        //按权值排序
        sort(vec.begin(), vec.end(), [](const edge &e1, const edge &e2) -> bool
        { 
            return e1.weight < e2.weight ? true : false ;
        });
        for (int j = 0; j < 10; ++j)
        {
            //st1存放的是已经加入的边用于判断是否会形成环（如果起点和终点都在st1中则加入该边会形成环）
            if (st1.find(vec[j].start) != st1.end() && st1.find(vec[j].end) != st1.end())
                continue;
            else
            {
                data2[j][0] = vec[j].start;//data2存放的是组成最小生成树的边
                data2[j][1] = vec[j].end;
                st1.insert(vec[j].start);
                st1.insert(vec[j].end);
            }
        }
        for (int j = 0; j < 10; ++j)
        {
            if (data2[j][0] != 0)
                cout << data2[j][0] << " " << data2[j][1] << endl;
        }
    }
    
    int main(int argc, char const *argv[])
    {
        int data[10][3] = //所有边的信息
        {
            {1,2,6},{1,6,12},
            {1,5,10},{2,3,3},
            {2,4,5},{2,6,8},
            {3,4,7},{4,6,11},
            {4,5,9},{5,6,16}
        };
        Kruskal(data);
        return 0;
    }

![942d5ed3b1a8d8768fd1b5382f811eac.gif][]

### 6.4.2 最短路径 ###

#### 迪杰特斯拉算法 ####

> 1.  找出最便宜的顶点，即距离出发顶点距离最近的顶点，作为新的出发顶点
> 2.  更新该顶点的邻居的开销
> 3.  重复（1）（2）步骤，直到对每个顶点都做了此操作
> 4.  计算最终路径

用Dijkstra算法求A到图中各点的最短路径

![img][img 6]

Dijkstral算法伪代码如下：

n次循环至n个顶点全部遍历：

1.1从权值数组中找到权值最小的，标记该边端点k

1.2打印该路径及权值

2.1如果存在经过顶点k到顶点i的边比v->i的权值小

2.2更新权值数组及对应路径

源码：

#include<iostream>
    #include<iomanip>//控制格式
    #include<string>
    
    
    #define INF 0x3f3f3f3f//定义无穷大
    using namespace std;
    
    
    #define vertexNum 5//源点数
    int G[vertexNum][vertexNum];//邻接矩阵
    string vertex[]={"A","B","C","D","E"};//源点字符串组
    void CreateMGraph()
    {
      for(int i=0;i<vertexNum;i++)
        for(int j=0;j<vertexNum;j++)
      {
        G[i][j]=INF;
      }
      G[0][1]=10;G[0][3]=30;G[0][4]=100;
      G[1][2]=50;
      G[2][4]=10;
      G[3][2]=20;G[3][4]=60;
    }
    void Dijkstra(int v)
    {
      int dist[vertexNum],i,num,k,min;//dist为权值存储数组
      string path[vertexNum];
      int s[vertexNum]={0};//初始化标记数组
      cout<<"初始权值数组和路径字符串数组:"<<endl;
      for(i=0;i<vertexNum;i++)
      {
        dist[i]=G[v][i];
        path[i]=vertex[v]+"-->"+vertex[i];
        cout<<path[i]<<" ";
        if(dist[i]!=INF) cout<<dist[i]<<endl;
        else cout<<"∞"<<endl;
      }
      s[v]=1;//标记第一个访问点
      dist[v]=0;
      num=1;//计数器
      cout<<"打印源点A到各点的最短路径及其权值和："<<endl;
      while(num<=vertexNum)//当不取等号时将不会获得A到自身的路径
      {
        min=INF;
        for(k=0,i=0;i<vertexNum;i++)//查找最小值
          {
          if(s[i]==0&&(dist[i]<min)) {min=dist[i];k=i;}
          }
        cout<<path[k]<<" "<<dist[k]<<endl;//打印路径及对应路径长（权值和）
        s[k]=1;num++;
        for(i=0;i<vertexNum;i++)//更新权值数组和字符串数组
          if((dist[i]>dist[k]+G[k][i])&&(G[k][i]!=INF))
        {
          dist[i]=dist[k]+G[k][i];
          path[i]=path[k]+"-->"+vertex[i];
        }
      }
    }
    
    
    
    int main()
    {
      CreateMGraph();//创建邻接矩阵
      cout<<"打印邻接矩阵："<<endl;
       for(int i=0;i<vertexNum;i++)
        for(int j=0;j<vertexNum;j++)
      {
        if(G[i][j]==INF) cout<<setw(4)<<"∞";
        else cout<<setw(4)<<G[i][j];
        if(j==vertexNum-1) cout<<endl;
      }
      Dijkstra(0);//以A为源点
      return 0;
    
    }

示例截图：

![img][img 7]

#### Floyd 算法 ####

### 6.4.3 拓扑排序,关键路径 ###

#### **1. AOV网络** ####

> AOV网（Activity On Vertex NetWork）用顶点表示活动，边表示活动（顶点）发生的先后关系。

若网中所有活动均可以排出先后顺序（任两个活动之间均确定先后顺序），则称网是拓扑有序的。

#### **2. 拓扑排序** ####

##### 1) 概念 #####

> 在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：
> 
> 每个顶点出现且只出现一次。  
> 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。  
> 有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

***时间复杂度***

如果AOV网络有n个顶点，e条边，在拓扑排序的过程中，搜索入度为零的顶点所需的时间是O(n)。在正常情况下，每个顶点进一次栈，出一次栈，所需时间O(n)。每个顶点入度减1的运算共执行了e次。所以总的时间复杂为O(n+e)。

##### 2) 算法步骤 #####

*  在网络中选择一个入度为0的顶点输出；
 *  在图中删除该顶点及所有以该顶点为起点的边；
 *  重复上述过程，直至所有边均被输出。

##### 3) 算法图解 #####

![9d1327560510903929a378b86ad12ead.png][]

![01fe3db5984e118547f0c48d92ad3e5f.png][]

##### 4) 代码 #####

#include <bits/stdc++.h>
    using namespace std;
    
    const int  M  = 10001;
    int matrix[M][M];
    int indegree[M]; //book已排序的顶点个数
    
    int main(int argc, char const *argv[])
    {
        int i, j, a, b, k, book = 0, n, m;
        cin >> n >> m;
        for (i = 1; i <= m; ++i)
        {
            cin >> a >> b;
            matrix[a][b]=1;
            indegree[b]++;
        }
        for (i = 1; i <= n; ++i) 
        {
            for (j = 1; j <= n; ++j) 
            {
                if (indegree[j] == 0) 
                { 
                    cout << j << " ";
                    //遍历所有入度为0的顶点
                    indegree[j] = -1;
                    book++;
                    for (k=1; k <= n; k++)
                    {
                       if (matrix[j][k] == 1)
                        {
                            //遍历所有入度为1的顶点
                            matrix[j][k] = 0;
                            indegree[k]--;
                        }
                   }
                   break;
                }
            }
        }   
        system("pause");
        return 0;
    }

##### 5) 应用 #####

拓扑排序通常用来“排序”具有依赖关系的任务。比如，如果用一个DAG图来表示一个工程，其中每个顶点表示工程中的一个任务，用有向边<A,B><A,B>表示在做任务 B 之前必须先完成任务 A。故在这个工程中，任意两个任务要么具有确定的先后关系，要么是没有关系，绝对不存在互相矛盾的关系（即环路）。

#### **3. AOE网络** ####

> AOE网的定义：在带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图简称为AOE网。

![de66f538110853a9085ab6840a507db3.png][]

#### **4. 有向无环图——描述表达式** ####

![b049670f569cd807ef68d2390592810d.png][]

**DAG描述表达式**

![3558ad9a9452a4a668956814b9d0c18b.png][]

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7Tiolsxu-1609144879933)(picture/31.png)\]

节省存储空间

![fa3712f2a12c816fb69dd4de2b07873c.png][]

![6113202606d22c78a40e4debeea60c59.png][]

![666aafb973aae9c115d382138765dc8a.png][]

***解题方法***

![2ab54422f487b82f96a080b6f7dc7728.png][]

Step1：把各个操作数不重复地排成一排

![ce06f80542419adc40cbab506a1ff7f9.png][]

Step2：标出各个运算符的生效顺序（先后顺序有点出入无所谓）

![1740be20a4a437085e9b82e394a7bd30.png][]

Step3：按顺序加入运算符，注意“分层“ (利用下面一层的运算结果来进行)

![20c4c3358fa062d5940aa2d23d3a1ce8.png][]

![6c0e4ef3a421431c4db76cb35b056c1d.png][]

![2c0cd341e777388d0823f93f5ebc098c.png][]

[img]: /images/20221120/7ded3d475b1d4eb9a8f0c2790f2e55af.png
[img 1]: /images/20221120/65154d1a44ab456395a8a92c905bdecb.png
[img 2]: /images/20221120/754f012dab9d4e0fa1b79330a535d381.png
[img 3]: /images/20221120/f7de5443105945bfa29bbab0603675b9.png
[img 4]: /images/20221120/cd3e07aafa5e4e788a742b4e6c1a5943.png
[img 5]: /images/20221120/19887b84bd2243b2978ca9ab4e48076d.png
[format_png]: /images/20221120/13fd054ca7394ec2a6688419a431a30c.png
[942d5ed3b1a8d8768fd1b5382f811eac.gif]: /images/20221120/86e2bd3305c4422584af9ff4155108cb.png
[img 6]: /images/20221120/59f4cb452bcf477d928e64aa923bbef7.png
[img 7]: /images/20221120/d5c964b4523c4613926dc4cd4a6d1ab9.png
[9d1327560510903929a378b86ad12ead.png]: /images/20221120/c022af1be7014823ba4cdc15808c38b1.png
[01fe3db5984e118547f0c48d92ad3e5f.png]: /images/20221120/89a7865239da48aa8b804a9834f836b4.png
[de66f538110853a9085ab6840a507db3.png]: /images/20221120/8c7ed17987774c75bad6d5120749a9e9.png
[b049670f569cd807ef68d2390592810d.png]: /images/20221120/d8ecf7362a06448ca0b7fd6806585d85.png
[3558ad9a9452a4a668956814b9d0c18b.png]: /images/20221120/24fe0eced169461686a38e91421a8051.png
[fa3712f2a12c816fb69dd4de2b07873c.png]: /images/20221120/1d4bdf2be6fe463a95d20317f5de35d1.png
[6113202606d22c78a40e4debeea60c59.png]: /images/20221120/d082943d8b2847b99c069b1d92622955.png
[666aafb973aae9c115d382138765dc8a.png]: /images/20221120/ee7630363f994597a71384a200f0cc5c.png
[2ab54422f487b82f96a080b6f7dc7728.png]: /images/20221120/49a14ff7bf924c4092a5237caab1cdac.png
[ce06f80542419adc40cbab506a1ff7f9.png]: /images/20221120/47c8fb695d924efd826731b0ab4d4743.png
[1740be20a4a437085e9b82e394a7bd30.png]: /images/20221120/319b712922ef4f90a88508e34ffede81.png
[20c4c3358fa062d5940aa2d23d3a1ce8.png]: /images/20221120/a2d4a839f993436e91716f2209237553.png
[6c0e4ef3a421431c4db76cb35b056c1d.png]: /images/20221120/450f124ff61a423892c27c7850e39ca5.png
[2c0cd341e777388d0823f93f5ebc098c.png]: /images/20221120/aa0f58a542e147f7b1947860a8d146bf.png