图

图

1.基本概念

1.定义

1、图G由顶点集V和边集E组成

2、|V|表示图中顶点的个数，也称为图的阶

3、|E|表示图中边的条数

注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集

2.图的逻辑结构的应用

1.V：车站、E：铁路

2.V：用户、E：微信好友关系

3.无向图&有向图

1、无向图：即连接顶点的边是无方向的

2、有向图：即连接定点的边是有方向的

4.简单图&多重图

5.顶点的度&入度&出度

1、对于无向图：

顶点v的度是指依附于该顶点的边的条数，计为TD(v)

所有度之和 = 边的条数*2 = 2e

2、对于有向图：

1）入度：是以顶点v为终点的有向边的数目，计为ID(v)

2）出度：是以顶点v为起点的有向边的数目，计为OD(v)

3）顶点v的度 = 入度 + 出度；TD(v) = ID(v) + OD(v);

在具有n个顶点、e条边的有向图中：所有的入度之和 = 所有的出度之和 = e

6.顶点-顶点的关系描述

1、路径：

顶点Vq 到顶点Vp之间的一条路径是指经过的顶点序列

2、回路：

第一个顶点和最后一个顶点相同的路劲称为回路或者环

3、简单路径：

在路径序列中，顶点不重复出现的路径称为简单路径

4、简单回路：

除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路

5、路径长度：

路径上边的数目

6、

从顶点v出发到顶点u的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷

7、连通&强连通

1）无向图中，若从顶点v到顶点u有路劲存在，则称v和w是连通的

2）有向图中，若从顶点v到顶点w，从顶点w到顶点v之间都有路径，则称为这两个顶点是强连通的

7.连通图&强连通图

1.连通图

若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图图

注意：对于n个顶点的无向图G：

1）若G是连通图，则至少要n - 1条边

2）若G是非连通图，则最多可能有 （[n - 1)* (n - 2)]/2 (n - 1个顶点两两相连有多少中可能的结果)

2.强连通图

若图中任何一对顶点都是强连通的，则称此图为强连通图

注意：对于n个顶点的有向图G

若G是强连通图，则最少有n条边（形成回路）

8.子图&生成子图

1.子图：

1）设有两个图G = （V，E） 和G2 = （V2，E2），若V2是V的子集，E2是E的子集，则称G2是G的子图

2）并非任意挑几个点、几条边都能构成子图，必须保证每条边连接两个顶点，否则不是子图

2.生成子图

若有满足V（G） = V（G2）的子图G2，责成其为G的生成子图（包含了原图中的所有顶点，但是可以去除一些边）

9.连通分量

1.极大连通子图：子图必须连通，且包含尽可能多的顶点和边

2.无向图中的极大连通子图称为连通分量

3.有向图中的极大连通子图称为有向图的强连通分量

10.生成树

1、极小连通子图：子图必须连通，边尽可能的少

2、无向连通图的生成树是包含图中全部顶点的一个极小连通子图；若图中顶点数为n，则它的生成树含有n - 1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

11.生成森林

在非连通图中，连通分量的生成树构成了非连通图的生成森林。

12.边的权、带权图/网

13.几种特殊形态的图

无向完全图&有向完全图：

稀疏图&稠密图

14.总结

2.图的存储结构

1.邻接矩阵法

1.图示

2.代码

3.求顶点的度、入度、出度

1）无向图：第i个节点的度 = 第i行（列）的非零元素个数

2）有向图：

第i个节点的出度 = 第i行的非零元素个数

第i个节点的入度 = 第i列的非零元素个数

第i个节点的度 = 第i行、第i列的非零元素个数之和

3）邻接矩阵法求顶点的度/出度/入度的时间复杂度为O(|V|)

4.性能分析

空间复杂度O(n^2)——只和顶点数相关，和实际的边数无关

适合用于存储稠密图

无向图的邻接举证是对称矩阵，可以压缩存储（只存储上三角区/下三角区)

5.邻接矩阵的性质

2.邻接表

1.图示

2.代码

3.注意

4.总结

3.十字链表

存储有向图

4.邻接多重表

存储无向图

总结

4.广度优先遍历BFS

1.算法思想

1.找到与一个顶点相邻的所有顶点

2.标记哪些顶点被访问过

3.需要一个辅助队列

FirstNeighbor(G,x);//求图G中顶点x的第一个邻接点，若有，返回顶点号
NextNeighbor(G,x,y);//假设图G中顶点y是顶点x的一个邻接点，，返回除y以外的顶点x的县一个邻接点的顶点号

2.代码实现

bool visited[MAX_VERTEX_NUM];        //访问标记数组，初值为false

//广度优先遍历
//从顶点v出发
void BFS(Graph G, int v){
  visit（v);
  visited[v] = true;
  Enqueue(Q,v);                //顶点v入队列Q
  while(!isEmpty(Q)){
    Dequeue(Q,v);            //顶点v出队列
    for(w = FirstNeighbor(G,v); w >= 0; w = NewtNeighbor(G,v,w)){
      if(!visited[w]){
        visit(w);
        visited[w] = true;
        Enqueue(Q,w);
      }
    }
  }
}

