网站制作佛山,wordpress调用最近发布的文章,教育网站网址,修改wordpress后台登陆地址今天主讲图论。 前言#xff1a;图的定义#xff1a;图G是一个有序二元组(V,E)#xff0c;其中V称为顶集(Vertices Set)#xff0c;E称为边集(Edges set)#xff0c;E与V不相交。它们亦可写成V(G)和E(G)。 一、图的存储#xff1a; 1、邻接矩阵#xff1a; 2、邻接表图的定义图G是一个有序二元组(V,E)其中V称为顶集(Vertices Set)E称为边集(Edges set)E与V不相交。它们亦可写成V(G)和E(G)。 一、图的存储 1、邻接矩阵 2、邻接表 数组模拟链表实现记录每条边的终点、边权如果有的话、同一起点的上一条边的编号并记录以每个点为起点的最后一条边的编号。 STL中的vector记录以每个点为起点的边。 一些vector的细节 vector 本质就是 c 模板库帮我们实现好的可以变长的数组 向一个数组vector型 a 的末尾加入一个元素 x a.push_back(x) 询问 a 的长度 a.size()询问a的真实长度a.capacity() 注意vector 中元素下标从 0 开始当需要变长时变长一倍因此需要额外的内存空间。 深入学习https://www.cnblogs.com/zhonghuasong/p/5975979.html 代码 邻接表 const int N 5005;//最多N个点/边struct edge {int u, v, w, next;//起点终点边权同起点的上一条边的编号
}edg[N];
int head[N]; //以每个点为起点的最后一条边的编号
int n, m, cnt; //cnt: 边的总数void add(int u, int v, int w)
{int e cnt;edg[e] (edge){u, v, w, head[u]};head[u] e;
}
int main()
{cin n m; cnt 0;for (int u, v, w, i 1; i m; i)cin u v w, add(u, v, w), odeg[u], ideg[v];return 0;
} vector: 1 #include bits/stdc.h2 3 using namespace std;4 5 const int N 5005;6 7 struct edge {8 int u, v, w;9 };
10 vectoredge edg[N];
11 int n, m, cnt; //cnt: numbers of edges
12 bool visited[N];
13
14 void add(int u, int v, int w)
15 {
16 edg[u].push_back((edge){u, v, w});
17 }
18 void travel(int u, int distance)//遍历
19 {
20 cout u distance endl; visited[u] true;
21 for (int e 0; e edg[u].size(); e)
22 if (!visited[edg[u][e].v])
23 travel(edg[u][e].v, distance edg[u][e].w);
24 }
25 int main()
26 {
27 cin n m; cnt 0;
28 for (int u, v, w, i 1; i m; i)
29 cin u v w, add(u, v, w);
30 return 0;
31 }
32 二、生成树 最小生成树给定一个 n 个点 m 条边的带权无向图求一个生成树使得生成 树中边权和的最小。 例题引入 扩展引用百度百科 只要求出最小生成树就好了。 求解最小生成树 生成树的本质选取若干条边使得任意两点连通。 各种求解算法的本质贪心 1、Kruskal算法克鲁斯卡尔算法 将所有边按边权排好序从最小的开始枚举若加入该边后会形成环即边的端点已经连通就忽略掉它看下一条否则加入该边直至得到最小生成树能得到的话。查询两点连通情况并查集。 时间复杂度OE log E 代码 1 #include bits/stdc.h2 3 using namespace std;4 5 const int maxn 1000005;6 struct edge {7 int u, v, w;8 }edg[maxn];9 int n, m, p[maxn], ans 0;
10
11 bool cmp(edge a, edge b)
12 {return a.w b.w;}
13 int findp(int t)
14 {return p[t] ? p[t] findp(p[t]) : t;}
15 bool merge(int u, int v)
16 {
17 u findp(u); v findp(v);
18 if (u v) return false;
19 p[u] v; return true;
20 }
21 int main()
22 {
23 cin n m;
24 for (int i 1, u, v, w; i m; i)
25 cin u v w, edg[i] (edge){u, v, w};
26 sort(edg 1, edg m 1, cmp);
27
28 for (int i 1; i m; i)
29 if (merge(edg[i].u, edg[i].v))
30 ans max(ans, edg[i]. w);
31 cout ans endl;
32 } 2、Prim算法普里姆算法 以一点为最小生成树的根找到一个到该最小连通块边权最小、不在该连通块里的点并加入到该连通块直到组成最小生成树。 时间复杂度O(n2) 代码 #includeiostream
#includecstdio
#includecstring
#define forup(i,n) for(int i1;in;i)//偷懒
using namespace std;
int n,m;
int ma[5001][5001],bianli1,d[5001];
bool vis[5001];
int main()
{int x,y,z,tot0;cinnm;memset(ma,0x3f,sizeof(ma));//求最短性图论问题一般初始化为一个很大的数forup(i,m){scanf(%d%d%d,x,y,z);//去重边if(zma[x][y])ma[x][y]ma[y][x]z;}vis[1]1;memset(d,0x3f,sizeof(d));d[1]0;memset(vis,0,sizeof(vis));//0蓝1白 int stt_node,stt_dis;forup(i,n){stt_dis0x3f3f3f3f,stt_node0;for(int j1;jn;j)if(!vis[j]d[j]stt_dis){stt_nodej;stt_disd[j];}vis[stt_node]1;totstt_dis;for(int j1;jn;j)if(!vis[j]d[j]ma[j][stt_node]){d[j]ma[j][stt_node];}}couttot;return 0;
} 三、路径 最短路径问题 最短路径算法本质思想不断进行松弛操作更新最短路操作 1、Floyd算法弗洛伊德算法 正确性 可求任意两点之间的最短路多源最短路时间复杂度O(n); 负权环 代码 1 int d[N][N], n, m;2 int main()3 {4 cin n m;5 for (int i 1; i n; i)6 for (int j 1; j n; j) d[i][j] inf;7 for (int u, v, w, i 1; i m; i)8 cin u v w, d[u][v] min(d[u][v], w);9
10 for (int k 1; k n; k)
11 for (int i 1; i n; i)
12 for (int j 1; j n; j)
13 d[i][j] min(d[i][j], d[i][k] d[k][j]);
14 } 2、Bellman-Ford算法贝尔曼-福特算法 单源最短路算法设源点为S 正确性 d[u]至少经过1条边经过几条边用几条边松弛后就能得到真实值。任意最短路经过不超过 n − 1 条边n 次松弛足矣。 因此不适用于有负权环的情况。n为点数m为边数 易知Bellman-Ford 算法中如果 d(u) 在上一次全局更新中没有被更新那么这一次全局更新中不必松弛 u 的出边若能更新上一次就不会不更新。 代码 1 struct edge{2 int u, v, w;3 }edg[N];4 int d[N], n, m, S;5 int main()6 {7 cin n m S;8 for (int i 1; i n; i) d[i] inf;9 for (int u, v, w, i 1; i m; i)
10 cin u v w, edg[i] (edge){u, v, w};
11
12 d[S] 0;
13 for (int i 1; i n; i)
14 for (int j 1; j m; j)
15 {
16 int u edg[j].u, v edg[j].v, w edg[j].w;
17 d[v] min(d[v], d[u] w);
18 }
19 } 3.SPFA算法Shortest Path Faster Algorithm 翻译最短路径快速算法在一般情况下的确挺快的只要不被针对 贝尔曼-福特算法的队列优化形式通过队列减少了很多冗余的计算时间复杂度OkE(k是小常数平均值为2最糟糕的时间复杂度O(VE)被针对的恐惧 代码 1 struct edge{2 int u, v, w;3 };4 vectoredge edg[N];5 int d[N], n, m, S;6 7 queueint Queue;8 bool inQueue[N];9 int cntQueue[N];
10
11 void add(int u, int v, int w)
12 {
13 edg[u].push_back((edge){u, v, w});
14 }
15 int main()
16 {
17 cin n m S;
18 for (int i 1; i n; i) d[i] inf;
19 for (int u, v, w, i 1; i m; i)
20 cin u v w, add(u, v, w);
21
22 d[S] 0; inQueue[S] true; Queue.push(S);
23 while (!Queue.empty())
24 {
25 int u Queue.front(); Queue.pop(); inQueue[u] false;
26 for (int e 0; e edg[u].size(); e)
27 {
28 int v edg[u][e].v, w edg[u][e].w;
29 if (d[v] d[u] w)
30 {
31 d[v] d[u] w;
32 if (!inQueue[v])
33 {
34 Queue.push(v); cntQueue[v]; inQueue[v] true;
35 if (cntQueue[v] n) {cout Negative Ring endl; return 0;}//是负权环
36 }
37 }
38 }
39 }
40 for (int i 1; i n; i)
41 cout d[i] endl;
42 } 4.Dijkstra算法 迪杰斯特拉算法 一个单源最短路算法。 知道d(u) 被更新成真实值之前u 出边的松弛操作都无意义。以一个点为源点设d[i]为i节点到根的最短距离。将d初始化有与源点连边的为边的边权否则为很大的数找到最小的d[i]且i未被确定将i节点标记为已确定最短路并更新i节点出边终点的d。重复以上过程至所有点都被确定。 时间复杂度 O(n 2 m) 代码 1 #include bits/stdc.h2 3 using namespace std;4 5 const int N 1e5 5;6 const int inf 1 29;7 8 struct edge{9 int u, v, w;
10 };
11 vectoredge edg[N];
12 int d[N], n, m, S;
13
14 bool relaxed[N];
15
16 void add(int u, int v, int w)
17 {
18 edg[u].push_back((edge){u, v, w});
19 }
20 int main()
21 {
22 cin n m S;
23 for (int i 1; i n; i) d[i] inf;
24 for (int u, v, w, i 1; i m; i)
25 cin u v w, add(u, v, w);
26
27 d[S] 0;
28 for (int i 1; i n; i)
29 {
30 int u 1; while (relaxed[u]) u;//找到第一个没有被确定的点
31 for (int j 1; j n; j)//找到d[i]最短且未被确定的i
32 if (!relaxed[j] d[j] d[u]) u j;
33 relaxed[u] true;
34 for (int e 0; e edg[u].size(); e)//进行松弛操作
35 {
36 int v edg[u][e].v, w edg[u][e].w;
37 d[v] min(d[v], d[u] w);
38 }
39 }
40 for (int i 1; i n; i)
41 cout d[i] endl;
42 } EXDijkstra堆优化 利用小根堆的性质节省找到d[i]最小且未被确定的i的时间。 代码 1 #include bits/stdc.h2 3 using namespace std;4 5 const int N 1e5 5;6 const int inf 1 29;7 8 struct edge{9 int u, v, w;
10 };
11 vectoredge edg[N];
12 int d[N], n, m, S;
13
14 bool relaxed[N];
15 struct Qnode {
16 int u, du;
17 bool operator(const Qnode v)
18 const {return v.du du;}//不加const会出错
19 };
20 priority_queueQnode PQueue;
21
22 void add(int u, int v, int w)
23 {
24 edg[u].push_back((edge){u, v, w});
25 }
26 int main()
27 {
28 cin n m S;
29 for (int i 1; i n; i) d[i] inf;
30 for (int u, v, w, i 1; i m; i)
31 cin u v w, add(u, v, w);
32
33 d[S] 0; PQueue.push((Qnode){S, 0});
34 while (!PQueue.empty())
35 {
36 int u PQueue.top().u; PQueue.pop();
37 if (relaxed[u]) continue;
38 //if edges staring from u are already relaxed, no need to relax again.
39 relaxed[u] true;
40 for (int e 0; e edg[u].size(); e)
41 {
42 int v edg[u][e].v, w edg[u][e].w;
43 if (d[v] d[u] w)
44 {
45 d[v] d[u] w;
46 PQueue.push((Qnode){v, d[v]});
47 //if d(v) is updated, push v into PQueue
48 }
49 }
50 }
51 for (int i 1; i n; i)
52 cout d[i] endl;
53 } 三、DAG有向无环图 任意一个DAG一定有出度为0的点和入度为0的点。一个DAG删去一点后仍是DAG 1、拓补排序topsort n个点的DAG一定存在拓补序列。 按照有向图中边的起点一定在终点之前的顺序给出一个可行的节点序列多数不唯一 换个角度 实现 1、 找到 DAG 中入度为 0 的点 uu 可以放在当前 DAG 拓扑序末尾将 v 和与 v 有关的连边从 DAG 中删除 2、广搜从入度为 转载于:https://www.cnblogs.com/InductiveSorting-QYF/p/10803250.html
