C++数据结构与算法（图）

谁借莪１个温暖的怀抱￠ 2021-10-31 16:30 338阅读 0赞

> **回顾：**线性表中，每个元素只有一个直接前驱和直接后继，在树形结构中，数据之间是层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。但这都是一对一或一对多的简单模型。

# 1 图的定义 #

> **图（Graph）**是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

> 注意：
> 
> 1.  线性表中我们把数据元素叫作元素，树中将数据元素叫结点，**在图中数据元素被称之为顶点**（Vertex）;
> 2.  线性表中可以没有数据元素，称为空表。树中可以没有结点，称为空树。**在图结构中，不允许没有顶点。在定义中，若V是顶点的集合，则强调了顶点集合V有穷非空；**
> 3.  线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而**图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。**

## 1.1 各种图定义 ##

> **无向图：**若顶点vi到vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对（vi,vj）来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图（Undirected graphs）。下面的无向图G1表示为G1=（V1，\{E1\}\}），其中顶点集合V1=\{A,B,C,D\}，边集合E1=\{(A,B),(B,C),(C,D),(D,A),(A,C)\}.
> 
> ![20190819163056626.png][]
> 
> **有向边：**若从顶点vi到vj的边有方向，则称这条边为有向边，也称为弧（Arc）。用有序偶对<vi,vj>来表示，vi表示弧尾，vj表示弧头。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图（Directed graph）。<A,D>表示弧，不能写成<D,A>。上面的有向图G2表示为G2=（V2，\{E2\}\}），其中顶点集合V2=\{A,B,C,D\}，边集合E2=\{<A,D>,<B,A>,<C,A>,<B,C>\}.
> 
>  *  **在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。**
>  *  **在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有0.5（n(n-1)）条边。**
>  *  **在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n(n-1)条边。对于有n个顶点和e条边数的图，无向图的边数在0~0.5（n(n-1)），有向图的边数在0~n(n-1)之间。**
>  *  **在很少条边或弧的图称为稀疏图，反之称为稠密图。稀疏和稠密是相对的概念。**
>  *  **有些图的边或者弧具有数字（权，Weight），这种带权的图称为网。**
>  *  **树中根结点到任意结点的路径是唯一的，但是图中顶点与顶点之间的路径却是不唯一的。**
>  *  **第一个顶点到最后一个顶点相同的路径称为回路或环（Cycle）。序列中顶点不重复出现的路径称为简单路径，除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单路径或简单环。**
>  *  无向图中的极大连通子图称为**连通分量。**
>  *  有向图中的极大强连通子图称作有向图的**强连通分量**。
>  *  所谓的一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。
>  *  如果一个有向图恰有一个顶点的入度为0，其余顶点的入度为1，则是一棵有向树。

## 1.2 图的定义与术语总结 ##

> 1.  图按照有无方向分为**无向图**和**有向图**。无向图由顶点和边构成，有向图由顶点和弧构成。弧有**弧尾**和**弧头**之分。
> 2.  图按照边或弧的多少分为**稀疏图**和**稠密图**。如果任意两个顶点之间都存在边叫**完全图**，有向的叫**有向完全图**。若无重复的边或顶点到自身的边则叫**简单图**。
> 3.  图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫度，有向图定点分为**入度**和**出度**。
> 4.  图上的边或弧上带权则称为**网**。
> 5.  图中顶点间存在**路径**，两顶点存在路径说明是**连通的**，如果路径最终回到起始点则称为**环**，当中不重复叫**简单路径**。若任意两顶点都是连通的，则图就是**连通图**，有向则称**强连通图**。图中有子图，若子图极大连通则就是**连通分量**，有向的则称**强连通分量**。
> 6.  无向图中连通且n个顶点n-1条边叫**生成树**。有向图中一顶点入度为0其余顶点入度为1的叫**有向树**。一个有向图由若干棵有向树构成**森林**。

