算法基础---搜索与图论
文章目录
- 树与图的存储
- 树与图的遍历
- DFS
- BFS
- 拓扑排序
- 单源最短路径
- 朴素版Dijkstra算法
- 堆优化版Dijkstra算法
- Bellman-Ford算法
- SPFA算法
- SPFA算法判断负环
- 多源最短路径
- Floyd算法
- 最小生成树
- 朴素版prim算法
- Kruskal算法
- 二分图
- 染色法
- 匈牙利算法
一、树与图的存储
树是一种特殊的图，与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。
1.邻接矩阵
1、定义
图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图，一个一维数组存储顶点信息，一个二维数组（成为邻接矩阵）存储边的信息。
设图G=(V, E)，其中V是图G中顶点的集合，E是图G中边的集合，通常用(vi, vj)表示无向边，用
图一：邻接矩阵的定义
2、存储表示
首先分别看下无向图和有向图的存储实例：
图二：无向图的邻接矩阵表示
邻接矩阵：g[a][b] 存储边a->b
2.邻接表
1、定义
邻接表是一种数组与链表相结合的存储方法。邻接表的处理方法如下：
-
图中的顶点用一个一维数组存储，也可以用单链表，只是用数组可以更容易的读取顶点信息。另外，在顶点数组中，每个数据元素需要存储一个指向第一个邻接点的指针。可以表示为 ：| data | firstedge | 。
-
图中每个顶点vi的所有邻接点组成一个线性表，因为个数不定，用单链表存储。每个节点可以表示为：| adjvex | next |。
2、存储表示
我们再来看下，无向图和有向图的邻接表存储实例：
图四：无向图的邻接表表示
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;// 添加一条边a->b
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}// 初始化
idx = 0;
memset(h, -1, sizeof h);二、树与图的遍历
1.DFS
int dfs(int u)
{st[u] = true; // st[u] 表示点u已经被遍历过for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (!st[j]) dfs(j);}
}2.BFS
queue q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);while (q.size())
{int t = q.front();q.pop();for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (!st[j]){st[j] = true; // 表示点j已经被遍历过q.push(j);}}
} 三、拓扑排序
拓扑排序的算法步骤很简单，就是两步：
(1) 在有向图中选一个没有前驱的顶点且输出之。
(2) 从图中删除该顶点和所有以它为尾的弧。
重复上述两步，直至全部顶点均已输出，或者当前图不存在无前驱的顶点为止，后一种情况说明有向图中存在环。
时间复杂度 O(n+m), n 表示点数，m 表示边数
bool topsort()
{int hh = 0, tt = -1;// d[i] 存储点i的入度for (int i = 1; i <= n; i ++ )if (!d[i])q[ ++ tt] = i;while (hh <= tt){int t = q[hh ++ ];for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (-- d[j] == 0)q[ ++ tt] = j;}}// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。return tt == n - 1;
}
四、单源最短路径
1.朴素版Dijkstra算法
思想：1..初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则
2.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
3.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
4.重复步骤b和c直到所有顶点都包含在S中。
时间复杂是 O(n2+m), n 表示点数，m 表示边数
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;for (int i = 0; i < n - 1; i ++ ){int t = -1; // 在还未确定最短路的点中，寻找距离最小的点for (int j = 1; j <= n; j ++ )if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;// 用t更新其他点的距离for (int j = 1; j <= n; j ++ )dist[j] = min(dist[j], dist[t] + g[t][j]);st[t] = true;}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}
2.堆优化版Dijkstra算法
时间复杂度 O(mlogn), n 表示点数，m 表示边数
typedef pair PII;int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;priority_queue, greater> heap;heap.push({0, 1}); // first存储距离，second存储节点编号while (heap.size()){auto t = heap.top();heap.pop();int ver = t.second, distance = t.first;if (st[ver]) continue;st[ver] = true;for (int i = h[ver]; i != -1; i = ne[i]){int j = e[i];if (dist[j] > distance + w[i]){dist[j] = distance + w[i];heap.push({dist[j], j});}}}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}
3.Bellman-Ford算法
思想：Bellman-ford的原理即每次做一次枚举所有边进行一次大松弛操作后必有所有最短路径的第一条边（起点为源点的边）被确定（尽管我们并不确切地知道是哪一条边），被确定后，则会凭这条边再下一次大松弛操作再确定第二条边，以此类推。由于n个点的图的两点间最短路径最长有n条边，所以最多要n次大松弛就能把一个单源最短路求出（但实际上很多时候不到n次大松弛操作，就没有可松弛的了，即已经找到答案，可记录当前大松弛是否做过松弛操作，或基于该缺点改进为spfa）。但如果发现在n次大松弛操作后还有松弛操作可做，就说明负权回路出现了。时间复杂度O（nm）（m为边数），有点大。
时间复杂度 O(nm), n 表示点数，m 表示边数
int n, m; // n表示点数，m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离struct Edge // 边，a表示出点，b表示入点，w表示边的权重
{int a, b, w;
}edges[M];// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。for (int i = 0; i < n; i ++ ){for (int j = 0; j < m; j ++ ){int a = edges[j].a, b = edges[j].b, w = edges[j].w;if (dist[b] > dist[a] + w)dist[b] = dist[a] + w;}}if (dist[n] > 0x3f3f3f3f / 2) return -1;return dist[n];
}
4.SPFA算法
思路：初始的时候将s放入队列中。
【1】队列出队，出队元素为current，松弛current与其邻接点相连的边，将松弛成功的邻接点放入队列中，这些点中包含其最短路径的第二个点（第一个点为起点）
【2】然后再次队列出队，出队元素为current，松弛current与其邻接点相连的边，但如果已在队列中就不要重复入队了
【3】重复以上步骤
时间复杂度 平均情况下 O(m)，最坏情况下 O(nm), n 表示点数，m 表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;queue q;q.push(1);st[1] = true;while (q.size()){auto t = q.front();q.pop();st[t] = false;for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入{q.push(j);st[j] = true;}}}}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n];
} 5.SPFA算法判断负环
思想：根据松弛次数是否大于等于n来判断负权环，根据出队次数是否大于等于n来判断，想到的。因为，判断出队次数，是判断更新次数的上界。用一个n大小的数组来代表每个点的松弛次数。因为SPFA算法里的松弛，和Bellman-ford算法里的松弛一样。Bellman-ford算法里，对同一个点的松弛次数，在极端情况下，可以想象把这些松弛次数分配到每一次迭代求解中去，而迭代求解一共只有n-1次。所以一旦某个点的松弛次数等于了n，那么就说明有负环。
所以，在每次进行松弛后，遍历判断每个点的松弛次数，如果有一个等于n（再执行下去就会大于n），就说明有负环。
时间复杂度是 O(nm), n 表示点数，m 表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中// 如果存在负环，则返回true，否则返回false。
bool spfa()
{// 不需要初始化dist数组// 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。queue q;for (int i = 1; i <= n; i ++ ){q.push(i);st[i] = true;}while (q.size()){auto t = q.front();q.pop();st[t] = false;for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];cnt[j] = cnt[t] + 1;if (cnt[j] >= n) return true; // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环if (!st[j]){q.push(j);st[j] = true;}}}}return false;
}
五、多源最短路径
Floyd算法
时间复杂度是 O(n3), n 表示点数
//初始化：for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )if (i == j) d[i][j] = 0;else d[i][j] = INF;// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{for (int k = 1; k <= n; k ++ )for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}六、最小生成树
1.朴素版prim算法
适合稠密图 ，稠密图适合用邻接矩阵存储
核心操作
1、 dist[i] 初始化为正无穷
2、集合s 表示在当前连通块内的所有点
3、for(i=1~n) 找到在集合外的距离最近的点->t
4、用t来更新其他点到集合的距离
5、把他加入到集合当中去 st[t]=true;（边的正负都可以）
时间复杂度是 O(n2+m), n 表示点数，m 表示边数
int n; // n表示点数
int g[N][N]; // 邻接矩阵，存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离
bool st[N]; // 存储每个点是否已经在生成树中// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{memset(dist, 0x3f, sizeof dist);int res = 0;for (int i = 0; i < n; i ++ ){int t = -1;for (int j = 1; j <= n; j ++ )if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;if (i && dist[t] == INF) return INF;if (i) res += dist[t];st[t] = true;for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);}return res;
}
2.Kruskal算法
算法思想：现在我们假设一个图有m个节点，n条边。首先，我们需要把m个节点看成m个独立的生成树，并且把n条边按照从小到大的数据进行排列。在n条边中，我们依次取出其中的每一条边，如果发现边的两个节点分别位于两棵树上，那么把两棵树合并成为一颗树；如果树的两个节点位于同一棵树上，那么忽略这条边，继续运行。等到所有的边都遍历结束之后，如果所有的生成树可以合并成一条生成树，那么它就是我们需要寻找的最小生成树，反之则没有最小生成树。
时间复杂度是 O(mlogm), n 表示点数，m 表示边数
nt n, m; // n是点数，m是边数
int p[N]; // 并查集的父节点数组struct Edge // 存储边
{int a, b, w;bool operator< (const Edge &W)const{return w < W.w;}
}edges[M];int find(int x) // 并查集核心操作
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}int kruskal()
{sort(edges, edges + m);for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集int res = 0, cnt = 0;for (int i = 0; i < m; i ++ ){int a = edges[i].a, b = edges[i].b, w = edges[i].w;a = find(a), b = find(b);if (a != b) // 如果两个连通块不连通，则将这两个连通块合并{p[a] = b;res += w;cnt ++ ;}}if (cnt < n - 1) return INF;return res;
}七、二分图
如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。
1.染色法
时间复杂度是 O(n+m), n 表示点数，m 表示边数
int n; // n表示点数
int h[N], e[M], ne[M], idx; // 邻接表存储图
int color[N]; // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{color[u] = c;for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (color[j] == -1){if (!dfs(j, !c)) return false;}else if (color[j] == c) return false;}return true;
}bool check()
{memset(color, -1, sizeof color);bool flag = true;for (int i = 1; i <= n; i ++ )if (color[i] == -1)if (!dfs(i, 0)){flag = false;break;}return flag;
}2.匈牙利算法
时间复杂度是 O(nm), n 表示点数，m 表示边数
关于匈牙利算法的详解
int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过bool find(int x)
{for (int i = h[x]; i != -1; i = ne[i]){int j = e[i];if (!st[j]){st[j] = true;if (match[j] == 0 || find(match[j])){match[j] = x;return true;}}}return false;
}// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{memset(st, false, sizeof st);if (find(i)) res ++ ;
}下一篇：转战C#---day7