前言

“图”学习提纲。

代码模板

图的C++语言描述实现模板_夜悊的博客-CSDN博客

图的基本概念

依据相关定义：

图：点，边

注意：图不可以为空图。即必须有点（有穷非空），不必须有边

无向图，有向图：无向边，有向边/弧：弧尾，弧头
简单图，多重图

数据结构中一般讨论简单图：不存在顶点到自身的边，不存在重复的边

完全图：无向完全图，有向完全图

无向完全图：边数为n(n-1)/2。n为点数
有向完全图：边数为n(n-1)。n为点数

稀疏图，稠密图

稀疏和稠密是相对而言的模糊概念

带权图/网：权
子图：生成子图

依据点与边的关系：

点的度，入度，出度

对无向图：点的度的和=边数×2
对有向图：点的入度的和=点的出度的和=边数；度=入度+出度

有向树
路径，路径长度，回路/环：简单路径，简单回路/环，最短路径/距离

若图有n个点，大于n-1条边，则存在回路

连通，连通图，非连通图，极大连通子图/连通分量

若图有n个点，小于n-1条边，则为非连通图

强连通，强连通图，强非连通图，极大强连通子图/强连通分量

注意：对无向图，为连通性；对有向图，为强连通性

极小连通子图/生成树，生成森林

图的生成树有n-1条边，有n-1条边不一定是图的生成树。n为点数

图的存储结构

邻接矩阵

类型：顺序存储结构

组成：

点数
边数
点一维数组：存储点数据
边二维数组：存储数值，可存储权值

创建的时间复杂度：

O(v²)。v为点数
O(v+v²+e) 。v为点数，e为边数。v为初始化点一维数组，v²为初始化边二维数组，e为给边赋值

空间复杂度：

O(v²)。v为点数
O(v+v²)。v为点数。v为点一维数组，v²为边二维数组

适用：稠密图

相关性质：

无向图：对称（可压缩存储上/下三角元素）；有效数值（如“1”表示点间存在边）数为边数的两倍；第i行或第i列的元素和为点i的度
有向图：不对称；有效数值数为边数；第i行的元素和为点i的出度，第i列的元素和为点i的入度
求点间是否有边：O(1)（依据点数据/下标取值）
求点的邻边/邻接点：O(v)。v为点数（遍历点数据所在的一行）
有权图：点到点有路径，数值为权值；点到当前点无路径，数值为0；点到其他点无路径，数值为无穷大
存在邻接矩阵A，A的n次方的元素：A的n次方[i][j]=点i到点j中，长度为n的路径数
邻接矩阵唯一

邻接表

类型：顺序和链式存储结构；关注点

组成：

点数
边数
点表：顺序存储结构；一维数组；单链表的头结点：存储点数据（当前点）和当前点指向第一个边结点的指针
（出）边表：链式存储结构；单链表；单链表的非头结点：存储点数据（其他邻接点）和当前点指向其他边结点的指针，可存储权值

创建的时间复杂度：

O(v+e) 。v为点数，e为边数。v为初始化点表，e为初始化边表

空间复杂度：

无向图：O(v+2e)。v为点数，e为边数
有向图：O(v+e)。v为点数，e为边数

适用：稀疏图

相关性质：

求点的出度：遍历该点的链表
求点的入度：遍历所有点的链表；使用逆邻接表
求点间是否有边：O(v)。v为其他邻接点数。（遍历该点的链表）
求点的邻边/邻接点：O(v)。v为其他邻接点数。（遍历该点的链表）
邻接表不唯一

邻接多重表

类型：无向图的顺序和链式存储结构；关注边

组成：

点表：顺序存储结构；单链表的头结点；存储点数据（当前点）和当前点指向第一个边结点的指针
边表：链式存储结构；单链表的非头结点；存储标志（可标记该边是否被搜索过），点i数据，点i（当前点）指向其他边结点的指针，点j数据（其他点），点j指向其他边结点的指针（“多重”的体现），可存储权值

空间复杂度：

无向图：O(v+2e)。v为点数，e为边数

相关性质：

易插入或删除边（相比于邻接表操作多个边结点，只需操作一个边结点）

十字链表

类型：有向图的顺序和链式存储结构

组成：

点表：顺序存储结构；单链表的头结点；存储点数据（当前点），以当前点为弧头的第一个边结点的指针，以当前点为弧尾的第一个边结点的指针
边表：链式存储结构；单链表的非头结点；弧尾点（当前点）数据，弧头点（其他点）数据，弧尾点（当前点）指向弧头相同的边结点的指针，弧头点（其他点）指向弧尾相同的边结点的指针，可存储权值

创建的时间复杂度：