## 1.3 图的抽象数据类型 ##

数据：顶点的有穷非空集合和边集合。

操作：

*  构造图
 *  销毁图
 *  返回某个顶点的位置
 *  返回顶点的值
 *  返回某个顶点的邻接节点，若无，则返回空
 *  返回某个顶点相对于顶点w的下一邻接顶点，若无，则返回空
 *  图中添加新顶点
 *  删除图中某个顶点及相关弧
 *  在图中增加弧，若是无向图需要增加对称弧
 *  在图中删除弧，若是无向图需要删除对称弧
 *  对图进行深度优先遍历，在遍历过程时对每个顶点调用
 *  对图进行广度优先遍历，在遍历过程中对每个顶点调用

# 2 图的存储结构 #

## 2.1 邻接矩阵 ##

> 图的**邻接矩阵（adjacency matrix）**存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

*  无向图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70][]

> **注：**这个二维数组是一个对称矩阵，有了这个矩阵，我们就会容易的知道图中的信息。第i个顶点的度就是第i行（列）的元素之和，第i个顶点的所有邻接点就是该顶点所在行（列）对应位置为1的顶点。

*  有向图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1][]

> 注：因为是有向图，所以二维数组不对称。有向图中，某顶点的入度是该顶点所在列所有数字之和，某顶点的出度是该顶点所在行的数字之和。判断两顶点是否存在弧，只需看对应的二维数组中的位置上是否为1即可。网图中，二维数组的值可以有权值，无穷大和零。

eg:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 2][]

## 2.2 邻接表 ##

> 邻接矩阵的问题：当存在边数相对顶点较少的图，这种结构是对存储空间的极大浪费。因此引入邻接表。

> 将数组与链表相结合的存储方法称为邻接表（adjacency list）。
> 
> 在邻接表中，图的顶点用一个一维数组存储（也可以用链表存储，但是数组读取更方便），对于顶点数组，每个数据元素还需存储指向第一个邻接点的指针；图中顶点的所有邻接点构成一个线性表，用单链表存储，无向图称为顶点vi的边表，有向图称为顶点vi作为弧尾的出边表。

*  有向图

![20190819215357862.png][]

*  无向图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 3][]

*  带权值的网图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 4][]

## 2.3 十字链表 ##

> 邻接表的问题：在有向图中，关心出度，想要了解入度就必须遍历整个图才能知道。反之，逆邻接表关心入度，却不了解出度。引入有向图的一种存储方式：十字链表（orthogonal list）——结合邻接表和逆邻接表.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 5][]

> 注：实线代表邻接表，虚线代表逆邻接表，十字链表就是两者的结合。在有向图中，十字链表是非常好的数据结构模型。

## 2.4 邻接多重表 ##

> 问题：无向图的应用中如果关心顶点，邻接表是个不错的选择，但是如果我们关注边的操作（标记、删除等），邻接表结构就比较繁琐。因此，引入邻接多重表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 6][]

> 邻接多重表与邻接表的差别：仅在于同一条边在邻接表中用两个结点表示，而在多重邻接表中，只有一个结点。这样有利于边的操作。

## 2.5 边集数组 ##

> 边集数组是由两个一维数组构成。一个是存储顶点的信息，另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标、终点下标和权组成。边集数组更注重边的操作，对于顶点的操作不适宜用边集数组。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 7][]

# 3 图的遍历 #

> 从图中某一顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次，这一过程叫做图的遍历（traversing graph）。

## 3.1 深度优先遍历 ##

> **深度优先遍历也被称为深度优先搜索（depth first search），简称DFS。**深度优先遍历类似于前序遍历。无向图中，对于邻接矩阵，需要O(n^2)；对于邻接表，需要O(n+e)。有向图同理。注：二叉树的前序遍历、中序遍历和后序遍历属于深度优先遍历。
> 
> 举例：找东西翻个底朝天

## 3.2 广度优先遍历 ##