邻接矩阵的遍历序列唯一，邻接表的遍历序列不唯一

以上代码如果是非连通图，则无法访问所有的节点，解决方法如下：

void BFSTraverse(Graph G){
  for(int i = 0; i < G.vexnum; ++i){
    visited[i] = false;            //访问数组初始化
  }
  InitQueue(Q);
  for(int i = 0; i < G.vexnum; ++i){
    if(!visited[i]){
      BFS(G,i);
    }
  }
}

3.算法度分析

访问边和访问顶点才耗费时间复杂度

4.广度优先生成树

1、根据广度优先遍历的过程实现的，此时图中没有回路

2、广度优先生成树由广度优先遍历过程确定。由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树也不唯一

3、邻接矩阵存储的图，其广度优先生成树是唯一的

5.深度优先遍历DFS

1.算方法思想

类似于树的先根遍历

2.代码实现

bool visited[MAX_VERTEX_NUM];        //访问标记数组

void DFS(Graph G, int v){
  visit(v);
  visited[v] = true;
  for(w = FirstNeighbor(G,v); w >=0 ; w = NextNeighor(G,v,w)){
    if(!visited[w]){
      DFS(G,w);
    }
  }
}

同样，对于非连通图，上面代码无法遍历全部节点，解决方法如下：

void DFSTraverse(Graph G){
  for(int i = 0; i < G.vexnum; ++i){
    visited[i] = false;        //初始化话访问数组
  }
  for(int i = 0; i < G.vexnum; ++i){
    if(!visited[v]){
      DFS(G,v);
    }
  }
}

3.复杂度分析

1、空间复杂度

2、时间复杂度

注意：同一个图的邻接矩阵表示方式唯一，因此图的深度优先遍历序列唯一；同一个图的邻接表表示方式不唯一，因此深度优先遍历序列不唯一

4.深度优先生成树

基于深度优先遍历过程实现的，此时图中的不再有回路；

如果图示非连通的，则会生成深度优先生成森林，有几个连通分量，会生成几个深度优先生成森林

5.图的遍历和图的连通性

1.无向图

DFS/BFS函数调用次数 = 连通分量数

2.有向图

1）若从起始点到其它顶点都有路径，则只需要调用1次DFS/BFS

2）对于强连通图，从任一顶点出发都只需要调用1次DFS/BFS

6.最小生成树

1.基本概念

1、对于一个带权连通无向图G = （V，E），生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。

2、设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树（MST）

3、最小生成树可能有多个，但边的权值之和总是唯一且最小的

4、最小生成树的边数= 顶点数 - 1。砍掉一条则不连通，增加一条则会出现回路

5、入股一个连通图本身就是一棵树，则其最小生成树就是它本身

6、只有连通图才有生成树，非连通图只有生成森林

2.求最小生成树

1.Prim算法

2.Kruskal算法

3.Prim算法

1、从某一个顶点开始构建生成树；

2、每次将代价最小的新顶点纳入生成树，知道所有顶点都纳入为止

4.Kruskal算法

1、每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选）

2、直到所有节点都连通

注意：此算法实现要使用并查集的知识

7.最短路径算法

Q1：单源最短路径问题：BFS（无权图） + Dijkstra算法（带权图、无权图）

Q2：每对顶点间最短路径：Floyd算法（带权图、无权图）

1.BFS求无权图单源最短路径

//无权值，所以d[w] = d[u] + 1;即可满足要求
void BFS_MIN_Distance(Graph G, int u){
  //d[i]表示从u到i节点的最短路径
  for(int i = 0; i < G.vexnum; ++i){
    d[i] = MAX_INT;    //初始化路径长度
    path[i] = -1;    //最短路径从哪个顶点过来
  }
  d[u] = 0;
  vinited[u] = true;
  EnQueue(Q,u);
  while(!isEmpty(Q)){
    Dequeue(Q,u);
    for(w = FirstNeighbor(G,u); w>=0; w = NextNeighbor(G,u,w)){
      if(!visited[w]){
        d[w] = d[u] + 1;
        path[w] = u;
        visited[w] = true;
        Enqueue(Q,w);
      }
    }
  }
}

通过d[]数组和path[]数组可以找到到达某一节点的最短路径长度以及路径

BFS算法的缺点是，对于带有权值的图，是没办法找到最短路径的

2.Dijkstra迪杰斯特拉算法

依次执行上述步骤，最终会得到一条如下路径：

步骤总结

注意：如果带权图中有负值，则会导致迪杰斯特拉算法失效

3.Floyd弗洛伊德算法

使用了动态规划思想：将问题求解分为多个阶段：

对于n个顶点的图G，求任意一对顶点Vi->Vj之间的最短路径可以分为以下几个阶段：