O(v+e) 。v为点数，e为边数。v为初始化点表，e为初始化边表

空间复杂度：

有向图：O(v+e)。v为点数，e为边数

相关性质：

易求点的入度和出度
图的十字链表不唯一，十字链表唯一确定图

边集数组

类型：顺序存储结构；关注边

组成：

点一维数组：存储点数据
边一维数组：存储点（起点）数据，存储点（终点）数据，可存储权值

相关性质：

求点的度：遍历边一维数组
适合依次操作边，不适合操作点

图的遍历算法

深度优先遍历（DFS）概述

类似二叉树先序遍历
是递归过程
图的邻接矩阵唯一，广度优先遍历序列唯一；图的邻接表不唯一，广度优先遍历序列不唯
保留遍历的边，删除未遍历的边，可形成深度优先遍历生成树（对连通图）或深度优先遍历生成森林（对非连通图）

深度优先遍历（DFS）的过程

初始化标记数组（空间复杂度：O(v)。v为点数）
循环遍历点表，标记每点为未访问
循环遍历点表，若点的标记为未访问，则深度优先遍历图g，从点v开始（连通图执行一次，非连通图执行多次。非连通无向图执行连通分量数次，非强连通有向图的非强连通分量不一定能遍历所有点）
深度优先遍历g，从v开始
访问v（二叉树先序遍历的体现）
标记v已访问
循环获取v的邻接点w
循环中，若w的标记为未访问，则深度优先遍历g，从w开始（递归的体现）

时间复杂度：依据存储结构

对邻接矩阵：遍历点数×查找每点的邻接点的时间=O(v×v)=O(v²)。v为点数（理解：遍历每一行）
对邻接表：遍历点数+查找每点的邻接点的时间=O(v+e)。v为点数，e为边数（理解：遍历点表和边表，因为是链式存储结构）

空间复杂度：O(v)。v为点数/辅助空间规模/递归栈规模

伪代码：

bool visited[MAX_VERTEX_NUM];	//访问标记数组
void DFSTraverse(Graph G){		//对图G进行深度优先遍历
	for(int v=0;v<G.vexnum;++v)	
		visited[v] = FALSE;		//初始化已访问标记数据
	for(int v=0;v<G.vexnum;++v)	//本代码是从v=0开始遍历
		if(!visited[v])
			DFS(G,v);
}

void DFS(Graph G,int v){		//从顶点v出发，深度优先遍历图G
	visit(v);					//访问顶点v
	visited[v] = TRUE;			//设已访问标记
	for(w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
		if(!visited[w]){		//w为v的尚未访问的邻接顶点
			DFS(G,w);
		}	//if
}

广度优先遍历（BFS）概述

类似二叉树层序遍历
是迭代过程
图的邻接矩阵唯一，广度优先遍历序列唯一；图的邻接表不唯一，广度优先遍历序列不唯一
保留遍历的边，删除未遍历的边，可形成广度优先遍历生成树（对连通图）或广度优先遍历生成森林（对非连通图）
类似迪杰斯特拉（Dijkstra）单源最短路径算法
类似普里姆（Prim）最小生成树算法

广度优先遍历（BFS）的过程

初始化标记数组（空间复杂度：O(v)。v为点数）
循环遍历点表，标记每点为未访问
初始化队列（空间复杂度：O(v)。v为点数）
循环遍历点表，若点的标记为未访问，则广度优先遍历图g，从点v开始（连通图执行一次，非连通图执行多次。非连通无向图执行连通分量数次，非强连通有向图的非强连通分量不一定能遍历所有点）
广度优先遍历g，从v开始
访问v
标记v已访问
v入队
当队列不为空时，循环
循环中，获取v的所有邻接点w（迭代的体现）
循环中，若w的标记为未访问，则访问w，标记w已访问，w入队（二叉树层序遍历的体现）

时间复杂度：依据存储结构

对邻接矩阵：遍历点数×查找每点的邻接点的时间=O(v×v)=O(v²)。v为点数（理解：遍历每一行）
对邻接表：遍历点数+查找每点的邻接点的时间=O(v+e)。v为点数，e为边数（理解：遍历点表和边表，因为是链式存储结构）

空间复杂度：O(v)。v为点数/辅助空间规模

伪代码：

bool visited[MAX_VERTEX_NUM];		//访问标记数组
bool BFSTraverse(Graph G){			//对图G进行广度优先遍历
	for(int i=0;i<G.vexnum;++i)
		visited[i] = FALSE;			//访问标记数组初始化
	InitQueue(Q);					//初始化辅助队列Q
	for(int i=0;i<G.vexnum;++i){	//从0号顶点开始遍历
		if(!visited[i])				//对每个连通分量调用一次BFS
			BFS(G,i);				//vi未访问过，从vi开始BFS
	}
}
 
void BFS(Graph G,int v){			//从顶点v出发，广度优先遍历图G
	visit(v);						//访问初始顶点v
	visited[v] = TRUE;				//对v做已访问标记
	EnQueue(Q,v);					//顶点v入队列Q 
	while(!isEmpty(Q)){		
		DeQueue(Q,v);				//顶点v出队列 
		for(w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))	
									//检测v所有邻接点
			if(!visited[w]){		//w为v的尚未访问的邻接顶点 
				visit[w];			//访问顶点w 
				visited[w] = TRUE;	//对w做已访问标记
				EnQueue(Q,w);		//顶点w入队列 
			}//if
	}//while
}