> 广度优先遍历，又被称为广度优先搜索（breadth first search），简称BFS。广度优先遍历类似于层次遍历。
> 
> 举例：找东西，先找可能会放在的地方，若没有再找其他地方。

>  *  两种遍历方式的时间复杂度一致，在全图遍历上没有优劣之分，仅是对顶点访问顺序不同。
>  *  深度优先遍历更适合目标比较明确，以找到目标为主要目的，而广度优先遍历更适合在不断扩大遍历范围时找到相对最优的情况。
>  *  深度和广度可以上升到方法论的角度，比如博览群书、不求甚解，还是深钻细研、鞭辟入里。

# 4 最小生成树 #

> 概念：将构造连通网的最小代价生成树称为最小生成树。
> 
> 目标：网结构中使得权值之和最小。

1.  方法一：普里姆算法
2.  克鲁斯卡尔算法

> 普里姆算法思路：以某顶点为起点，逐步找各顶点上的最小权值的边来构建最小生成树。该算法的时间复杂度是O(n^2)。
> 
> 举例：从一个入口进世博会，找自己所在位置的周边最感兴趣的场馆，然后进行参观。

> 克鲁斯卡尔算法：以边为目标去创建，因为权值在边上，所以直接去找最小权值的边来构造生成树，构建时要考虑是否会形成环路，采用图的边集数组存储结构。该算法的时间复杂度是O(eloge)。
> 
> 举例：事先计划好去最想去的场馆。

> 对比两个算法：
> 
>  *  克鲁斯卡尔算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势；
>  *  普里姆算法对于稠密图，即半数非常多的情况会更好一些。

# 5 最短路径 #

> 概念：对于网图来说，最短路径是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 8][]

两种求最短路径的方法

*  迪杰斯特拉算法（Dijkstra）
 *  弗洛伊德算法（Floyd）

> **迪杰斯特拉算法**：按路径长度递增的次序产生最短路径，并不是一下子就求出最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得最远顶点的最短路径。时间复杂度:O(elogv)。
> 
> **弗洛伊德算法**：从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大；对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。该算法时间复杂度是O(n^3)，空间复杂度是O(n^2)。

# 6 拓扑排序 #

## 6.1 相关概念 ##

> 1.  在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网（activity on vertex network）.AOV网中的弧表示活动之间存在的某种制约关系。
> 2.  所谓拓扑排序就是对一个有向图构造拓扑序列的过程。

![20190820111412929.png][]

## 6.2 拓扑排序算法 ##

> **算法思想**：从AOV网中选择一个入度为0的顶点输出，然后删除此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。

