第六章：图

6.1 图的定义和术语

详细定义

数据结构：图(Graph)【详解】UniqueUnit的博客-CSDN博客数据结构图
这里放一张图来看一下本章需要学习的

基本这里看看定义就可以了，比较简单，不详细赘述了。（上述链接中有关图的东西讲的很详细了，后面的篇幅会更侧重重点部分）

6.2 图的存储结构

图的四种常用存储结构：

• 数组(邻接矩阵)表示法
• 邻接表
• 十字链表
• 邻接多重表

重点记住邻接矩阵、邻接表即可

之后的内容都是挑上面那个链接里面的重点来讲的，所以不懂的地方可以看原文章。

邻接矩阵表

根据上述有关于图的定义，我们不难知道图的种类一般分为四种：

• 有向图
• 无向图
• 有向带权图
• 无向带权图

我们先用最简单的无向图来解释。

• 所谓邻接矩阵就是用一个二维数组，来表示对应点是否存在边(也就是用来表示边的集合）
• 用一个一维数组来表示结点的集合

举个例子：

在这个二维数组中，1表示这两个结点有边，0则表示没有。

由于无向图不分出和入，所以无向图的二维数组是一个关于主对角线对称的矩阵。 结点Vi的度 = Vi所在行或者列的数值之和。

那推广到有向图

可以发现有向图的二维数组就不一定是对称矩阵了

结点Vi的入度 = Vi所在行的数值之和。 结点Vi的出度 = Vi所在列的数值之和。

再推广到带权图可以得到如下

简单的来讲就是将1转换为对应的权值。不存在边就用无穷大表示两点的权值大小

无向图同理，这里就不再放出来了。 有一点需要注意的是，这里的无穷大在C语言中没办法表示，所以我们一般会顶一个一个很大的值，来模拟表示无穷大。 比如我定义一个 #define MAX 65535 用MAX来代替无穷大。

接下来讲抽象存储结构

下面是PPT上面的定义

#define INFINITY       INT_MAX                    // 我也不知道这个定义是干啥的，应该是用来定义无穷大的
#define MAX_VERTEX_NUM    20                    //定义结点的最大个数 不能超过20个
typedef enum {DG, DN, UDG, UDN} GraphKind        //这个是一个枚举类型，GraphKind表示图的类型，enum {DG, DN, UDG, UDN}表                                                    示图的类型只能是DG，DN，UDG，UDN其中一个，就是对应我讲过的四种基本的图的类型
//定义存储边的集合的二维数组
typedef struct ArcCell{
    VRType       adj;                            // 定义边是否存在（一般是int类型，1表示存在，0表示不存在）
    InfoType      *info;                        // 这玩意我这也不知道是干嘛的 有懂的速速私我
}ArcCell, AdjMatrix[MAX_VERTEX_NUM ][MAX_VERTEX_NUM] 
// 这里的表示等同于 AdjMatrix = ArcCell[MAX_VERTEX_NUM ] [MAX_VERTEX_NUM]
// 这样之后定义一个二维数组就只需要使用 “AdjMatrix 变量名”即可
//下面才是关于图的定义
typedef struct {
    VertexType   vex[MAX_VERTEX_NUM];            // 定义类型为VertexType（一般为char类型）的vex数组来存储结点，个数为                                                           MAX_VERTEX_NUM，
    AdjMatrix   arcs;                            // 定义边集
    int   vexnum, arcnum;                        // 分别定义结点的个数，边的个数
    GraphKind  kind;                            // 定义图的类型（图的类型只能是DG，DN，UDG，UDN其中一个）
}MGraph

因为图有四个种类，所以创建图的时候需要一个总函数来判断类型，再根据不同类型创建图。

Status CreateGraph(MGraph &G){//在邻接矩阵存储结构上根据图的种类调用具体构造算法
    printf("please input the kind of graph\n");
    scanf("%d",&G.kind);
    //根据图的不同种类来进行构建
    switch(G.kind){
        case DG:return CreateDG(G);      //构造有向图
        case DN:return CreateDN(G);      //构造有向网
        case UDG:return CreateUDG(G);     //构造无向图
        case UDN:return CreateUDN(G);     //构造无向网
        default:return ERROR;
    }
}

这里用无向图来举例进行创建

Status CreateUDG(MGraph &G) //在邻接矩阵存储结构上，构造无向图 
  {
    scanf(&G.vexnum,&G.arcnum);                            //读入顶点和边数目
    for(i=0;i<G.vexnum;i++)    scanf(“%c”,&G.vexs[i]); //构造顶点向量 %c说明是字符类型
    //邻接矩阵初始化
    for(i=0;i<G.vexnum;i++)                                     
       for(j=0;j<G.vexnum;j++)
          G.arcs[i][j]={0, NULL};
    // 这里用大括号赋值，前一个0表示i j结点不存在边
    // 如果说着是一个带权图，这里的0就替换成 MAX（表示无穷大）
    for(k=0;k<G.arcnum;k++){                                //构造邻接矩阵
    scanf(“%c,%c”,&v1,&v2);                                    //读入一条边依附的顶点及权值 v1，v2就是边的两个端点
    // 在无向图里面顺序不重要，但是在有向图里面表示v1->v2
    i=LocateVex(G,v1); j=LocateVex(G,v2);                    //确定v1、v2在图中的索引
        G.arcs[i][j].adj=1;                                    //根据索引确定边<v1，v2>的权值（如果是有向图就输入对应权值）
        G.arcs[j][i]=G.arcs[i][j];                            //置<v1,v2>的对称弧<v2,v1>
        // 如果是有向图，上面这条语句就可以去除
    }     return OK;
}//CreateUDG

当边比较少的情况下，邻接矩阵就比较浪费存储空间，所以下面引入邻接表。

邻接表

邻接表简单的来讲就是以所有结点为头结点，创建n个单链表
每个单链表后面的结点都表示头结点和该几点存在边
如下图所示

这里竖的节点12345就表示顶点表 每一个横的链表就是边表 顶点的度：该顶点所在单链表中表结点个数 这里只演示无向图，有向图也差不多，相信大家自己都能明白，这里就不做解释了。

邻接表的抽象定义：

#define MAX_VERTEX_NUM 20
typedef struct ArcNode
{    int adjvex;                    //存放结点的下标或者位置
    struct ArcNode *nextarc;    //指向下一个表结点
    infoType *info;                //存储权值
}ArcNode;
typedef struct VNode            //头结点的定义
{    VertexType data;            //存储结点的值
    ArcNode *firstarc;            //头结点的指针
}VNode,AdjList[MAX_VERTEX_NUM];    //用AdjList表示头结点的集合
typedef struct
{    AdjList vertices;            //结点的集合
    int vexnum,arcnum;            //点的个数和边的个数
    int kind;                    //图的种类
}ALGraph;

构造无向图邻接表的算法

//创建以邻接表为存储结构的无向图
void creategraph(ALGraph &G){                                 
    scanf(“%d，%d”,&G.vexnum, &G.arcnum);            //读入顶点和边的数目
    for(i=0;i< vexnum;i++){                                 
        scanf(“%c”,&G.vertices[i].data);                     
        G.vertices[i].firstarc=NULL;     
    }//读入顶点值
    for(i=0;i<=arcnum;i++){                            //建立边<s,d>(<d,s>)的信息
        scanf(“%d,%d”,&s,&d);                        //读入顶点序号（在数组中的索引）
        p=(ArcNode*)malloc(sizeof(ArcNode)); 
        q=(ArcNode*)malloc(sizeof(ArcNode));
        //创立两个临时的ArcNode指针
        p->adjvex=d;   q->adjvex=s;    
        //边<G.vertices[s].data,G.vertices[d].data>     
        p->nextarc=G.vertices[s].firstarc;            //表示p结点的指向的下一个是索引为s头结点的下一个结点
        G.vertices [s].firstarc=p;                    //q->p
        // 如果是有向图下面这两句就可以去除
        q->nextarc=G.vertices[d].firstarc;
        G.vertices[d].firstarc=q;//无向图，所以是双向的 与上面同理
    }
}

数据结构 图的邻接表夜雨柠檬-CSDN博客数据结构邻接表
邻接表的优缺点：

• 优点：易找到任一顶点的第一个邻接点和下一个邻接点。适合存储稀疏图。
• 缺点：判定任意两个顶点之间是否有边或弧相连，需搜索第i和第j个单链表。不及邻接矩阵

…..

代码我是真的看不懂了，真的蚌埠住了，自己看吧，我就讲讲算法了，等我之后会了代码再说。

6.3 图的遍历

深度优先遍历（DFS算法）

算法：类似二叉树的先序遍历
简单来讲就是从左开始往深处遍历，一直到不能遍历，在回到上一层往右遍历至不能遍历，如此循环。
例如：

其深度优先遍历的结果为 a b d e h c f g
代码：

bool visited[MAX_VERTEX_NUM];    //访问标记数组
/*从顶点出发，深度优先遍历图G*/
void DFS(Graph G, int v){
    int w;
    visit(v);    //访问顶点
    visited[v] = TRUE;    //设已访问标记
    //FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。
    //NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点v
    for(w = FirstNeighbor(G, v); w>=0; w=NextNeighor(G, v, w)){
        if(!visited[w]){    //w为u的尚未访问的邻接顶点
            DFS(G, w);
        }
    }
}
/*对图进行深度优先遍历*/
void DFSTraverse(MGraph G){
    int v; 
    for(v=0; v<G.vexnum; ++v){
        visited[v] = FALSE;        //初始化已访问标记数据
    }
    for(v=0; v<G.vexnum; ++v){    //从v=0开始遍历
        if(!visited[v]){
            DFS(G, v);
        }
    }
}

用邻接矩阵存储图时，查找每个顶点的邻接点需要O(n2); 用邻接表存储图时，查找邻接点需要O(e); 当以邻接表作存储结构时，深度优先遍历的时间复杂度为O(n+e) 其中n为**顶点个数**，e为**边数**

广度优先遍历（BFS算法）

算法：类似二叉树的层次遍历
简单来讲逐层遍历。
例如：

其深度优先遍历的结果为 a bc defg h
代码：

/*邻接矩阵的广度遍历算法*/
void BFSTraverse(MGraph G){
    int i, j;
    Queue Q;
    for(i = 0; i<G,numVertexes; i++){
        visited[i] = FALSE;
    }
    InitQueue(&Q);    //初始化一辅助用的队列
    for(i=0; i<G.numVertexes; i++){
        //若是未访问过就处理
        if(!visited[i]){
            vivited[i] = TRUE;    //设置当前访问过
            visit(i);    //访问顶点
            EnQueue(&Q, i);    //将此顶点入队列
            //若当前队列不为空
            while(!QueueEmpty(Q)){
                DeQueue(&Q, &i);    //顶点i出队列
                //FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。
                //NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点v
                for(j=FirstNeighbor(G, i); j>=0; j=NextNeighbor(G, i, j)){
                    //检验i的所有邻接点
                    if(!visited[j]){
                        visit(j);    //访问顶点j
                        visited[j] = TRUE;    //访问标记
                        EnQueue(Q, j);    //顶点j入队列
                    }
                }
            }
        }
    }
}

6.4 图的连通性问题

无向图的连通分量和生成树（了解即可）

联通分量

简单来讲就是连通在一起的就是一个连通分量

比如上面这张图的连通分量就是3。
分别是ABCFLMJ和DE和IGHK

生成树

就是把所有的连通分量转换成为树从而形成一个森林
如下图

怎么形成的这里先不讲，因为这个不是重点。 注意：生成树不唯一

最小生成树（重点）

最小生成树：生成树中边的权值（代价）之和最小的树。

最小生成树同样不唯一。

举个例子：

左图的最小生成树就有右边两种。

构造最小生成树的算法

Prim算法（重点掌握）

算法思想：

看不懂没关系，举个例子一下就明白的

举个例子：写出下面图的最小生成树。

第一步：找一个头结点，这里我们选择的是V1

第二步：找到V1结点和剩下结点里面形成的边中最小的边

第三步：找V3和V1结点和剩下结点里面形成边中最小的边

第四步：接着上述步骤，寻找不形成回路的最小边



算法实现

//定义一个辅助数组
struct  {
     VertexType  adjvex;  // U集中的顶点
     VRType     lowcost;   // 边的权值
} closedge[MAX_VERTEX_NUM];
void MiniSpanTree_P(MGraph G, VertexType u)
{ //用普里姆算法从顶点u出发构造网G的最小生成树
  k = LocateVex ( G, u ); 
  for ( j=0; j<G.vexnum; ++j )  // 辅助数组初始化
     if (j!=k)  
         closedge[j] = { u, G.arcs[k][j].adj };  
  closedge[k].lowcost = 0;  // 初始化，U＝{u}
  for (i=1; i<G.vexnum; ++i) {//选择其余n-1个顶点
  }
}

算法分析和评价

• 时间复杂度：O(n**2**) , 与网中的边数无关
• 适用于求边稠密的网的最小生成树

  Kruscal算法（不要求掌握）

  算法思想：
  最小生成树上边权值之和最小，应使树上每一条边的权值尽量小。
  

  简单的来讲就是在不构成环路的情况下依次选择最小的边

直接看例题：

还是这张图

第一步：找到最短的边，也就是V1-V3=1

第二步：找第二短的边

第三步：后面依次类推



算法分析

• 时间复杂度：O( elog*2**e )
• 适合于求边稀疏的网的最小生成树

6.5 拓扑排序

相关概念：

其实简单来讲就是保证有向图中的节点，如果节点V0能通过连通到达V1，则V1一定不能通过连通到达V0

AOV(Activity On Vertices)网：

有向图表示工程，顶点表示活动。
有向边<vi,vj>表示活动vi必须先于活动vj进行,其中vi是vj的直接前驱，vj是vi的直接后继。
若从顶点vi到vk有一条路径，则vi是vk的前驱、vk是vi的后继。

拓扑排序的实现步骤

算法思想

不多bb，直接看例子，判断下面这张图是否满足是一个AOV网 只需要记住一点，依次删除入度为0的结点和相应的边

如果最后所有的边和点都能删除完，那么说明这个图就是一个AOV网
根据删除的顺序得到下列的拓扑排序：

这里比如C2和C3是同时删除的，所以C2也可以在C3前面逻辑结构上：拓扑序列不唯一

代码实现

 Staus TopologicalSort(ALGraph G)      // 有向图G采用邻接表存储
｛ FindInDegree(G, indegree)   //对各顶点求入度indegree[0..vexnum-1]
     InitStack(s);
     for(i=0; i<G.vexnum; ++i)  if (!indegree[i])  push(S, i); 
     count=0;   //对输出顶点计数
     while(!StackEmpty(S))
    {  pop(S,i); printf(i,G.vertices[i].data); ++count;  //输出i号顶点并计数
       for(p= G.vertices[i].firstarc; p; p=p->nextarc)
      {   k=p->adjvex;   //对i号顶点的每个邻接点的入度减1
          if(!(--indegree[k]))  push(S,k);  //若入度为0，则入栈   ｝
      ｝
}
       if(count<G.vexnum) return ERROR;    //有回路
       else return OK;
 }

关键路径

AOE-网

AOE-网(Active On Edge)：在带权的有向无环图中，顶点表示事件，弧表示工程的一个活动，弧上权值表示活动持续的时间。用来估算工程完成时间。
源点：入度为0的顶点。
汇点：出度为0的顶点。
路径长度：AOE网中路径上各活动持续时间之和。
关键路径：路径长度最长的路径。

（1）完成工程的最短时间是从开始点到完成点的最长路径的长度。 （2）关键路径的改变会影响整个工期。

假设任意两个结点j和k：

事件vj的最早发生时间ve(j)：从源点v0到vj的最长路径长度。
事件vj的最迟开始时间vl(j)：保证汇点vn-1在ve(n-1)时刻完成的前提下，事件v**j**最迟允许开始的时间。
活动ai的最早开始时间e(i)：从源点v0到vj的最长路径长度。
活动ai的最迟开始时间l(i)：是不推迟工程完成的前提下，该活动允许的最迟开始时间。
活动ai时间余量：l(i)-e(i)
关键活动：满足l(i)=e(i)的活动。关键路径上的活动都是关键活动。

其中dut(<j,k>)表示的是权值，也就是a**i**的值，也就是活动ai的活动时间。
记住下面的计算公式

• ve(k)=Max{ve(j)+dut()}
• vl(j)=Min{vl(k)-dut()}
• e(i)= ve(j);
• l(i)=vl(k)-dut()

求解关键活动

根据上述的定义，可以知道要求解关键活动，就要求所有活动的最早开始时间和最迟开始时间
而要求解这两个必须要先把每个事件的最早发生时间和最迟开始时间求出来。

以下面这张图为例：

第一步：首先利用如下两个公式写出每个事件的最早/迟开始时间

• ve(k) = Max{ve(j)+dut()}
• vl(j)=Min{vl(k)-dut()}

列出表格得

注意：源点的最早/迟开始时间都是0。
汇点的最早开始时间=最迟开始时间

第二步：用下面的两个公式写出每个活动的最早/迟开始时间

• e(i) = ve(j);
• l(i) = vl(k) – dut()

第三步：算出他们的差，差为0的就是关键活动
关键路径就是关键活动所在的所有点。
所以关键路径是V1 ,V2, V5, V7, V9和V1 ,V2 ,V5 ,V8 ,V9

代码实例

Status TopologicalSort(ALGraph G , Stack &T){ //T为拓扑序列顶点栈
    //采用邻接表存储结构，求各顶点的最早发生时间ve若G无回路，
    //则用T返回一个拓扑序列，并返回OK，否则返回ERROR
    FindInDegree(G,indegree); 
    count=0; 
    ve[0..G.vexnum-1]=0;
    InitStack(S); InitStack(T);
    while(!StackEmpty(S)){
        Pop( S, i) ;Push(T,i);count++;
        for(p= G.vertices[i].firstarc; p; p=p->nextarc) { 
            k=p->adjvex;  
            //删除弧、使新入度为0的顶点入栈
            if(! (--indegree[k]) Push(S,k);       //重新计算k的ve 
            if(ve[i]+*(p->info)>ve[k] ve[k]= ve[i]+*(p->info); 
        } // for
     } // while
     if(count<G.vexnum) return ERROR  else return OK;
     }// TopologicalSort
Status CriticalPath( ALGraph  G)
{ //G为有向图的邻接表存储结构，输出G的各项关键活动
    if (!TopologicalSort(G ,T)) return ERROR;
    vl[0..G.vexnum-1]=ve[G.vexnum-1] ;// 初始化vl
    while(!StackEmpty(T)){ //按逆拓扑序列求各顶点的vl
        Pop(T,j);
        for(p=G.vertices[j].firstarc;p;p=p->nextarc){
            k=p->adjvex;dut=*(p->info);   // dut<j,k> 
            if(vl[j]>vl[k]-dut)  
                vl[j]=vl[k]-dut;
        }
    }
    for(j=0;j<G.vexnum;j++){ //扫描每一条弧
        for(p= G.vertices[j].firstarc;p;p=p->nextarc){
              k=p->adjvex; dut=*(p->info);
               ee=ve[j];el=vl[k]-dut;  // 求弧的e 、 l  
               if(ee==el) printf(j,k,dut); 
        }// 输出关键活动
}// CriticalPath

关键路径分析说明

1. 任何一项活动持续时间的改变都会影响关键路径的改变。
2. 关键活动的速度提高是有限的,只有在不改变网的关键路径的情况下,提高关键活动的速度才有效。
3. 若网中有几条关键路径，那么，单是提高一条关键路径上的关键活动的速度，还不能导致整个工程缩短工期，而必须同时提高在几条关键路径上的活动速度。

6.6 最短路径

相关定义

最短路径问题：找一条路径使得沿此路径上各边上的权值总和最小。
两个节点之间的最短路径具有如下三个性质：

1. 第一条路径长度最短的路径的特点:

在这条路径上，必定只含一条弧，并且这条弧的权值最小。 （设为(v0,vj) )

1. 下一条路径长度次短的最短路径(v0…vk)的特点:

它只可能有两种情况:或者是直接从源点到该点(v0,vk) ； 或者是，从源点经过顶点vj，再到达该顶点(v0,vj,vk);

1. 一般情况下，假设S为已求的最短路径的顶点的集合，则下一条最短路径（设其终点为x）或者是弧(v0,x) ,或者是中间只经过S中的顶点而最后到达顶点x的路径。

   Dijkstra算法（重点掌握）

   核心思想：从源点出发不断找离源点最近的点

   算法思想：

2. 设立一个只有源点的集合为S={V**0**}

3. 然后从S集合出发寻找源点能到的达结点中距离源点最近的点，假设是**V****i**。
4. 把这个点归并到S集合当中，S={V0，Vi}
5. 重复2,3两步，直到找到所有距离源点最近的点。

例子

第一步：首先S={V0}
第二步：从V0出发找到距离V0最近的点，发现是V2（距离为10），此时S={V**0，V2**}
第三步：从V0，V2出发找距离V0最近的点，发现是V4（距离为30），此时S={V**0，V2，V4**}
第四步：重复上述步骤，得到如下的图

代码实例

void   ShortestPath(MGraph   G , int v0 , PathMatrix  &P , ShortPathTable  &D){
//用Dijkstra算法求从顶点v0到其余顶点的最短路径P[v]及其带权长度
//若P[v][w]为TRUE，则说明w是从v0到v的最短路径上的顶点。
    for(v=0;v<G.vexnum;v++){ 
        final[v]=FALSE;     // 初始化S、 D
        D[v]=G.arc[v0][v];  
        for(w=0;w<G.vexnum;w++)  P[v][w]=FALSE ;//设空路径
            if(D[v]<INFINITY) {  
                P[v][v0]= TRUE;
                P[v][v]=TRUE;  }  //若存在弧（v0,v)，则初始路径为{v0,v} 
    }    
    D[v0]=0; final[v0]=TRUE;   p[v0][v0]=TRUE; //将v0并入S中
    for(i=1;i<G.vexnum;i++){  //最多循环n-1次
        min= INFINITY;
        for(w=0;w<G.vexnum;w++)  //求路径长度最短者
            if(! final[w])           // w ∈V-S 
                if(D[w]<min ){ v=w ; min=D[w];}
        if(min< INFINITY){       // v是找到的路径长度最短的顶点，若v存在
            final[v]=TRUE ;      //  S=S⊔ {v}
            for(w=0;w<G.vexnum;w++) //修改D[w][和P[w]
                if (! final[w]&&(min+G.arc[v][w]<D[w])){
                    D[w]= min+G.arc[v][w]; 
                    P[w]=P[v]; P[w][w]=TRUE; // P[w]=P[v] ⊔ {w}
                }// if
        }//for
    }

时间复杂度：O（n**2**)

还是不理解的可以看下面这两个链接

最短路径问题—-Dijkstra算法详解_William-CSDN博客_dijkstra
迪杰斯特拉算法详解及C语言实现

Floyd算法（不要求掌握）

看下面链接即可，掌握上面那个算法即可，这个只要了解一下。

弗洛伊德算法详解及C语言实现