[C++知识库]基于C语言的图论汇编

图论

图形结构，多对多的关系

图的定义和基本术语

G = (V,E) V:顶点Vertex，有穷非空集合
E: 边Edge，非空集合

区分有向图和无向图

完全图：任意两个顶点都有一条边相连

有向完全图，任意两个顶点都有两条边相连，边称为弧

无向完全图：任意两个顶点都有一条边相连

无向完全图：若有n个顶点，则有n(n-1)/2条边
有向完全图：若有n个顶点，则有n(n-1)条边

稀疏图：有很少边或弧的图。(e<n *log (n))

稠密图：有较多边或弧的图

网： 边或弧带权的图

邻接：两个顶点之间有边或弧相连，邻接关系

<Vi,Vj>称为Vi邻接到Vj,Vj邻接于Vi

(Vi,Vj),称Vi和Vj互为邻接点

关联（依附）：边或弧与顶点之间的关系

顶点的度：与该顶点相关联的边的数目，记为：D（v）Degree在有向图中，顶点的度又分为入度和出度并且顶点的度等于入度+出度，入度ID(v)Input Degree,出度OD(v)Output Degree

当有向图中仅有一个顶点的入度为0,其余顶点的入度均为1,此时是何形状？

答：是树！而且是一颗有向树

路径：接续的边构成的顶点序列

路径长度：路径上边或弧的数目或权值之和

回路（环）：第一个顶点和最后一个顶点是相同的。

简单路径：除了路径起点和重点可以相同外，其余顶点均不相同的路径。

简单回路简单环）：从起点出发又回到终点，并且路径无重叠

非简单回路：又回到终点，并且路径无重叠。

连通图（强连通图），在无（有）向图G=(V,{E})中，若对任何两个顶点 V,u 都存在从V到u的路径，则称G是连通图（强连通图），所有点都可以去

非连通图：有些点去不了

权与网：图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。

网：路径图称为网

子图：若一个图的顶点和边都分别是另一个图的子集，则称前者是后者的子图。

连通子图：子图任意连个顶点之间是连通的。

极大连通子图：子图中连图数目达到了最大，在加入一个顶点的话就回破坏连通性。

连通分量：无向图的极大连通子图称为连通分量。

强连通分量：有向图的极大连通子图称为强连通分量。单个顶点也是强连通分量。

极小连通子图：在一个连通子图中，删除任何一条边都将破坏图的连通性。

生成树：包含无向图的所有顶点的极小连通子图。可以转换为树的形式。

生成森林：对非连通图，由各个连通分量的生成树的集合。

图的存储结构（无向图）

图没有顺序存储结构，但是可以借助二维数组来表示元素间的关系

邻接矩阵（数组）：数组表示法

图的链式存储结构：邻接表（链式），邻接多重表，十字链表

数组表示法具体实现：

    1建立一个顶点表：A = (V,E),Vexs[n]
    2.建立邻接矩阵：二维数组A.arcs[n][n]
        如果<i,j>属于E的子集，或者（i,j）属于E的子集则添加1
        否则添加0
        顶点和它自身不存在邻接关系

特点：

无向图的邻接矩阵是对称的

顶点的度数等于 邻接矩阵中每一行中1的个数，即邻接矩阵中该行所有元素之和。

特别的，完全图的邻接矩阵中，只有对角元素为0,其余都为1。

邻接矩阵规模：N*N

图的存储结构（有向图）

有向图的邻接矩阵只记录弧的发出者

有向图的邻接矩阵中，行头记录发出者，列头记录接受者

特点：

邻接矩阵非对称
顶点的度数  = 所在行元素之和 + 所在列元素之和

网（带权图）的邻接矩阵表示法

邻接矩阵的元素为两个顶点之间的权重，如果两个顶点之间没有弧则记该元素为无穷大

邻接矩阵的建立

用两个数组分别存储顶点表和邻接矩阵

#define MVN 100 // Matrix Vertex Number
#define Maxlnt 32767 // 无穷大
typedef char VerTexType; // Vertex type
typedef int ArcType;//Arc type
typedef struct
{
    VerTexType vex[MVN];// Vertext array
    ArcType arcs[MVN][MVN];// Adjacency Matrix Graph
    int Vexnum,Arcnum;// Current vertex nums & arc nums
}AMGraph;

算法思想：

