大纲要求：图的相关算法相对较多，通常只要求掌握其基本思想和实现步骤，而算法的具体实现不是重点。

一、图的基本概念

1. 图的概念：图G由顶点集V和边集E组成的，记为G=（V，E）
2. 有向图：若E是有向边（也称为弧），则G为有向图
   G=（V，E），其中V={1，2，3}，E={<1,2>，<2,3>，<2,1>}
3. 无向图：若E是无向边（也称为边），则G为无向图
   G=（V，E），其中V={1，2，3}，E={（1,2），（2,3），（2,1）}
4. 简单图：不存在重复的边，不存在顶点到自身的边（数据结构仅讨论简单图）
5. 多重图：存在重复的边，存在顶点到自身的边
6. 完全图：对于无向图来说有n(n-1)/2条边，对于有向图来说有n(n-1)条边
7. 连通：对于无向图来说，若顶点v到顶点w有路径存在，则称v和w是连通的
   连通图：对于无向图来说，若任意两个顶点都连通，则称为连通图。否则称为非连通图。
   连通分量：对于无向图来说，无向图中的极大连通子图称为连通分量
8. 强连通：对于有向图来说，若顶点v到顶点w有路径存在，则称v和w是强连通的
   强连通图：对于有向图来说，若任意两个顶点都连通，则称为强连通图。否则称为非强连通图。
   强连通分量：对于有向图来说，有向图中的极大强连通子图称为强连通分量
9. 生成树：包含图中全部顶点的一个极小连通子图。
   极小连通子图是既要保持图的连通又要使得边数最少的子图。极大连通子图要求包含所有的边
10. 度TD、出度ID、入度OD
    顶点的度等于入度与出度之和
    有向图的全部顶点的入度之和和出度之和相等，无向图没有出度和入度之分。
    无向图的全部顶点的度的和等于边数的2倍，有向图也是。
11. 网：带有权值的边的图称为网
12. 稠密图：边数满足E>=VlogV的图。
    稀疏图：边数满足E
13. 路径：顶点v到顶点w之间的顶点序列
    路径长度：路径边上的数目
    回路：第一个顶点和最后一个顶点相同的路径
14. 距离：两个顶点之间最短路径
15. 有向树：一个顶点（作为根）入度为0，其余顶点（非根）入度为1的有向图

二、图的存储结构

核心思想：紧扣 “图由点和边组成” 这一基本概念思考四种存储结构

1. 邻接矩阵法

【数据结构】

#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct{VertexType Vex[MaxVertexNum];					//顶点表EdgeType Edge[MaxVertexNum][MaxVertexNum];		//边表，邻接矩阵形式int vexNum;			//顶点数int arcnum;			//边数
}

【存储特点】

1. 当邻接矩阵的元素仅表示相应边是否存在时，EdgeType可采用值为0和1;
   当邻接矩阵的元素表示相应边的权值时，EdgeType需要表示具体权值；
2. 无向图的邻接矩阵是对称矩阵，对规模大的邻接矩阵可采用压缩存储；
   邻接矩阵表示法的空间复杂度为O(n2n^2n2)，其中n为图的顶点数
3. 适用范围：稠密图适合使用邻接矩阵的存储表示

【相关计算】

1. 对于无向图，邻接矩阵的第i行(列)非零元素(非∞元素)的个数正好是顶点i的度TD
   对于有向图，邻接矩阵的第i行非零元素(非∞元素)的个数正好是顶点i的出度OD，邻接矩阵的第i列非零元素(非∞元素)的个数正好是顶点i的入度TD
2. 设置图G的邻接矩阵为A，AnA^nAn的元素An[i][j]A^n[i][j]An[i][j]等于由顶点i到顶点j的长度为n的路径的数目

2. 邻接表法

【数据结构】

#define MaxVertexNum 100
typedef struct ArcNode{		//边表结点int adjvex;				//该弧所指向的顶点的位置struct ArcNode *next;	//指向下一条弧的指针
}ArcNode;
typedef struct VNode{		//顶点表结点VertexType data;		//顶点信息ArcNode *first;			//顶点的第一条弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{AdList vertices;			//邻接表int vexnum,arcnum;			//图的顶点数和边数
}ALGraph;

【存储特点】

