-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph_theory.tex
199 lines (130 loc) · 6.71 KB
/
graph_theory.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
% graph_theory.tex
% 2017/07/20, v1
\chapter{图论}
\label{graph_theory}
\newcommand{\prefixgrapthy}[1]{graph\_theory/#1}
\newcommand{\xprefixgrapthy}[1]{graph_theory/#1}
\section{最短路}
\subsection{Dijkstra,邻接矩阵存储}
\lstinputlisting{graph_theory/dijkstra1.cpp}
\subsection{Dijkstra,邻接矩阵存储,双路径信息}
\lstinputlisting{graph_theory/dijkstra2.cpp}
\subsection{Dijkstra,结点带权值}
\lstinputlisting{graph_theory/dijkstra3.cpp}
\subsection{Dijkstra,priority\_queue优化}
\lstinputlisting{graph_theory/dijkstra4.cpp}
\subsection{Bellman-Ford}
\lstinputlisting{graph_theory/bellman_ford.cpp}
\subsection{SPFA}
\lstinputlisting{graph_theory/SPFA.cpp}
\subsection{Floyd,邻接矩阵存储}
\lstinputlisting{graph_theory/floyd1.cpp}
\subsection{Floyd,点权 + 路径限制}
\lstinputlisting{graph_theory/floyd2.cpp}
\section{第K短路}
\subsection{Dijkstra}
\lstinputlisting{graph_theory/kth_sssp1.cpp}
\subsection{Floyd,邻接矩阵存储}
\lstinputlisting{graph_theory/kth_sssp2.cpp}
\section{最小生成树 / 森林}
\begin{example}[最小生成树]
\href{https://xoj.red/problems/show/1240}{XOJ 1240 Agri-Net 最短网络}
\end{example}
\xsubsection{Prim + 邻接矩阵}{\prefixgrapthy{mst\_prim\_matrix.cpp}}
\lstinputlisting{\xprefixgrapthy{mst_prim_matrix.cpp}}
\xsubsection{Prim + 邻接表}{\prefixgrapthy{mst\_prim\_vector.cpp}}
\lstinputlisting{\xprefixgrapthy{mst_prim_vector.cpp}}
\xsubsection{Prim + priority\_queue优化}{\prefixgrapthy{mst\_prim\_priority\_queue.cpp}}
\lstinputlisting{\xprefixgrapthy{mst_prim_priority_queue.cpp}}
\subsection{Kruskal}
\lstinputlisting{graph_theory/mst_kruskal.cpp}
\subsection{斯坦纳树}
\lstinputlisting{graph_theory/kth_sssp2.cpp}
\subsection{最小生成森林 / K棵树}
数据结构:并查集 算法:改进Kruskal 复杂度:O(mlongm)
根据Kruskal算法思想,图中的生成树在连接完第n - 1条边前,都是一个最小生成森林,每次贪心的选择两个不属于同一连通分量的树(如果连接一个连通分量,因为不会减少块数,那么就是不合算的)且用最“便宜”的边连起来,连接n - 1次后就形成了一棵MST,n - 2次就形成了一个两棵树的最小生成森林,n - 3、……、n - k次后,就形成了k棵树的最小生成森林,也就是题目要求的解。
\section{次小生成树}
\subsection{$O(v^2)$}
\lstinputlisting{graph_theory/secondary_mst.cpp}
\section{最小树形图}
\subsection{朱刘算法}
\lstinputlisting{graph_theory/mst_zhuliu.cpp}
\subsection{有向图最小树形图}
\lstinputlisting{graph_theory/mst_dir_tree.cpp}
\section{LCA}
\subsection{DFS + ST在线算法}
例:POJ 1330 Nearest Common Ancestors
\lstinputlisting{graph_theory/LCA_st.cpp}
\subsection{Tarjan离线算法}
例:POJ 1470 Closest Common Ancestors
\lstinputlisting{graph_theory/LCA_Tarjan.cpp}
\subsection{倍增法}
例:POJ 1330 Nearest Common Ancestors
\lstinputlisting{graph_theory/LCA_redouble.cpp}
\section{树相关}
\subsection{树的重心}
\lstinputlisting{graph_theory/centre_of_tree.cpp}
\subsection{DAG的DFS序}
\lstinputlisting{graph_theory/dag_dfs_order.cpp}
\section{连通性问题}
\subsection{DFS求联通分量}
\lstinputlisting{graph_theory/connected_component1.cpp}
\subsection{无向图的连通度 / 割}
\lstinputlisting{graph_theory/connected_component2.cpp}
\subsection{无向图的割顶和桥}
例:\href{https://xoj.red/problems/show/3099}{XOJ 3099},求无向图的割顶和桥(模板)。
\lstinputlisting{graph_theory/connected_component_cut.cpp}
\subsection{双连通分量}
\subsubsection{点-双连通分量}
去掉桥,其余的连通分支就是边双连通分支了。一个有桥的连通图要变成边双连通图的话,把双连通子图收缩为一个点,形成一颗树。需要加的边为(leaf+1)/2 (leaf 为叶子结点个数)
例:POJ 3177 Redundant Paths
给定一个连通的无向图 G,至少要添加几条边,才能使其变为双连通图。
\lstinputlisting{graph_theory/biconnected_component.cpp}
\subsubsection{边-双连通分量}
对于点双连通分支,实际上在求割点的过程中就能顺便把每个点双连通分支求出。建立一个栈,存储 当前双连通分支,在搜索图时,每找到一条树枝边或后向边(非横叉边),就把这条边加入栈中。如果遇到某时满足 DFS(u)<=Low(v),说明u是一个割点,同时把边从栈顶一个个取出,直到遇到了边(u,v), 取出的这些边与其关联的点,组成一个点双连通分支。割点可以属于多个点双连通分支,其余点和每条边只属于且属于一个点双连通分支。
例:POJ 2942 Knights of the Round Table
奇圈,二分图判断的染色法,求点双连通分支
\lstinputlisting{graph_theory/biconnected_component_edge.cpp}
\subsection{有向图强连通分量}
\subsubsection{基于邻接矩阵的DFS / BFS}
\lstinputlisting{graph_theory/connected_strongly_dfsbfs.cpp}
\subsubsection{Tarjan}
\lstinputlisting{graph_theory/connected_strongly_tarjan.cpp}
\subsubsection{Kosaraju}
\lstinputlisting{graph_theory/connected_strongly_kosaraju.cpp}
\section{最小环}
令e(u, v)表示u和v之间的连边,令min(u, v)表示删除u和v之间的连边之后u和v之间的最短路, 最小环则是min(u, v) + e(u, v). 时间复杂度是 $O(EV^2)$.
改进算法:在Floyd的同时,顺便算出最小环,g[i][j]=(i,j)之间的边长
\begin{lstlisting}
dist:=g;
for k:=1 to n do
begin
for i:=1 to k-1 do
for j:=i+1 to k-1 do
answer:=min(answer, dist[i][j]+g[i][k]+g[k][j]);
for i:=1 to n do
for j:=1 to n do
dist[i][j]:=min(dist[i][j], dist[i][k]+dist[k][j]);
end;
\end{lstlisting}
最小环改进算法的证明:一个环中的最大结点为k(编号最大), 与他相连的两个点为i, j, 这个环的最短长度为g[i][k]+g[k][j]+i到j的路径中所有结点编号都小于k的最短路径长度. 根据floyd的原理, 在最外层循环做了k-1次之后, dist[i][j]则代表了i到j的路径中所有结点编号都小于k的最短路径综上所述,该算法一定能找到图中最小环。
\lstinputlisting{graph_theory/minimum_circle.cpp}
\section{拓扑排序}
\lstinputlisting{graph_theory/topsort.cpp}
\section{2-SAT问题}
\subsection{2-SAT}
\lstinputlisting{graph_theory/2sat.cpp}
\subsection{稳定婚姻问题}
\lstinputlisting{graph_theory/2sat2.cpp}
\section{最大团问题}
\subsection{DP + DFS}
\lstinputlisting{graph_theory/max_clique_dfs.cpp}
\section{一般图的匹配}
\subsection{一般图匹配带花树}
\lstinputlisting{graph_theory/match_edmonds.cpp}
\section{弦图}
\subsection{判定}
\lstinputlisting{graph_theory/chordal_judge.cpp}
\subsection{Perfect Elimination点排列}
\lstinputlisting{graph_theory/chordal_cardinality.cpp}
\endinput % graph_theory