一 图论基本概念
Directed Acyclic Graph (DAG)
二 图的存储
①邻接矩阵(适用于稠密图)
②邻接表(适用于稀疏图)
三、图的遍历
①深度优先搜索
//(基于邻接表实现,以有向图为例)
//DFS:Depth First Search 深度优先搜索
//1、访问起始顶点 2、访问一个未访问过的邻接顶点 3、若所有邻接顶点都已被访问,则回溯 4、所有顶点都被访问,遍历结束
void dfs(int start, bool visited[])
{
//访问起始结点
cout << verList[start].ver << '\t';
visited[start] = true;
//找到顶点表中该顶点对应的链表
edgeNode* node = verList[start].head;
while (node)
{
if (!visited[node]) dfs(visited[node],visited); //访问未访问过的邻接结点
node = node->next; //跳过已访问的结点
}
//当所有邻接结点都已被访问,则回溯
} //递归函数结束时,生成一棵深度优先搜索树
void dfs()
{
//访问标志数组初始化
bool* visited=new bool[Vers]; //Vers:顶点数量
for (int i = 0; i < Vers; i++)
Vers[i] = false;
for (int i = 0; i < Vers; i++)
{
if (visited[i] == true) continue; //寻找下一个树遍历的起始结点
dfs(i, visited);
} //生成深度优先搜索森林(起点选择不同,生成结果不同,有些情况能只生成一棵树)
}
DFS将所有边和顶点遍历一次,若采用邻接数组,时间复杂度为O(V²),若采用邻接矩阵,时间复杂度为O(V+E)。
②广度优先搜索
//BFS:Breadth First Search 广度优先搜索
//1、访问起始顶点 2、依次访问起始顶点的所有未访问的邻接结点 3、所有顶点都被访问,遍历结束
void bfs()
{
queue<int> q;
bool* visited = new bool[Vers];
for (int i = 0; i < Vers; i++)
visited[i] = false;
for (int i = 0; i < Vers; i++)
{
if (visited[Vers] == true) continue; ///寻找一棵新的搜索树的起始结点
q.push(i); //结点入队,开始一棵搜索树的生成
while (!q.empty())
{
int currentNode = q.front();
q.pop();
if (visited[currentNode]) continue; //这里需要注意,比如1的邻接结点2、3入队,而3邻接于2,在访问3的过程中已访问了2,所以2出队时无需再次访问
cout << verList[currentNode].ver << '\t'; //访问当前结点
visited[currentNode] = true;
//找到顶点表中该顶点对应的链表
edgeNode* node = verList[currentNode].head;
//将未访问的邻接顶点入队
while (node)
{
if (!visited[node->end]) q.push(node->end); //将未访问的邻接顶点入队
node = node->next;
}
}
}
}
可用优先级队列实现。
BFS将所有边和顶点遍历一次,若采用邻接数组,时间复杂度为O(V²),若采用邻接矩阵,时间复杂度为O(V+E)。
四、图的应用
1、欧拉路径(一笔画问题)
欧拉路径:在图中找到一条路径经过每一条边,且每条边只经过一次
欧拉回路:起点和终点相同的欧拉路径
2、图的连通性
①无向图的连通性
②有向图的连通性(Kosaraju算法)
G图和Gr图分别进行一次dfs,时间复杂度为O(V+E)
3、拓扑排序
能进行拓扑排序的图是有向无环图(DAG),顶点表示活动的图称为AOV网((activity on the vertex)
4、关键路径
AOE(activity on the edge)网是另一种有向无环图,有向边的权值表示活动的持续时间,弧尾表示活动的起点,弧头表示活动的终点,边的方向表示事件发生的先后顺序。可以用AOE网表示一项工程,如下图A为工程的源点,G为工程的收点。关键路径具有从源点到收点的最长路径长度,其上的活动称为关键活动。
顶点x的最早发生时间为ee(x),最晚发生时间为le(x),定义le(x)-ee(x)=△e(x)为时间余量,满足△e(x)=0的顶点x为关键活动,找到所有时间余量为0的顶点即找到了关键路径。
算法实现:
①进行拓扑排序
②按照拓扑序列,正向遍历每一个顶点x,计算最早发生时间ee(x):
所有顶点的ee初始化为0,假设边<u,v>的长度为Luv,对于每一个顶点u,检查其后继顶点v,若ee(u)+Luv>ee(v),更新ee(v)=ee(u)+Luv 。ee(G)即为工程的最短完成时间,即关键路径的长度Len.
③按照拓扑序列,逆向遍历每一个顶点x,计算最晚发生时间le(x):
所有顶点的le初始化为Len,假设边<u,v>的长度为Luv,对于每一个顶点u,检查其后继顶点v,若le(v)-Luv<le(u),更新le(u)=le(v)-Luv 。
④计算△e(x)=le(x)-ee(x),输出△e(x)=0的顶点即为关键活动,构成一条关键路径。
5、最小生成树
最小生成树:边的权值之和最小的生成树
①Kruskal算法
[选择边][优先级队列+并查集]
②Prim算法
[选择点]
最小生成树不一定唯一,当所有边的权值不同时,最小生成树唯一。
6、最短路径
单源最短路径:计算从一个顶点出发,到其他每一个顶点的最短路径。算法实现的目标是得到一个顶点出发到其他顶点的最短路径,并获取路径的结构。
①非加权单源最短路径(BFS)
distance[i]:源点到顶点i的最短路径
prev[i]:最短路径中i的前驱顶点
用bfs实现(利用队列),输出使用递归
时间复杂度:O(V+E)
②加权单源最短路径(Dijkstra算法)
Dijkstra算法,只适用于所有路线的权值都为正的,如果有负权值路线则算法失效,因为第一个点就不能确保是最短路径(可能存在权值总和为负数的回路)。
③带负权值单源最短路径(SPFA)
SPFA适用于无负环图
当图中无环时可以按照拓扑排序的序列改进Dijkstra算法,使时间复杂度达到线性,算法实现类似SPFA的过程。
总结一下,Dijkstra的一般性算法适用于无负权图,时间复杂度为O(V²),使用优先级队列可以是复杂度降低到O((V+E)logV),当图无环时,采用拓扑排序+队列可以使时间复杂度降低到线性。当存在负权时,Dijkstra算法可能出错,可以采用SPFA算法,时间复杂度为O(VE)。
④所有顶点对之间的最短路径(Floyd算法)
①想要找到所有顶点对之间的最短路径,可以使用V次Dijkstra算法,时间复杂度达到O(V^3)或者O(V^2logV);
②第二种经典解决算法是Floyd算法,使用穷举的思想,不断更新结点对之间的最短距离。
完结撒花!!!