1. 适用范围：稀疏图适合使用邻接表法的存储表示
2. 邻接表法的空间复杂度：无向图的空间复杂度为O(V+2E)，有向图的空间复杂度为O(V+E)
3. 在邻接表中，给定一顶点，能很容易找出它的所有邻边，因为只需要读取它的邻接表，时间复杂度远小于O(n);而在邻接矩阵则需要扫描一行，时间复杂度为O(n).
   在邻接表中，确认两个顶点是否存在边，则需要在边链表上依次查找，时间复杂度为O(n);而在邻接矩阵则可以通过A[i][j]元素查到，时间复杂度为O(1).
4. 在有向图的邻接链表中，求一个顶点的出度只需要计算其邻接表中的结点个数；但求其顶点的入度则需要遍历全部的邻接表。后者可以采用逆邻接表来加速求解。
5. 图的邻接表表示并不唯一

3. 十字链表法（只用于有向图）

【数据结构】 这种存储结构要从边的特点出发定义

1. 弧的两个端点：弧头和弧尾
2. 弧的分类：弧头相同的弧链接在一起，弧尾相同的弧链接在一起。
   
   

【存储特点】

1. 在十字链表中，既容易找到V为尾的弧，又容易找到V为头的弧，因而容易求得顶点得出度和入度。

4. 邻接多重表（只用于无向图）

【数据结构】
【数据结构】 这种存储结构要从边的特点出发定义

1. 边的两个端点：弧头和弧尾
2. 边的分类：依附在相同顶点的边链接在一起。
   
   

三、图的基本操作

基本操作 ：图的基本操作是独立于图的存储结构的，而对于不同的存储方式，操作算法的具体实现会有着不同的性能。在设计具体算法的实现时，应考虑采用何种存储方式的算法效率会更高。

1. Adjacent(G,x,y)：判断图G是否存在边或(x,y)
2. Neighbors(G,x)：列出图G中与结点x邻接的边
3. InsertVertex(G,x)：在图G中插入顶点x
4. DeleteVertex(G,x)：在图G中删除顶点x
5. AddEdge(G,x,y)：若无向边(x,y)或者有向边不存在，则添加
6. RemoveEdge(G,x,y)：若无向边(x,y)或者有向边存在，则删除
7. FirstNeighbor(G,x)：求图G中第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1.
8. NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号。若没有则返回-1；
9. Get_edge_value(G,x,y)：获取权值
10. Set_edge_value(G,x,y)：设置权值

四、图的遍历算法

1. 广度优先搜索BFS

【算法思想】

1. 首先从未被访问的顶点v开始，接着由顶点v出发，依次访问v的各个未被访问过的邻接顶点w1，w2，w3…，然后依次访问w1，w2，w3…未被访问过的邻接结点，直到没有邻接结点为止。
2. 如果图中尚有未被访问过的结点，则另选择一个未曾被访问过的顶点作为始点，重复上述过程。

【代码实现】 （辅助队列+非递归算法）

bool visited[MAX_VERTEX_NUM];
void BFSTraverse(Graph G){for(int i=0;ivisited[i]=FALSE;}InitQueue(Q);for(i=0;ivisit(v);visited[v]=TRUE;Enqueue(Q,v);while(!isEmpty(Q)){DeQueue(Q,V);for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v)){//如果为空，会返回-1if(!visited[w]){visit(w);visited(w)=TRUE;EnQueue(Q,w);}}}
}

【具体实例】

【算法分析】

1. 空间复杂度：最坏的情况下空间复杂度为O(V)
2. 时间复杂度：邻接表时间复杂度为O(V+E)=顶点访问时间O(V)+边访问时间O(E)，邻接矩阵时间复杂度为O(V2V^2V2)

【BFS算法求解单源最短路径问题】 (注意与Dijkstra算法的区别)

void BFS_MIN_Distance()
{for(i=0;iDeQueue(Q,u);for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))if(!visited[w]){visited[w]=TRUE;d[w]=d[u]+1;			//整个算法的精髓EnQueue(Q,w);}}
}

【广度优先生成树】

1. 在广度遍历的过程中，我们可以得到一棵遍历树，称为广度优先生成树
2. 由于邻接矩阵表示唯一，所以生成树也是唯一的
3. 由于邻接表存储表示不唯一，所以生成树也是不唯一的

2. 深度优先搜索

【算法思想】

1. 首先访问图中某一起始顶点v，然后从v出发，访问与v邻接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点w2…重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点。
2. 若还有尚未被访问的顶点，则从该顶点开始继续上述搜索过程。

【代码实现】

bool visited[MAX_VERTEX_NUM];
void BFSTraverse(Graph G){for(int i=0;ivisited[i]=FALSE;}for(i=0;ivisit(v);visited[v]=TRUE;for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))if(!visited[w]) DFS(G,w)		//精髓：直接选用了新结点来寻找邻接结点，这就成了深度遍历了
}