输入总顶点数和总变数
以此输入点的信息存入顶点表中
初始化邻接矩阵，使每个权值初始化为极大值
构造邻接矩阵

Status CreateUDN(AMGraph &G)// Create Un Direction Net
{
    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++)
        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;// 输入确定边的两个点和边的权值
        i = LocateVex(G,v1);//在顶点表中查找顶点的下标
        j = LocateVex(G,v2);
        G.arcs[i][j] = w;// 边<v1,v2>确定的权值为w
        G.arcs[j][i] = G.arcs[i][j];//无向有权图矩阵特性：沿对角线对称
        
    }
    return OK;
    // 悟：邻接矩阵中的元素若不为极大值，则标志v1 和v2 是连通的，并且元素的值代表着边的权值。
    // 悟：学好邻接矩阵的关键在于心中要有图，要有表。
}

int LocateVex(AMGraph G, VertexType u)
{
    int i;
    for(i = 0;i < G.vexnum;i++)
    {
        if(u == G.vexs[i])// 如果该顶点和顶点表中的值相匹配的话。
            return i;// 返回顶点表中该顶点的下标。
    }
   
}

无向图的建立

基于无向网的建立，初始化时不需要把每个矩阵中每个元素的值都定义为极大值，另外用1来表示该顶点和另一顶点之间存在通路。

有向网的建立

基于无向网的建立，邻接矩阵是非对称矩阵，只有G.arcs[i][j]没有G.arcs.[j][i],简单来说就是只有双向的两个顶点才和无向网一样，单向的只有一组联系。

邻接矩阵的评价

优点：方便查找任一顶点的邻接点。方便查看两个顶点之间的关系。

缺点：结构太静态，不容易修改。如果两个顶点之间没有关系，那么仍然回按照顶点来构造矩阵，会造成空间的浪费。对于稀疏图的边的统计是比较浪费时间的。

Time：2022.9.14 图的存储结构

为了解决邻接表求节点的度的困难问题，有向图我们用十字链表来存储，无向图我们用邻接多重表来存储。

十字链表

十字链表是有向图的另一种链式存储结构，目的是方便检查顶点的入度和出度，核心思想是把邻接矩阵和逆邻接矩阵结合起来。

弧尾→ 弧头

通过下列顶点结构

struct {
    VertexType data;
    ArcBox *firstin,*firstout;//分别指向该顶点第一条入弧和出弧
}

邻接多重表（无向图的另一种链式存储结构）

出现原因：无向图的邻接矩阵中，每条边都需要存储两边。

顶点构造：Data, firstedge,边节点:mark, ivex, ilink, jvex, jlink, infomark 显示该边是否被搜索过，ivex搭配jvex指示该边所依附的两个顶点在数组中的位置，ilink 搭配ivex指示ivex的其他连通的情况，jlink 搭配 jvex指示 jvex的其他连通情况。如果是网的话，info可以用来存储权值等信息。

我们可以快速知道顶点的出入度情况。

• 1. 实现邻接表和逆邻接表
• 2. 学习离散数学中树和图的有关知识（了解）
• 3. 学习 王卓-数据结构与算法-的图的十字链表知识，并作笔记。

图的遍历

定义：

从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，并且每个顶点仅被访问以此，这个过程叫做图的遍历，他是图的基本运算。

特征：

图中可能存在回路

怎样避免重复访问？

答：visited[n]用来标记每个被访问过的顶点。初始状态为0,被访问过则修改为1.

深度优先搜索遍历DFS(Depth First Search)

一条道走到黑沿着某一分支搜索到底，然后折返，看看折返后的顶点有没有未被访问过的分支，如果有搜索到底，然后折返重复以上动作，直到所有顶点的所有分支都被访问过为止。

深度优先的算法实现

是存储结构规定了遍历的顺序

void DFS(AMGraph G, int v)
{
    printf("%d",v);
    visited[v] = true;//已被访问过，打上标记
    for(int w = 0; w < G.Vexnum; w++)// 访问v的邻接点w
        if((G.arcs[v][w]!=0)&&(!visited[w]))//如果是邻接点，且未被访问过，则访问
            DFS(G,w);// 递归调用DFS继续访问
}

算法效率分析

n^2,邻接表 n + e

用邻接表来表示图，虽然有2e个表节点，但只需要扫描e个节点即可完成遍历，加上访问n个头节点的时间，时间复杂度为n+e