图的应用

最小（代价）生成树概述

概念：

对连通图
是极小连通子图
有图的所有点，尽量少的边
若少一条边，则成非连通图；若多一条边，则存在回路

性质：

边数=点数-1
树形不唯一。若图中各边权值不相等，则唯一；若图中存在相等权值的边，构造时都被加入树中，则唯一
边权值的和唯一且最小

构造算法：基于贪心思想；对无向图

普里姆（Prim）算法
克鲁斯卡尔（Kruskal）算法

构造算法的伪代码：

GENERIC MST(G){
	T=NULL;
	while T未形成一棵生成树；
		do 找到一条最小代价边(u,v)并且加入T后不会产生回路；
			T=T∪(u,v);
}

最小（代价）生成树的普里姆（Prim）算法

概述：

类似图的最短路径的迪杰斯特拉（Dijkstra）算法
对点

过程：选边加点加边

加点
加候选边
依据代价，从候选边中选边（每次构造一定为连通图）
依据所选边，加点
依据所加点，加候选边
重复345步，直到加入所有点（执行n-1次，n为点数）

伪代码：

void Prim(G,T){
	T=空集;						//初始化空树
	U={w};						//添加任一顶点w 
	while((V-U)!=空集){			//若树中不含全部顶点
		设(u,v)是使u属于U与v属于(V-U),且权值最小的边；
		T=T∪{(u,v)}				//边归入树
		U=U∪{v};				//顶点归入树
}

时间复杂度：O(n²)。n为点数

空间复杂度：O(n)。n为点数。辅助空间记录标记已访问点和候选边

适用：边稠密图

最小（代价）生成树的克鲁斯卡尔（Kruskal）算法

概述：

对边

过程：加边加点；合并点/连通分量/树

依据代价，排序边
依据代价，从小到大遍历边
若边为候选边，则加边（每次构造不一定为连通图）
依据所加边，若点为候选点，则加点，否则不加边不加点并转2
重复234步，直到直到加入n-1条边。n为点数/所有点在一个连通分量

若边为候选边和若点为候选点的另一种描述：若加边不构成回路，则加边加点，否则不加边不加点并转2

伪代码：

void Kruskal(V,T){
	T=V;					//初始化树T，仅含顶点
	numS=n;					//连通分量数
	while(numS>1){			//若连通分量数大于1 
		从E中取出权值最小的边(v,u);
		if(v和u属于T中不同的连通分量){
			T=T∪{(v,u)};	//将此边加入生成树中
			numS--;			//连通分量数减1 
		}
	}
}

时间复杂度：排序算法中常用堆排序，堆存储边：O(eloge)。e为边数

空间复杂度：O(n)。n为点数。辅助空间并查集记录点的树型结构

适用：边稀疏点稠密图/稀疏图

最短路径概述

概念：

对带权图
带权路径长度最短的路径

算法：

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

最短路径的迪杰斯特拉（Dijkstra）算法

概述：

类似图的最小（代价）生成树的普里姆（Prim）算法
对点
基于贪心策略

思想：求单源最短路径：图中某点到其他点的最短路径

求多源最短路径：图中多点到其他点的最短路径。时间复杂度：O(n×n²)=O(n的3次方)。n为点数

过程：选边加点加边

加点
加候选边
依据代价，从候选边中选边（每次构造一定为连通图）
依据所选边，加点
依据所加点，加候选边，更新代价
重复345步，直到加入所有点（执行n-1次，n为点数）

伪代码：

void Dijkstra(MGraph g,int v,int dist[],int path[])
{
    int set[maxSize];
    int min, i, j, u;
    /*从这句开始对各数组进行初始化*/
    for(i=0;i<g.n;++i)
    {
        dist[i]=g.edges[v][i];
        set[i]=0;
        if(g.edges[v][i]<INF)
            path[i]=v;
        else
            path[i]=-1;
    }
    set[v]=1;path[v]=-1;   
    /*初始化结束*/
    /*关键操作开始*/
    for(i=0;i<g.n-1;++i)
    {
        min=INF;
        /*这个循环每次从剩余顶点中选出一个顶点，通往这个顶点的路径在通往所有剩余顶点的路径中是长度最短的*/
        for(j=0;j<g.n;++j)
        {
            if(set[j]==0&&dist[j]<min)
            {
                u=j;
                min=dist[j];
            }
        }
        set[u]=1;	//将选出的顶点并入最短路径中
        /*这个循环以刚并入的顶点作为中间点，对所有通往剩余顶点的路径进行检测*/
        for(j=0;j<g.n;++j)
        {
            /*这个if语句判断顶点u的加入是否会出现通往顶点j的更短的路径，如果出现，则改变原来的路径及其长度，否则什么都不做*/
            if(set[j]==0&&dist[u]+g.edges[u][j]<dist[j])
            {
                dist[j]=dist[u]+g.edges[u][j];
                path[j]=u;
            }
        }
    }    
    /*关键操作结束*/
}
/*函数结束时，dist[]数组中存放了v点到其余顶点的最短路径长度，path[]中存放v点到其余各顶点的最短路径*/

时间复杂度：O(n²)。n为点数

空间复杂度：O(n)。n为点数。辅助空间记录点间代价，路径中点的前一点和标记已访问点

适用：非带权图；不存在负权值的带权图

最短路径的弗洛伊德（Floyd）算法

思想：求点间的最短路径

过程：迭代

初始化代价矩阵为邻接矩阵，路径矩阵
遍历点
对所遍历点，遍历点对
对遍历点对，所遍历点作为中间点，依据代价，更新代价矩阵和路径矩阵
重复234步，直到遍历所有点（执行n-1次，n为点数）

伪代码：

void Floyd(MGraph *g,int Path[][maxSize],int A[][maxSize])
{	//图g的边矩阵中，用INF来表示两点之间不存在边
    int i,j,k;    
    /*这个双循环对数组A[][]和Path[][]进行了初始化*/
    int A[MAXSIZE][MAXSIZE] = { 0 };
    for(i=0;i<g->n;++i)
    {
        for(j=0;j<g->n;++j)
        {
            A[i][j]=g->edges[i][j];
            Path[i][j]=-1;
        }
    }
    /*下面这个三层循环是本算法的主要操作，完成了以k为中间点对所有的顶点对(i,j)进行检测和修改*/
    for(k=0;k<g->n;++k)
    	for(i=0;i<g->n;++i)
        	for(j=0;j<g->n;++j)
            {
                if(A[i][j]>A[i][k]+A[k][j])
                	Path[i][j] = k;
            }
}

时间复杂度：O(n的3次方)。n为点数

空间复杂度：O(n²)。辅助空间记录代价和路径

适用：非带权图；可存在负权值，负权值边不成回路的带权图

拓扑排序概述

顶点表示活动的网/活动在顶点上的网（AOV网）：

工程中，各活动间先后关系的有向无环图
无回路的有向图/有向无环图/DAG图表示工程，点表示活动，边表示活动的先后关系

有向无环图可类比树，使用表达式描述

算法：拓扑排序

拓扑排序算法

概念：

对有向无环图，构造拓扑排序序列的过程
每点访问且仅访问一次
若图中存在点A到点B的路径，则拓扑排序序列中点A在点B的前面

过程：

选择一个没有前驱/入度为0的点，输出
删除该点和以该点为起点的有向边
重复12步，直到AOV网为空（排序成功）或AOV网不为空且不存在没有前驱/入度为0的点（存在回路，排序失败）

伪代码：

int TopSort(AGraph *G)
{
    int i,j,n=0;
    int stack[maxSize],top=-1;	//定义并初始化栈
    ArcNode *p;
    /*这个循环将图中入度为0的顶点入栈*/
    for(i=0;i<G->n;++i)			//图中顶点从0开始编号
        if(G->adjlist[i].count==0)
        	stack[++top]=i;
    /*关键操作开始*/
    while(top!=-1)
    {
        i=stack[top--];			//顶点出栈
        ++n;    				//计数器加一，统计当前顶点
        cout<<i<<" ";			//输出当前顶点
        p=G->adjlist[i].firstarc;
        /*这个循环实现了将所有由此顶点引出的边所指向的顶点的入度都减少1，并将这个过程中入度变为0的顶点入栈*/
        while(p!=NULL)
        {
            j=p->adjvex;
            --(G->adjlist[j].count);
            if(G->adjlist[i].count==0)
            {
                stack[++top]=j;
            }
            p=p->nextarc;
        }
    }
    /*关键操作结束*/
    if(n==G->n)
        return 1;
    else 
    	return 0;
}