//摘自https://www.cnblogs.com/skywang12345/p/3711493.html
    #include <iomanip>
    #include <iostream>
    #include <vector>
    #include <cstring>
    using namespace std;
    
    #define MAX 100
    // 邻接表
    class ListDG
    {
        private: // 内部类
            // 邻接表中表对应的链表的顶点
            class ENode
            {
                int ivex;           // 该边所指向的顶点的位置
                ENode *nextEdge;    // 指向下一条弧的指针
                friend class ListDG;
            };
    
            // 邻接表中表的顶点
            class VNode
            {
                char data;          // 顶点信息
                ENode *firstEdge;   // 指向第一条依附该顶点的弧
                friend class ListDG;
            };
    
    	private: // 私有成员
            int mVexNum;             // 图的顶点的数目
            int mEdgNum;             // 图的边的数目
            VNode *mVexs;            // 图的顶点数组
    
        public:
            // 创建邻接表对应的图(自己输入)
    		ListDG();
            // 创建邻接表对应的图(用已提供的数据)
            ListDG(char vexs[], int vlen, char edges[][2], int elen);
    		~ListDG();
    
            // 深度优先搜索遍历图
            void DFS();
            // 广度优先搜索（类似于树的层次遍历）
            void BFS();
            // 打印邻接表图
            void print();
            // 拓扑排序
            int topologicalSort();
    
    	private:
            // 读取一个输入字符
            char readChar();
            // 返回ch的位置
            int getPosition(char ch);
            // 深度优先搜索遍历图的递归实现
            void DFS(int i, int *visited);
            // 将node节点链接到list的最后
            void linkLast(ENode *list, ENode *node);
    };
    
    /*
     * 创建邻接表对应的图(自己输入)
     */
    ListDG::ListDG()
    {
        char c1, c2;
        int v, e;
        int i, p1, p2;
        ENode *node1, *node2;
    
        // 输入"顶点数"和"边数"
        cout << "input vertex number: ";
        cin >> mVexNum;
        cout << "input edge number: ";
        cin >> mEdgNum;
        if ( mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum-1))))
        {
            cout << "input error: invalid parameters!" << endl;
            return ;
        }
     
        // 初始化"邻接表"的顶点
        mVexs = new VNode[mVexNum];
        for(i=0; i<mVexNum; i++)
        {
            cout << "vertex(" << i << "): ";
            mVexs[i].data = readChar();
            mVexs[i].firstEdge = NULL;
        }
    
        // 初始化"邻接表"的边
        for(i=0; i<mEdgNum; i++)
        {
            // 读取边的起始顶点和结束顶点
            cout << "edge(" << i << "): ";
            c1 = readChar();
            c2 = readChar();
    
            p1 = getPosition(c1);
            p2 = getPosition(c2);
            // 初始化node1
            node1 = new ENode();
            node1->ivex = p2;
            // 将node1链接到"p1所在链表的末尾"
            if(mVexs[p1].firstEdge == NULL)
              mVexs[p1].firstEdge = node1;
            else
                linkLast(mVexs[p1].firstEdge, node1);
        }
    }
    
    /*
     * 创建邻接表对应的图(用已提供的数据)
     */
    ListDG::ListDG(char vexs[], int vlen, char edges[][2], int elen)
    {
        char c1, c2;
        int i, p1, p2;
        ENode *node1, *node2;
    
        // 初始化"顶点数"和"边数"
        mVexNum = vlen;
        mEdgNum = elen;
        // 初始化"邻接表"的顶点
        mVexs = new VNode[mVexNum];
        for(i=0; i<mVexNum; i++)
        {
            mVexs[i].data = vexs[i];
            mVexs[i].firstEdge = NULL;
        }
    
        // 初始化"邻接表"的边
        for(i=0; i<mEdgNum; i++)
        {
            // 读取边的起始顶点和结束顶点
            c1 = edges[i][0];
            c2 = edges[i][1];
    
            p1 = getPosition(c1);
            p2 = getPosition(c2);
            // 初始化node1
            node1 = new ENode();
            node1->ivex = p2;
            // 将node1链接到"p1所在链表的末尾"
            if(mVexs[p1].firstEdge == NULL)
              mVexs[p1].firstEdge = node1;
            else
                linkLast(mVexs[p1].firstEdge, node1);
        }
    }
    
    /* 
     * 析构函数
     */
    ListDG::~ListDG() 
    {
        ENode *node;
    
        for(int i=0; i<mEdgNum; i++)
        {
            node = mVexs[i].firstEdge;
            while (node != NULL)
            {
                delete node;
                node = node->nextEdge;
            }
        }
    
        delete[] mVexs;
    }
    
    /*
     * 将node节点链接到list的最后
     */
    void ListDG::linkLast(ENode *list, ENode *node)
    {
        ENode *p = list;
    
        while(p->nextEdge)
            p = p->nextEdge;
        p->nextEdge = node;
    }
    
    
    /*
     * 返回ch的位置
     */
    int ListDG::getPosition(char ch)
    {
        int i;
        for(i=0; i<mVexNum; i++)
            if(mVexs[i].data==ch)
                return i;
        return -1;
    }
    
    /*
     * 读取一个输入字符
     */
    char ListDG::readChar()
    {
        char ch;
    
        do {
            cin >> ch;
        } while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
    
        return ch;
    }
    
    
    /*
     * 深度优先搜索遍历图的递归实现
     */
    void ListDG::DFS(int i, int *visited)
    {
        ENode *node;
    
        visited[i] = 1;
        cout << mVexs[i].data << " ";
        node = mVexs[i].firstEdge;
        while (node != NULL)
        {
            if (!visited[node->ivex])
                DFS(node->ivex, visited);
            node = node->nextEdge;
        }
    }
    
    /*
     * 深度优先搜索遍历图
     */
    void ListDG::DFS()
    {
        int i;
        int *visited;       // 顶点访问标记
    
        visited = new int[mVexNum];
        // 初始化所有顶点都没有被访问
        for (i = 0; i < mVexNum; i++)
            visited[i] = 0;
    
        cout << "== DFS: ";
        for (i = 0; i < mVexNum; i++)
        {
            if (!visited[i])
                DFS(i, visited);
        }
        cout << endl;
    
        delete[] visited;
    }
    
    /*
     * 广度优先搜索（类似于树的层次遍历）
     */
    void ListDG::BFS()
    {
        int head = 0;
        int rear = 0;
        int *queue;     // 辅组队列
        int *visited;   // 顶点访问标记
        int i, j, k;
        ENode *node;
    
        queue = new int[mVexNum];
        visited = new int[mVexNum];
        for (i = 0; i < mVexNum; i++)
            visited[i] = 0;
    
        cout << "== BFS: ";
        for (i = 0; i < mVexNum; i++)
        {
            if (!visited[i])
            {
                visited[i] = 1;
                cout << mVexs[i].data << " ";
                queue[rear++] = i;  // 入队列
            }
            while (head != rear) 
            {
                j = queue[head++];  // 出队列
                node = mVexs[j].firstEdge;
                while (node != NULL)
                {
                    k = node->ivex;
                    if (!visited[k])
                    {
                        visited[k] = 1;
                        cout << mVexs[k].data << " ";
                        queue[rear++] = k;
                    }
                    node = node->nextEdge;
                }
            }
        }
        cout << endl;
    
        delete[] visited;
        delete[] queue;
    }
    
    /*
     * 打印邻接表图
     */
    void ListDG::print()
    {
        int i,j;
        ENode *node;
    
        cout << "== List Graph:" << endl;
        for (i = 0; i < mVexNum; i++)
        {
            cout << i << "(" << mVexs[i].data << "): ";
            node = mVexs[i].firstEdge;
            while (node != NULL)
            {
                cout << node->ivex << "(" << mVexs[node->ivex].data << ") ";
                node = node->nextEdge;
            }
            cout << endl;
        }
    }
    
    /*
     * 拓扑排序
     *
     * 返回值：
     *     -1 -- 失败(由于内存不足等原因导致)
     *      0 -- 成功排序，并输入结果
     *      1 -- 失败(该有向图是有环的)
     */
    int ListDG::topologicalSort()
    {
        int i,j;
        int index = 0;
        int head = 0;           // 辅助队列的头
        int rear = 0;           // 辅助队列的尾
        int *queue;             // 辅组队列
        int *ins;               // 入度数组
        char *tops;             // 拓扑排序结果数组，记录每个节点的排序后的序号。
        ENode *node;
    
        ins   = new int[mVexNum];
        queue = new int[mVexNum];
        tops  = new char[mVexNum];
        memset(ins, 0, mVexNum*sizeof(int));
        memset(queue, 0, mVexNum*sizeof(int));
        memset(tops, 0, mVexNum*sizeof(char));
    
        // 统计每个顶点的入度数
        for(i = 0; i < mVexNum; i++)
        {
            node = mVexs[i].firstEdge;
            while (node != NULL)
            {
                ins[node->ivex]++;
                node = node->nextEdge;
            }
        }
    
        // 将所有入度为0的顶点入队列
        for(i = 0; i < mVexNum; i ++)
            if(ins[i] == 0)
                queue[rear++] = i;          // 入队列
    
        while (head != rear)                // 队列非空
        {
            j = queue[head++];              // 出队列。j是顶点的序号
            tops[index++] = mVexs[j].data;  // 将该顶点添加到tops中，tops是排序结果
            node = mVexs[j].firstEdge;      // 获取以该顶点为起点的出边队列
    
            // 将与"node"关联的节点的入度减1；
            // 若减1之后，该节点的入度为0；则将该节点添加到队列中。
            while(node != NULL)
            {
                // 将节点(序号为node->ivex)的入度减1。
                ins[node->ivex]--;
                // 若节点的入度为0，则将其"入队列"
                if( ins[node->ivex] == 0)
                    queue[rear++] = node->ivex;  // 入队列
    
                node = node->nextEdge;
            }
        }
    
        if(index != mVexNum)
        {
            cout << "Graph has a cycle" << endl;
            delete queue;
            delete ins;
            delete tops;
            return 1;
        }
    
        // 打印拓扑排序结果
        cout << "== TopSort: ";
        for(i = 0; i < mVexNum; i ++)
            cout << tops[i] << " ";
        cout << endl;
    
        delete queue;
        delete ins;
        delete tops;
    
        return 0;
    }
    
    int main()
    {
        char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        char edges[][2] = {
            {'A', 'G'}, 
            {'B', 'A'}, 
            {'B', 'D'}, 
            {'C', 'F'}, 
            {'C', 'G'}, 
            {'D', 'E'}, 
            {'D', 'F'}}; 
        int vlen = sizeof(vexs)/sizeof(vexs[0]);
        int elen = sizeof(edges)/sizeof(edges[0]);
        ListDG* pG;
    
        // 自定义"图"(输入矩阵队列)
        //pG = new ListDG();
        // 采用已有的"图"
        pG = new ListDG(vexs, vlen, edges, elen);
    
        pG->print();   // 打印图
        pG->DFS();     // 深度优先遍历
        pG->BFS();     // 广度优先遍历
        pG->topologicalSort();     // 拓扑排序
    
        return 0;
    }