用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为n^2

非连通图的遍历，需要到另一个连通分量中任选一个顶点然后重复遍历算法。

结论： 邻接矩阵用于稠密图的深度遍历，邻接表用与稀疏图的深度遍历。

广度优先搜索遍历BFS(Breadth First Search)

从图的某一节点出发，首先访问该节点的所有临界点，在按照这些节点被访问的先后次序依次访问与他们相邻接的所有未被访问的顶点。重复此过程，直到所有顶点都被访问完为止。

算法实现：

使用邻接表来存储顶点
需要一个visited数组，用以记录该节点是否被访问过
需要一个循环队列，类似于树的层次遍历，从根节点到孩子节点依次入队

void BFS(Graph G, int v)//Breadth First Search
{
    printf("%d",v);
    visited[v] = true;
    InitQueue(Q);// 初始化循环队列
    EnQueue(Q,v);// v 进队
    while(!QueueEmpty(Q))// 队列非空
    {
        DeQueue(Q,u);// 对头元素出队，并置为u
        for(w = FirstAdjVex(G,u); w > = 0; w = NextAdjVex(G, u, w))
            if(!visited[w])
            {
                printf("%d",w);// 输出下一个节点
                visited[w] = true;//标记为已访问
                EnQueue(Q,w);// v的邻接点w入队
            }// if
    }//while
}//BFS

算法效率分析

如果BFS使用邻接矩阵的存储方式的话，时间复杂度是n^2（n为行元素个数与列元素个数）

如果BFS使用邻接表的存储方式的话，时间复杂度是n+e(e为节点个数，n为头节点个数)

邻接矩阵方便查找出度，和度数，但是不方便查找入度。解决方案一是建立逆邻接矩阵，解决方案二是使用邻接表。

DFS & BFS 算法效率比较

空间复杂度相同，DFS借用了栈(递归算法)，BFS借用了队列，空间复杂度为n

时间复杂度只与存储结构有关（邻接矩阵或邻接表），与搜索路径无关。

任务

• 实现有向图的邻接表的存储结构
• 实现一个循环队列
• 翻看严蔚敏—数据结构与算法—深度&广度优先章节

图的应用

最小生成树

生成树：所有顶点均由边连接在一起，但是不存在回路的图
一个图可以有许多生成树
生成树的顶点个数与图的顶点个数相同
生成树是图的极小连通子图，去掉一个边则不连通
在生成树中再加一条边必然形成回路
若图的节点个数是n则生成树的边数是n-1生成树要包含图中所有顶点
生成树中任意两个顶点间的路径是唯一的
具有n个节点，n-1条边的树不一定是生成树（主要考虑：连通性和回路）

构建生成树的方法

使用深度优先法，但是访问所有的节点，每访问一条边就加上一条边，但是不能形成回路。此种方法也叫深度优先生成树。

什么是最小生成树？

给定一个无向网，在该网的所有生成树中，使得各边权值之和最小的那棵生成树被称为最小生成树，也叫最小代价生成树。

最小生成树3,MST性质（Minium Spanning Tree）

**最小生成树性质：**设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中一条“一个端点在U中(例如：u∈U)，另一个端点不在U中的边(例如：v∈V-U)，且(u，v)具有最小权值，则一定存在G的一棵最小生成树包括此边(u，v)。附带书面笔记。

最小生成树4,利用MST性质构造最小生成树。

葡李穆 （prim）算法：三个集合，V集合（顶点集），U集合，TE集合（边集合），不断的在V中搜索最小带权路径（距离U中顶点），并把相应的V中元素纳入到U中（不能成环），直到集合U= V为止。手写笔记有图片。

最小生生成树5，克鲁斯卡尔（Kruskal）算法

算法思想：两个集合，一个是E即顶点集，一个是T非连通的顶点集，不断的在E中挑选最小的带权路径，如果此路径不会导致T中对应的顶点形成环的话，就直接把T中对应的顶点相连，结束条件应是：若E中有n个元素，则应有n-1条边。

当路径的权值相同时，肯能造成不同的最小生成树，但最小生成树本就不唯一。

两个算法P & K 对比

葡李穆算法时间复杂图为n^2（n为顶点数）,克鲁斯卡尔算法时间复杂度为eloge（e为边数）。根据时间复杂度，P适用于稠密图，K适用于稀疏图。

最短路径问题