【具体实例】

【算法分析】

1. 空间复杂度：使用了递归工作栈，故空间复杂度为O(V)
2. 时间复杂度：邻接表时间复杂度为O(V+E)=顶点访问时间O(V)+边访问时间O(E)，邻接矩阵时间复杂度为O(V2V^2V2)

【深度优先生成树】

1. 在深度遍历的过程中，我们可以得到一棵遍历树，称为深度优先生成树
2. 由于邻接矩阵表示唯一，所以生成树也是唯一的
3. 由于邻接表存储表示不唯一，所以生成树也是不唯一的

3. 图的遍历

1. 对于无向图来说，两个函数调用BFS(G,i)和DFS(G,i)的次数等于该图的连通分量数。
2. 对于有向图来说，两个函数调用BFS(G,i)和DFS(G,i)的次数等于该图的强连通分量数。

五、图的应用

1. 最小生成树

【概念特性】

1. 概念：权值之和最小的生成树
2. 特性：最小生成树不是唯一的，但是最小生成树的边的权值之和是唯一的。

【Prim算法】

1. 算法思想：初始时从图中任选一个顶点加入树T，此时树中只含有一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中的顶点数和边数都增1.
2. 算法分析：时间复杂度为O(V2V^2V2)，因为n个顶点，每个顶点有n-1条边比较大小。
3. 适用范围：边稠密的图
4. 具体实例

【Kruskal算法】

1. 算法思想：初始时为只有n个顶点而无边的非连通图T={V，{}}，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量上（即不形成环路），则将此边加入T，否则舍弃此边而选择下一条权值最小的边。直至T中所有顶点都在一个连通分量上。
2. 算法分析：时间复杂度为O(ElogEElogEElogE)
3. 适用范围：边稀疏的图
4. 具体实例
   

2. 最短路径

【Dijkstra算法：实现单源最短路径问题】 （带正权无向图、带正权有向图）

1. 算法介绍：Dijkstra算法应用了贪心算法思想，是目前公认的最好的求解最短路径的方法。算法解决的是有带权无向图、带权有向图中单个源点到其他顶点的最短路径问题。
2. 辅助数组
   dist[]：记录从源点v0v_0v0​到其他各顶点当前的最短路径长度。
   path[]：path[i]表示源点到顶点i之间的最短路径的前驱结点。
3. 算法思想：
   设置一个集合S记录已求得的最短路径的顶点，初始时把源点v0v_0v0​放入S；
   集合S每并入一个新顶点viv_ivi​，都要修改源点v0v_0v0​到集合V-S中顶点当前的最短路径长度值；
4. 算法特点：使用邻接矩阵的时间复杂度为O(V2V^2V2)，并且不适用于权值带负数的情况
5. 具体实例
   

【Floyd算法：各顶点之间最短路径问题】（带正负权无向图、带正负权有向图）

【算法思想】

【代码实现】

//核心代码
for(int k=0;kd[i][k]+d[k][j])d[i][j]=>d[i][k]+d[k][j];

【具体实例】

【算法分析】

1. 时间复杂度：根据核心代码不难得出时间复杂度为O(V3V^3V3).
2. 使用范围：带正负权无向图、带正负权有向图，但是不允许含带负权值的边组成的回路。

3. 有向无环图DAG描述表达式 （描述含有公共子式的表达式的有效工具）

【使用真题演示】

4. 拓扑排序

【基本概念】

1. AOV网：带权有向无环图 表示活动的网络，记为AOV网
2. 活动：每个顶点代表一个活动
3. 事件：每条边代表一个事件

【算法思想】

1. 从AOV网中选择一个没有前驱的顶点并输出
2. 从网中删除该顶点和所有以它为起点的有向边
3. 重复步骤1和步骤2直到当前AOV网为空

【代码实现】

bool TopoLogicalSort(Graph G){InitStack(S);for(int i=0;iif(indegree[i]=0)Push(S,i)}int count=0;		//用来计数是否全部结点拓扑完毕while(!IsEmpty(S)){Pop(S,i);print[count++]=i;for(p=G.vertices[i].firstarc;p;p=p->nextarc){	//这个for循环是核心v=p->adjvex;if(!(--indegree[v])) Push(S,v);}}if(count