# 7 关键路径 #

> 如果要对一个流程图获得最短时间，就必须要分析它们的拓扑关系，并且找到当中最关键的流程，这个流程的时间就是最短时间。
> 
> 在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为**AOE网（activity on edge network）**。
> 
> 实现代码见：[https://www.cnblogs.com/may-star/p/10613448.html][https_www.cnblogs.com_may-star_p_10613448.html]

[20190819163056626.png]: /images/20211031/6ada3d4d611e4f19a3d63155731eadb1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70]: /images/20211031/1fff38abed0d4c5d84e5762f19846642.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1]: /images/20211031/6ab555604f2b4b80b87de39ceda5d4bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 2]: /images/20211031/1dd0835429f444d18a80f30c112bc14e.png
[20190819215357862.png]: /images/20211031/2ee216adb90b44cda26939c1997d47fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 3]: /images/20211031/13c8de0c6c084bad873e1c53a8a30e60.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 4]: /images/20211031/36568d4fc73d417f818229fa4675dcfa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 5]: /images/20211031/1bff83509ae340ae9094fa363acfd755.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 6]: /images/20211031/2ca91ace703d4433b6fbab401731a593.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 7]: /images/20211031/457ded3e93fd4b1082b43c636f77dbe9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 8]: /images/20211031/7cfef83887f645779617ac892deda49d.png
[20190820111412929.png]: /images/20211031/6f22517b15b545448099a09ee9331a29.png
[https_www.cnblogs.com_may-star_p_10613448.html]: https://www.cnblogs.com/may-star/p/10613448.html