如何能够使一个地点到另一个地点的运输时间最短或运费最省？这就是一个求两个地点间的最短路径问题。

问题抽象：在有向网中A点到B点的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。

第一类问题：知道原点和终点，找到最短路径。

单源最短路径：用Dijkstra(迪克牛仔斯特拉)算法，两个集合：S集合（已找到的最短路径的顶点集合）和T集合（未搜索的路径的集合），将T中顶点按最短路径递增的次序加入到S中。

保证：集合S中的顶点到源点的路径长度是递增的。

保证：每个顶点对应一个距离值，S中顶点对应最短路径，T中顶点对应从源点到S中间顶点最后到T中顶点的最短路径长度。

按路径长度递增

第二类问题：某源点到其他各点最短路径。

所有顶点间的最短路径：用Floyd(弗洛伊德)算法。

首先构造一个邻接矩阵，初始化该矩阵，只记录每个顶点可以直达的顶点对应的边。然后每次从图的顶点中拿出一个顶点加入到已存在的图中，看看有没有新的路径产生，或者已存在的路径是否会变小，如果有变动，则修改邻接矩阵。直到把图中所有的顶点都试探完为止。

代码暂无

迪克牛仔斯特拉：有效的程序员不应该浪费时间用于调试程序，而应该在一开始就把故障引入。

拓扑排序

有向无环图：Directed Acycline Graphy DAG

AOV 网：用一个有向图表示一个工程的各个子工程及其相互制约关系，其中以顶点表示活动，弧表示活动之间的制约关系，我们称这种图为顶点表示活动的网（Activity On Vertex network）解决拓扑排序问题

AOV网的特点：

若从i到j有一条有向路径，则i是j的前驱，j是i的后继

若从i到j是网中的有向边，则i是j的直接前驱，j是i的直接后继

AOV网中不允许存在回路，如果存在回路则表示某一活以自身为先决条件，这是荒谬的。

拓扑有序序列

在AOV网中没有回路的前提下，我们把图中的全部顶点（活动）排成一个有序序列，使得这个序列中的元素仍然能保持AOV网中前驱与后继的关系，那么这个有序序列也叫做拓扑有序序列。相应的算法，叫做拓扑排序。

AOV的拓扑序列是不唯一的

检测环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。

拓扑序列检测网中是否有环的原理：环的每一个顶点都有前驱，而构造拓扑序列需要的是无前驱的顶点。因此存在环的哪一部分顶点必然回剩下，不会加载到拓扑序列中去。

关键路径1

AOE网： 用一个有向图表示一个工程的各个子工程及其相互制约关系，以弧表示活动本身，以顶点表示活动的开始或结束，我们称这种图为边表示活动的网（Activity of Edge network）解决关键路径问题

把工程计划表示为边表示活动的网络，即AOE网，用顶点表示事件，弧表示活动本身，弧的权表示活动持续的时间呢。顶点表示事件的起点和终点。

Time:2022.9.16

• 王卓-数据结构与算法往后学习
• 整理数据结构与算法笔记
• 实现十字链表

关键路径2

关键路径就是图的路径长度最长的路径。

路径长度：路径上个各活动持续时间之和。

ve(vj) early, 事件vj的最早发生时间。
vl(vj) late，事件vj最晚发生时间。

e(i) 表示活动i的最早开始时间。
l(i) 表示活动i的最晚开始时间。

时间余量：最晚开始时间减去最早开始时间。
关键活动：没有时间余量， l(i) - e(i) = 0;

如何找到某一活动的最早/最晚开始时间？

只需找出该活动所在两个顶点（事件）中，一事件的最早发生时间，一事件的最晚发生时间，求差值即可。
1.计算Ve(i),Vl(j)即每一个顶点的最早和最晚发生时间
2.求e(i),l(i)
3.计算l(i) - e(i)

关键路径总结

1.若网中有几条关键路径存在，则需加快同时在几条关键路径上的关键活动
2.如果一个活动处于所有的关键路径上，那么提高这个活动的速度就能缩短整个工程完成的时间。
3 处于所有关键路径上的活动完成时间也不能缩短太多，否则会使原来的关键路径变成不是关键路径。这时，就需要重新寻找关键路径，这可能导致时间资源的浪费。

Time: 2022.9.18 日铭记国耻

• 实现深度遍历和广度遍历
• 聚合整理笔记。