1）初始：i和j之间不允许在其他顶点中转，最短路径是？

2）若允许在V0中转，最短路径是？

3）若允许在V0，V1中转，最短路径是？

4）若允许在V0，V1，V2中转，最短路径是？

……

5）若允许在V0，V1，……Vn-1中转，最短路径是？

找最短路径

代码实现

时间复杂度O(n^3)，空间的复杂度O(n^2)

Floyd算法可以解决带负权值的图的最短路径问题

通过Path矩阵可以找到完整的最短路径

Floyd算法不能解决带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径

4.总结

8.有向无环图描述表达式

1.有向无环图DAG

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图

2.DAG描述表达式

1.问题

表达式重复，因此会出现浪费地址空间的问题

2.解决方式

合并重复的部分

3.求最少顶点数

3.拓扑排序

1、DAG图的第二个应用

2、AOV网：用DAG图表示一个工程。顶点表示活动，有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行；（AOV网中不存在回路）

3、拓扑排序：找到做事的先后顺序

4、拓扑排序的实现：

1）从AOV网中选择一个没有前驱（入度为0）的顶点并输出

2）从网中删除该顶点和所有以它为起点的有向边

3）重复1、2直到当前AOV网为空或当前网中不存在无前驱的顶点为止

5、如果图中有回路，则无法实现拓扑排序，因为在回路中，无法找到入度为0的顶点

6、代码实现

//时间复杂度 O(V + E)

#define MaxVertexNum 100         //图中顶点数目的最大值
typedef struct ArcNode{            //边表节点
  int adjvex;                                //该弧指向的顶点的位置
  struct ArcNode *nextarc;    //指向下一条弧的指针
}ArcNode;

typedef struct VNode{        //顶点表节点
  VertexType data;            //顶点信息
  ArcNode *fristarc;        //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];        

typedef struct{
  AdjList vertices;            //邻接表
  int vexnum,arcnum;        //图的顶点数和弧数
}Graph;                                    //Graph是以邻接表存储的


int indegree[];            //用于记录当前顶点的入度
int print[];                //记录拓扑排序序列


bool TopologicalSort(Graph G){
  InitStack(S);                //初始化栈，存储入度为0的顶点
  for(int i = 0; i < G.vexnum; i++){
    if(indegree[i] == 0){
      Push(S,i);            //将所有入度为0的顶点进栈
    }
  }
  int count = 0;             //技术，记录当前已经输出的顶点数
  while(!IsEmpty(S)){
    Pop(S,i);
    print[count++] = i;            //输出顶点i
    for(p = G.vertices[i].firstarc; p; p=p->nextarc){
      //将所有i指向的顶点的入度减1，并且将入度减为0的顶点入栈
      v = p->adjvex;
      if(!(--indegree[v])){
        Push(S,v);
      }
    }
  }
  if(count < G.vexnum){
    return false;        //排序失败，有向图中有回路
  }
  else{
    return true;        //拓扑排序成功
  }
}

4.逆拓扑排序

1.逆拓扑排序的实现

1）从AOV网中选择一个没有后继（出度为0）的顶点并输出

2）从网中删除该顶点和所有以它为终点的有向边

3）重复1、2直到当前的AVO网为空

2.代码实现和拓扑排序一样，拓扑排序考虑入度，逆拓扑排序考虑出度

3.值得注意的是，拓扑排序，通过邻接表很方便实现，在删除某个节点时，可以很方便找到当前节点指向的下一个节点，但是如果通过邻接表实现逆拓扑排序的话，如果想要找到指向当前节点的所有节点，只有通过遍历才能实现，所以效率低下。可以考虑通过邻接矩阵实现，或者通过逆邻接表实现

4.逆邻接表中保存的是指向当前节点的节点，邻接表中保存的是指向后继节点的信息

5.深度DFS算法实现拓扑排序

1、深度优先遍历算法，遍历的顺序就是逆拓扑排序

2、将逆拓扑排序倒置，则编程了拓扑排序

3、如果有回路时，需要判断是否有回路，如果有回路，则无拓扑排序，实现方法，可以通过并查集的思想实现，在DFS之前，先检查有无环存在

9.关键路径

1.AOE网

1、在带权有向图中，以顶点表示时间，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网

2、AOV网用顶点表示活动，AOE网用边表示活动

3、AOE网具有以下两个性质：

1）只有在某顶点所代表的时间发生后，从该顶点出发的各有向边所代表的活动才能开始；

2）只有进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的时间才能发生。另外，有些活动可以并行进行。

4、如下图

2.关键路径

1、从源点到汇点的有向路径可能有多条，在所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动

2、完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长

3、时间余量

3.求关键路径的详细步骤

1、关键活动的特性：关键果冻耗时增加，则整个工程的工期将增长

2、缩短关键活动的时间，可以缩短整个工程的工期

3、当缩短到一定程度时，关键活动可能会变成非关键活动

3、可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

4.步骤框架