数据结构——图

一 图论基本概念

 

 

 

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、最短路径