图

由顶点集V与边集E组成，记为G(V，E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中边的集合

|V|表示图G中顶点个数，又称图的阶
|E|表示图G中边的条数
图必非空（即顶点集V非空），但边集E可以为空。

图的基本概念

无向图与有向图

若E是无向边的有限集合，则图G为无向图，即边(v，w)等价于边（w，v）

无向图中的度：顶点v的度是指依附于该顶点的边的条数，记为TD(v)
无向图的全部顶点的度之和等于边数的2倍

若E是有向边（又称弧）的有限集合，则图G为有向图，弧是顶点的有序对，记为<v，w>，v就是弧尾，w是弧头

入度：以顶点v为终点的有向边的条数，记为ID(v);
出度：以顶点v为起点的有向边的条数，记为OD(v);
顶点的度=入度与出度之和，即TD(v)=ID(v)+OD(v)；

简单图与多重图

简单图：不存在重复边，不存在顶点到自身的边。

多重图：图中某两个结点之间的边数多于一条，允许顶点通过同一条边和自己关联。

顶点与顶点的关系

路径：顶点V_p到顶点V_q的一条路径，指一个顶点序列，V_p,V_i1,V_i2,,,V_im,V_q 。

顶点之间可能不存在路径

回路：第一个顶点和最后一个顶点相同的路径称为回路或环。

简单路径：路径序列中，顶点不重复出现的路径
简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路

路径长度：路径上边的数目

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

连通图

在无向图中，若顶点v到顶点w有路径存在则称v与w连通
在有向图中，若顶点v到顶点w和从w到v之间都有路径，则称v与w强连通

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

对于n个顶点的无向图G，若G为连通图，则最少有n-1条边，非连通则最多有$C_{n-1}^2$条边

若图G中任意一对顶点强连通，则称此图为强连通图，有n个顶点，则最少有n条边(形成回路)

图与图的关系

子图：

若有满足V(G’)=V(G)的子图G’，则称该子图为G的生成子图

连通分量：无向图中的极大连通子图(子图必须连通且包含尽可能多的顶点和边)称为连通分量

强连通分量与连通分量类似，其描述的对象为有向图

生成树：包含途中全部顶点的一个极小连通子图(边尽可能的少，但要保持连通)，且并不一定唯一。

若图中顶点数为n，则其生成树含有n-1条边，对于生成树而言，砍去一条边，就会变成非连通图，加上一条边就会产生回路
n个顶点的图，若|E|>n-1，则一定有回路

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

带权路径长度：一条路径上所有边的权值之和，称为该路径的带权路径长度

有向完全图与无向完全图

无向完全图：无向图中任意两个顶点之间都存在边

若顶点数|V|=n，则$|E|= n(n-1)/2$

有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧

若定点数|V|=n，则$|E| = n(n-1)$

确保无向图为连通图的方法：取n-1个顶点构成完全无向图，再添一条边用于第n个结点的连通

图的存储

邻接矩阵(顺序)

0表示两个结点相互不邻接(无边)
1表示两个结点相互邻接(有边)

1
2
3
4
5
6


#define MaxVertexNum 100
typedef struct{
    char vex[MaxVertexNum];//顶点表
    int Edge[MaxVertexNum][MaxVertexNum];
    int vexnum,arcnum;//图的当前顶点数与边数
}MGraph;//不带权

1
2
3
4
5
6
7
8
9


#define MaxVertexNum 100
#define INFINITY //无穷大常量
typedef int EdgeType;
typedef char VertexType;
typedef struct{
    VertexType vex[MaxVertexNum];//顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];//边权
    int vexnum,arcnum;//图的当前顶点数与边数
}MGraph;

对于无向图的邻接矩阵：

第i个结点的度 = 第i行/列的非零元素个数

对于有向图的邻接矩阵：

第i个结点的出度 = 第i行的非零元素个数
第i个结点的入度 = 第i列的非零元素个数
第i个结点的度 = 第i列i行所有非零元素个数之和

空间复杂度O(|V|²)，只与顶点数有关，和实际边数无关

适合用于存储稠密图

无向图的邻接矩阵是对称矩阵且唯一，所以可以压缩存储（存上三角或下三角）

性质：

邻接矩阵A[i][j]表示顶点i到顶点j长度为n的路径的数目
只要确定了顶点编号，图的邻接矩阵表示方式唯一

邻接表(顺序+链式)

1
2
3
4
5
6
7
8


typedef struct VNode{
    VertexType data;//顶点信息
    ArcNode *first;//第一条边/弧
}Vnode,AdjList[MaxVertexNum];
typedef struct ArcNode{
    int adjvex;//边/弧指向哪个结点
    struct ArcNode *next;//指向下一条边的指针
}ArcNode;

对于无向图：由于其特性，每条边在表中将重复出现两次，故空间复杂度O(|V|+2|E|)

对于有向图：每条边只会出现一次，故空间复杂度O(|V|+|E|)

图的邻接表表示方式不唯一
适合存储稀疏图

十字链表(仅有向图)

顺着顶点结点的绿色指针firstout走到尾可以找到所有从结点向外发射的所有弧
顺着顶点结点的橙色指针firstin走到尾可以找到所有指向这个结点的弧

例：找A->B与A->C，即寻找以A为弧尾的所有弧，从顶点结点出发根据firstout指针依次寻找，弧结点的headvex将指明弧尾A指向了什么弧头

空间复杂度：O(|V|+|E|)，仅适用于有向图

邻接多重表(仅无向图)

空间复杂度：O(|V|+|E|)，每条边只对应一份数据

图的操作

图的广度优先遍历(BFS)

类似二叉树的层序遍历算法

找到与一个顶点相邻的所有顶点
标记哪些顶点被访问过
需要一个辅助队列
核心操作：
- FirstNeighbor(G,x)：该操作返回G中顶点x的第一个邻接点号，没有该顶点或无邻接点返回-1
- NextNeighbor(G,x，y)：该操作返回x的除邻接点y以外的下一个邻接点顶点号，若y是x的最后一个结点，返回-1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


bool visited[MAX_VERTEX_NUM];	//初始值设为false
void BFS(Graph G,int v){ 		//从顶点v出发广度优先遍历图G
    visit(v); 					//访问初始结点v
    visited[v]=True;			//对v作已访问标记
    EnQueue(Q,v);				//顶点入队
    while(!isEmpty(Q)){
        DeQueue(Q,v);			//顶点v出队
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
            //检测v所有邻接点
            if(!visited[w]){
                visit(w);
                visited[w]=True;
                EnQueue(Q,w);
            }
        }
    }
}//若图为非连通图则无法遍历完所有结点
//可以再遍历寻找visited[]中的false结点，再对其进行BFS,改进如下
void BFSTraverse(Graph G){
    for(i=0;i<G.vexnum;++i){
        visited[i]=False;//标记数组初始化
    }
    InitQueue(Q);//辅助队列初始化
    for(i=0;i<G.vexnum;++i){
        if(!visited[i])//对每一个连通分量调用一次BFS
            BFS(G,i);
    }
}//对于无向图，调用BFS函数的次数=l

