有向图、无向图
有权图、无权图
有向图:度 = 出度 + 入度
完全图:所有点可直接到达其他所有点
环:从一点出发,又可回到该点(只在有向图中讨论)
图的存储
邻接矩阵:
- 矩阵大小:m × m,m 代表点的个数
- 矩阵内容:0 为 i 和 j 不连通,a 为 i 和 j 连通,且权值为 a
邻接表(C语言):
- 表的大小:m 个二元组(tuple)及m个动态数组。
- 二元组内容:第一个元素为指针地址,指向实际存储“边的内容”的数组首地址;第二个元素为该数组所存储元素的个数。
- 动态数组内容:x个二元组(tuple)。其中第一个元素为可到达的点;第二个元素为权值。
邻接表(STL模板):
-
表的大小:m 个可动态开辟空间的 vector(二维 vector)。
-
vector<vector<tuple>> table(m, vector<tuple>());
-
顺序容器的内容:二元组(tuple)。其中第一个元素为可到达的点;第二个元素为权值。
链式前向星:
- 把邻接表中用来存储“边的内容”的各个小数组合一起,组成一个大的存储“边的内容”的大数组,原本的数组首地址改为所存放的最后一条边在该数组中的地址偏移,也就是索引。
最短路径
Floyd算法(弗洛伊德)—— 多源最短路径:
-
思想:遍历并更新所有“经过中转”与“不经过中转”的最小值
-
不变性(单次循环的正确性):确实能记录“经过 h ”与“不经过 h ”的最小值
-
单调性(问题规模不断缩小):外循环每运行一次都能压缩一条路径
-
1 -> 3 -> 2 -> 4 可变成 1 -> 3 -> 4 再变成 1 -> 4
-
时间复杂度:O(n^3)
memset(arr, 0x3F, sizeof(arr)); //初始化为极大值
for (int h = 0; h < n; h++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = min(arr[i][j], arr[i][h] + arr[h][j]);
}
}
}
Dijkstra算法(迪科斯彻)—— 单源最短路径:
- 边的权值不能是负数,因为Dijkstra算法认为“只要结果被更新过就没必要再搜索该点”(可去除的小边界),“只要队列的值比结果中的大就没必要继续搜索”(终极边界),而如果出现负数的情况则不然。但是如果去除迪科斯彻认为的条件,则该算法会因失去终止边界而一直广搜下去,也就是说此时的算法已经不满足有穷性的条件了,不能称之为算法。
- 未进行堆优化前,每个点的所有边都需要遍历,而每个点最多可有n条边,故时间复杂度:O(n^2)
- 进行堆优化后,可能要对所有的边(共m条)都进行堆插入操作,故时间复杂度:O(mlogn)
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <vector>
#include <queue>
using namespace std;
struct edge {
int next_vex, weight;
};
struct node {
int vex, dis;
bool operator<(const node &b) const{ //常成员函数,必须加上const
return this->dis > b.dis; //所有的成员函数都有一个“this指针”的隐含参数(默认是大顶堆)
}
};
int main() {
int n, m, s;
cin >> n >> m >> s;
vector<vector<edge> > edges(n + 5, vector<edge>()); //防止编号是从1开始的
for (int i = 0; i < m; i++) {
int a, b, c;
//cin >> a >> b >> c;
scanf("%d%d%d", &a, &b, &c);
edges[a].push_back((edge){b, c});
edges[b].push_back((edge){a, c});
}
int dis_min[n + 5];
memset(dis_min, -1, sizeof(dis_min));
priority_queue<node> que;
que.push((node){s, 0});
while (!que.empty()) {
node now = que.top();
que.pop();
if (now.dis > dis_min[now.vex]) continue; //终极边界
dis_min[now.vex] = now.dis;
for (int i = 0; i < edges[now.vex].size(); i++) {
int next_vex = edges[now.vex][i].next_vex;
int weight = edges[now.vex][i].weight;
if (dis_min[next_vex] != -1) continue; //堆优化后的小边界
que.push((node){next_vex, now.dis + weight});
}
}
for (int i = 1; i <= n; i++) {
//cout << dis_min[i] << endl;
printf("%d\n", dis_min[i]);
}
return 0;
}
可采用OJ上第746的“最短路”题进行测试
Bellman-Ford算法(贝尔曼-福特)—— 单源最短路径:
特点:支持边的权值为负数
用队列装载可到达的点,遍历所有的边(共m条),得到按"当前顺序"遍历时的最小距离,循环以上操作,当最小距离不再更新时停止,最多可能循环n-1次,n为点的个数。
时间复杂度:O(km) - O(nm),其中k是小常数
最小生成树
Kruskal算法(克鲁斯卡尔):
将所有的边按权重排序,从小到大取出,若这条边所连接的两个结点均在同一集合中,则丢弃;反之,则合并(即并查集问题)。最后当用于合并的边的数量等于结点的数量-1时即可终止程序。
适用于结点较多,边较稀疏的情况
Prim算法(普里姆):
将任一结点所有的边都放入优先队列中,并取出其中权重最小的一条,连接新的节点,并把其所有的边也放入优先队列中,重复以上步骤直至把所有的结点都连接完成。
适用于结点较少,边较稠密的情况
拓扑排序
拓扑排序问题只局限于有向图的情况,且不能成环(可用该特性判别是否成环)
输出其中一种拓扑排序的方法:
将所有入度为0的结点放入队列中,取出队列中的结点,同时相应的下一个结点入度-1,若其入度为0,则将其也放入队列中,反之跳过,重复以上操作,直至队列为空。
输出所有可能的拓扑排序的方法(归根结底还是排列组合问题):
将所有的结点都放入顺序表中进行递归。在递归函数中,若入度为0,则对其进行标记,同时相应的下一个结点入度-1,并进入到下一层递归函数中;最终当所有结点都标记完毕后则输出;向上回溯时再逐个解除标记,同时相应的下一个结点入度+1。
标签:图论,include,int,结点,vex,算法,now,dis From: https://www.cnblogs.com/Kelvin-Wu/p/16795346.html