图的概念
图：由V和E两个集合组成的二元组 G（V,E）
子图：V’是V的子集，E’是E的子集，且E’中的边所关联的顶点均在V’中，则G’ = ( V’ , E’ )也是一个图，称其为G的子图
生成子图： V’ = V
连通分支：无向图G的极大连通子图称为G的连通分支。任何连通图都只有一个连通分支，而非连通图有多个连通分支。通俗来讲，一个图被分成几个小块，每个小块是联通的，但小块之间不联通，那么每个小块称为联通分支。一个孤立点也是一个联通分支。
强连通分支：强连通是指一个有向图中任意两点v1、v2间存在v1到v2的路径及v2到v1的路径。强连通的连通分支是强连通分支。
生成树： | E’| = n-1 且G’连通。
极小生成树：包含原图中的所有 n 个结点，并且有保持图连通的最少的边。
图的表示法
1.邻接矩阵表示法
用一个二维数组存储图中各边的信息。
图G的邻接矩阵是一个布尔矩阵，若 i j 间有边则A[i，j]为1。当图是一个网络时A[i , j]为边的权重，无边时为∞。
2.邻接表表示法
对V中的每个顶点，将他的所有邻接顶点存放在一个表中，成为顶点 i 的邻接表。将每个顶点的邻接表存储在G的邻接表数组中。
图的遍历
1、DFS（对应树的前中后序遍历）
2、BFS（对应树的层次遍历）
最短路径
1.单源最短路
① Dijkstra算法 O（n^2）
设S为已求出最短路径的结点集合，U为未被选过的结点集合。
开始时dist都为INF，只有源点为0。每次从U中选取一个dist最小的顶点 i 加入S中（该选定的距离就源点v到 i 的最短路径长度）。然后以 i 为新考虑的中间点，修改从 i 点能到达的其他结点的dist值，若从源点到结点 j 的距离（经过 i ）比原来距离（不经过 i）短（dist[j] > dist[i]+value[i][j]），则修改dist[j]为 dist[i]+value[i][j]，这样直到所有顶点都包含在S中。
Dijkstra的特点
· 求出n-1条最短路径（单源最短路径）
· 按长度递增的次序
· 只适用于非负权边
· 贪心算法（每次在dist中找最小）
② Bellman-Ford算法 O（mn）
第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。
第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。
第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况：
d（v） > d (u) + w(u,v)
则返回false，表示途中存在从源点可达的权为负的回路。
之所以需要第三部分的原因，是因为，如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径。
Bellman-Ford特点：
· 允许负权边
· 以边为跳板，看是否由于存在某条边而对结果产生影响
③ SPFA算法（非经典算法，Bellman-Ford的改进）
实现方法为，初始时所有点dist为INF，只有起始点的dist为0。然后建立一个队列，初始时队列里只有起始点，之后不断弹出队首结点 i 去更新它能到达的所有点 j 的dist值，如果dist[j] > dist[i]+value[i][j]则更新成功，再判断下被更新的结点若不在队列中，则把该点加入到队列。这样重复执行直到队列为空。
2.所有顶点间最短路径
Floyd算法（博客很详尽）
算法思想在于逐点试探，看加入这个点是否会影响结果。
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j];
这段代码的基本思想就是：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，来进行松弛操作。
Floyd算法允许负权边不允许负权图。（否则可以一直走负圈）
无圈有向图DAG
1.AOV网（顶点为某一活动，例为“学生排课”）
大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。
每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，《数据结构》必须在选修了《高级语言程序设计》之后才能选修。我们称《高级语言程序设计》是《数据结构》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。
学生不可能学完大学所开设的所有课程，因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。
拓扑排序：（不断找入度为0的点）
step1：邻接表中所有入度为0的点入栈
step2：输出栈顶。栈顶 i 出栈， i 的直接后继入度-1。若入度为0则进栈。
step3：若栈空时输出n个则结束，否则一定存在环。
时间复杂度O（n+e）
2.AOE网（某一活动需持续一段时间，例“工程计划”）
（图中结点表示“事件的开始”或“事件的结束”，边a表示a事件持续的时间。）
完成工程的最少时间应为最长路径。影响工程进程的关键点应为最长路径上的活动。
（转）关键路径的算法思想：
1 > 从ve[0]=0开始利用递推公式求出其余顶点的最早发生时间ve[j]
ve[j]=Max{ve[i]+dut < i , j > }
(i=0,1,2,….n-1 j=1,2,…n-1 < vj , vk > ∈E )
即从源点开始按拓扑有序求各顶点的最早发生时间
2 > 从vl[n-1]=ve[n-1]开始利用递推公式求出其余顶点的最迟发生时间vl[j]； vl[j]=Min{vl[k]-dut < j , k > }
3 > 求出每条弧(即活动)的最早开始时间e[i]与最迟开始时间l[i]
e[i]=ve[j]; l[i]=vl[k]-dut < vj , vk >
若 e[i]=l[i]即为关键活动。由关键活动组成的路径即关键路径
v1最早发生时间:ve[1]=ve[0]+a1=0+5=5;
v2最早发生时间:ve[2]=ve[0]+a2=0+6=6;
v3最早发生时间:有两条路v0->v1->v3,路径长度为5+3=8；v0->v2->3, 路径长度为6+12=18；取最大的即公式中的Max{ve[i]+dut < i , j >}的含义ve[3]=18
ve[4]=18+3=21;ve[5]=21;ve[6]=23;ve[7]=25;ve[8]=28;ve[9]=30;
假定vl[l]=ve[9]=30反向递推其余顶点的最迟发生时间
vl[8]=vl[9]-a14=30-2=28;
vl[7]=vl[8]-a13=28-2=26;
vl[6]=vl[8]-a12=28-5=23;
vl[5]=26;
vl[4]有两路：vl[6]-a9=22;vl[7]-a10=26-10=16取最小的16
其他依次类推：然后是
4 > 求出每条弧(即活动)的最早开始时间e[i]与最迟开始时间l[i]
e[i]=ve[j]; l[i]=vl[k]-dut < vj , vk >
找到 e[i]=l[i]的活动即关键活动。由关键活动组成的路径即关键路径
最小生成树
图中所有边的权值都不同时，最小生成树唯一
如果有2条或以上的边有相同权值，最小生成树不一定唯一（但最小的权值和唯一）
考虑n结点m条边的图中的最小生成树算法：
·Prim算法（选点）
设集合V为已选结点集合，集合U为未选结点集合。
一开始所有结点的dist都为INF，起始结点的dist更新为0。每次从U中选一个dist最小的结点 i 加入V中，更新 i 结点所能到达全部结点 j 的dist值为dist[i]加上i，j间的边权。这样直到所有结点都加入V中为止。
时间复杂度O（n*n），主要与结点数有关，适用于稠密图。
·Kruskal算法（选边）
设集合E为已选的边集合，集合U为未选的边集合。
把所有边的边权val排序后，每次选一条最短的边（即遍历边），判断下这条边的两个结点是否已经相连（并查集维护结点间是否相连），若没有则加入集合E。执行n-1次的加入操作后退出。（生成树的边数为n-1）
时间复杂度O（mlog（m）），主要与边数有关，不适用于稠密图。
图的匹配
设G = （V,E）是一个图，如果集合M真包含于E，且M中任何两条边都不与同一个顶点相关联，则称M是G的一个匹配。G的边数最多的匹配称为G的最大匹配。如果图的一个匹配使得图中每个顶点都是该匹配中某条边的端点，那么就称这个匹配为图的完全匹配。
//–作业题
11.3 被Gank的亚索
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#define MAX_N 100+7
#define MAX_M 100000+7
#define INF 10000000+7
using namespace std;
int i,j;
int n,m,s,e;
bool vis[MAX_N];
int dist[MAX_N];
int path[MAX_N];
int id[MAX_N];
int head[MAX_N];
int next[*MAX_M];
int tot = ;
struct Edge
{
int to;
int val;
}edge[*MAX_M];
void addEdge(int u ,int v, int w)
{
edge[++tot].to = v;
edge[tot].val = w;
next[tot] = head[u];
head[u] = tot;
}
void spfa() //源点到结点距离dist 最短路径条数path
{
queue<int> que;
que.push(s);
vis[s] = true;
while(!que.empty())
{
int u = que.front();
for(j = head[u]; j ; j = next[j])
{
int v = edge[j].to;
if(dist[u]+edge[j].val < dist[v])
{
dist[v] = dist[u]+edge[j].val;
if(!vis[v])
{
que.push(v);
vis[v] = true;
}
}
}
que.pop();
vis[u] = false;
}
}
bool cmp(int a,int b)
{
return dist[a] < dist[b];
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&e);
int u,v,w;
for(i = ; i <= m; i++)
{
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
addEdge(v,u,w);
}
for(i = ; i <= n; i++)
{
id[i] = i;
dist[i] = INF;
}
dist[s] = ;
path[s] = ;
spfa();
sort(id+,id+n+,cmp); //按dist排序id
for(i = ; i <= n; i++) //从s开始更新每个较近结点
{
int index = id[i];
for(j = head[index]; j ; j = next[j])
{
int t = edge[j].to;
if(dist[index]+edge[j].val < dist[t])
path[t] = path[index];
else if(dist[index]+edge[j].val == dist[t])
path[t] += path[index];
}
}
printf("%d %d\n",dist[e],path[e]);
return ;
}
11.4 玩游戏的亚索
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX_N 5000+7
#define MAX_M 500000+7
int n,m,i,j;
struct Edge
{
int u,v,w;
}e[MAX_M];
bool cmp(const Edge & e1, const Edge & e2)
{
return e1.w < e2.w;
}
struct UF //并查集模板
{
int fa[MAX_N];
void init() { for(int i = ; i <= MAX_N; i++) fa[i] = i;}
int find(int a) { return fa[a] == a ? a : fa[a] = find(fa[a]);}
void mix(int a,int b) { fa[find(a)] = find(b);}
bool isSame(int a, int b) { return find(a) == find(b);}
} uf;
int main()
{
scanf("%d%d",&n,&m);
int e_n = ;
for(i = ; i <= m; i++)
{
e_n++;
scanf("%d%d%d",&e[e_n].u,&e[e_n].v,&e[e_n].w);
}
sort(e+,e+m+,cmp);
// for(i = 1; i <= m; i++)
// cout << e[i].w << endl;
int ned,ans = ;
uf.init();
for(i = ,ned = n-;ned && i <= m; i++) //选取n-1条边
{
if(uf.isSame(e[i].u,e[i].v)) continue;
ned--;
ans+=e[i].w;
uf.mix(e[i].u,e[i].v);
}
printf("%d\n",ans);
return ;
}