空间复杂度：需要设置辅助队列，为O(|V|)

时间复杂度：对于邻接表存储方式，为O(|V|+|E|)，对于邻接矩阵，为O(|V|²)

图的深度优先遍历(DFS)

与树的先根遍历类似，使用递归实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


bool visited[MAX_VERTEX_NUM];//访问标记数组
void DFSTraverse(Graph G){
    for(v=0;v<G.vexnum;++v){
        visited[v]=false;//初始化标记
    }
    for(v=0;v<G.vexnum;++v){
        if(!visited[v]){//从第一个未访问数据开始遍历
            DFS(G,v); //开始深搜
        }
    }
}
void DFS(Graph G,int v){
    visit(v);//从顶点v出发开始遍历
    visited[v]=true;//标记访问
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
        if(!visited[w]){ 
        	DFS(G,w); //不断向深处递归
    	}
    }
}

空间复杂度来源于函数调用栈，最坏递归深度为O(|V|);
时间复杂度=访问各节点所需时间+探索各条边所需时间
邻接矩阵存储的图时间复杂度为O(|V|²)
邻接表存储的图时间复杂度为O(|V|+|E|)

图的应用

最小生成树(MST)

使图的所有生成树集合中，取所有边的权值之和最小的数作为最小生成树

最小生成树不唯一，权值之和唯一
最小生成树的边数等于顶点数-1

Prim算法

从某一个顶点开始构建生成树，每次将代价最小的顶点纳入生成树直到所有顶点全部纳入为止。

初始化：向空树添加图中任意结点
循环：从图中选择还未加入到树中，离树最近，且代价最小的结点与边
树中已含所有结点，退出循环

时间复杂度O(|V|²)，不依赖于边的个数，适用于边稠密图，即边数|E|接近|V|²的图

Kruskal算法

每次选择一条权值最小的边，使这条边的两头连通（原本已经连通就不选，直至所有结点连通。

初始化：将图初始化为n个顶点无边的非连通图T，此时每个节点都是一个连通分量
循环：按照边的权值，每次选择一条未被选过且最小的边，若该边两头的顶点落在不同的连通分量上(即不会产生回路)，则加入到T中，否则舍弃选择下一条边
直到所有结点落在一个连通分量上，退出循环

判断是否连通属于并查集的范畴
时间复杂度O(|E|log~2~|E|)，依赖于边数，适用于边稀疏而顶点较多的图

单源最短路径问题

给定一个源点，求解源点到各顶点间的最短距离问题

BFS算法

仅适用于无权图或所有边权值相同的图

基于广度优先遍历对visit函数进行改动即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


//d[i]表示从u到i的最短路径
void BFS_MIN_Distence(Graph G,int u){
    for(i=0;i<G.vexnum;++i){
        d[i]=Infinity； 
        path[i]=-1;
    }
    d[u]=0;
    visited[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]){	//w为u的尚未访问的邻接顶点
                d[w]=d[u]+1;	//路径长度+1
                path[w]=u;		//最短路径应从u到w
                visited[w]=Ture;//设置已访问
                EnQueue(Q,w);	//w入队
            }
        }
    }
}

Dijkstra算法

适用于带权图与无权图，使用dist[j]，表示源点到顶点j的最短距离，使用arc[i][j]表示表示有向边<i,j>的权值，集合S保存顶点

初始化：dist[i]=arc[0][i]，即初态下，dist[]将源点的邻接点的弧作为各源点邻接点的最短路径，集合S仅含源点
从不在集合S的顶点集中选出V_j，满足dist[j]在dist[]中最小，并将该顶点加入到集合S
查看V_j顶点的所有邻接点V_k，循环判断dist[j]+arc[j][k]与dist[k] 的大小关系，小于则说明源点通过V_j可获得源点到V_k的最短路径，直到所有邻接点V_k都比较完毕
重复2，3步骤直到所有结点加入集合S

基于贪心策略，该算法时间复杂度为O(|V|^2^)

Dijkstra算法并不适用于负权值带权图

Floyd算法

适用于带权、无权图、可解决负权图

基于动态规划，对于一对结点V_j ，V_i，用A[i][j]表示其最短距离

初始时将arc[i][j]作为其最短距离
随后尝试在路径中添加中间结点V_k，若添加后的距离变短，更新路径序列值
- 即$A^{k}[i][j]=min(A^{k-1}[i][j],A^{k-1}[i][k]+A^{k-1}[k][j])$
经过n次迭代后，方阵A中保存了任意一对结点的最短路径信息

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


for(int k=0;k<n;k++){
    for(int i=0;i<n;i++){//考虑以Vk作为中转点
        for(int j=0;j<n;j++){//遍历矩阵
            if(A[i][j]>A[i][k]+A[k][j]){
                A[i][j]=A[i][k]+A[k][j];//以Vk为中转点的路径更短
                path[i][j]=k;
            }
        }
    }
}