一. 图的概念

  1.定义

  某类具体事物（顶点）和这些事物之间的联系（边）,由顶点（vertex）和边（edge）组成, 顶点的集合V，边的集合E，图记为G = (V,E) 

2.分类

    1、无向图 Def：边没有指定方向的图

    2、有向图 Def：边具有指定方向的图 （有向图中的边又称为弧，起点称为弧头，终点称为 弧尾） 

                                       

 

    3.带权图 Def: 边上带有权值的图。（不同问题中，权值意义不同，可以是距离、时间、价格、代价等不同属性）

 

                                     

 

3.无向图的术语 

 两个顶点之间如果有边连接，那么就视为两个顶点相邻。

 路径：相邻顶点的序列。

 圈：起点和终点重合的路径。

 连通图：任意两点之间都有路径连接的图。                             

 度：顶点连接的边数叫做这个顶点的度。

    树：没有圈的连通图。

 森林：没有圈的非连通图。

 

                  连通图                   非连通图

                             

 

4.有向图的术语

在有向图中，边是单向的：每条边所连接的两个顶点是一个有序对，他们的邻接性是单向的。

有向路径：相邻顶点的序列。

有向环：一条至少含有一条边且起点和终点相同的有向路径。

有向无环图（DAG）：没有环的有向图。

度：一个顶点的入度与出度之和称为该顶点的度。

  1）入度：以顶点为弧头的边的数目称为该顶点的入度

  2）出度：以顶点为弧尾的边的数目称为该顶点的出度 

 

eg.

                                  

1->3->5->6 ：有向路径      1->3->4->1 ：有向环      (3、4、5、6) ：无环有向图

节点1的度：3     节点1的入度：1     节点1的出度：2 

 

二.图的表示

  引入：如何用计算机来存储图的信息（顶点、边），这是图的存储结构要解决的问题？ 

 1、邻接矩阵

  对于一个有V的顶点的图而言，可以使用V*V的二维数组表示。G[i][j] 表示的是顶点i与顶点j的关系。

    如果顶点i和顶点j之间 有边相连， G[i][j]=1

    如果顶点i和顶点j之间 无边相连， G[i][j]=0

  对于无向图：G[i][j]=G[j][i]

  在带权图中，如果在边不存在的情况下，将G[i][j]设置为0，则无法与权值为0的情况分开，因此选择较大的常数INF即可。

 

  邻接矩阵的优点：可以在常数时间内判断两点之间是否有边存在。

   邻接矩阵的缺点：表示稀疏图时，浪费大量内存空间。表示稠密图还是很划算。 

                     

  

  eg. 邻接矩阵存储图

Code

 #include<bits/stdc++.h>
using namespace std;
int a[1005][1005];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		a[u][v]=a[v][u]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j])
				printf("%d ",j);
		}
		printf("\n");
	}
	return 0;
}

 2、邻接表

  通过把“从顶点0出发有到顶点2，3，5的边”这样的信息保存在链表中来表示图。

 

  

 

出边表的表结点存放的是从表头结点出发的有向边所指的尾顶点

入边表的表结点存放的则是指向表头结点的某个头顶点 

 带权图的邻接表  :在表结点中增加一个存放权的字段 

 

  

 

eg.

将如下的图利用邻接表进行表示，并输出每个顶点的度。 

 

Code

 #include<vector>
//存边（编号和边权）
struct edge{
	int v,w;
	edge(){}
	//构造函数
	edge(int V,int W){
		v=V;
		w=W;
	}
};
vector<edge> G[maxn];

void addEdge(int u,int v,int w){
	G[u].push_back(edge(v,w));
}

for(int i=1;i<=N;++i){
	int u,v,w;
	cin>>u>>v>>w;
	addEdge(u,v,w);
	addEdge(v,u,w);
}

 3.链式前向星

  参考：链式前向星–最通俗易懂的讲解

  如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好写，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。                                                                                                                                                                  ——摘自《百度百科》

链式前向星其实就是静态建立的邻接表，时间效率为O（m），空间效率也为O（m）。遍历效率也为O（m）。

对于下面的数据，第一行5个顶点，7条边。接下来是边的起点，终点和权值。也就是边1 -> 2 权值为1。

样例

 5 7
1 2 1
2 3 2
3 4 3
1 3 4
4 1 5
1 5 6

链式前向星存的是以【1，n】为起点的边的集合，对于上面的数据输出就是：

print

 1 //以1为起点的边的集合
1 5 6
1 3 4
1 2 1
 
2 //以2为起点的边的集合
2 3 2
 
3 //以3为起点的边的集合
3 4 3
 
4  //以4为起点的边的集合
4 5 7
4 1 5
 
5 //以5为起点的边不存在

 

对比邻接表

 对于邻接表来说是这样的：
1 -> 2 -> 3 -> 5
2 -> 3
3 -> 4
4 -> 1 -> 5
5 -> ^
对于链式前向星来说是这样的：
edge[0].to = 2; edge[0].next = -1; head[1] = 0;
edge[1].to = 3; edge[1].next = -1; head[2] = 1;
edge[2].to = 4; edge[2],next = -1; head[3] = 2;
edge[3].to = 3; edge[3].next = 0; head[1] = 3;
edge[4].to = 1; edge[4].next = -1; head[4] = 4;
edge[5].to = 5; edge[5].next = 3; head[1] = 5;
edge[6].to = 5; edge[6].next = 4; head[4] = 6;
简化后：1 -> 5 -> 3 -> 2

  由此可见对于每一个节点，输出的顺序为输入时的逆序

我们先对上面的7条边进行编号第一条边是0以此类推编号【0~6】，然后我们要知道两个变量的含义：

• Next ：表示与这个边起点相同的上一条边的编号。
• head[ i ] ：数组，表示以 i 为起点的最后一条边的编号。

  加边函数是这样的：

void add_edge(int u, int v, int w)//加边，u起点，v终点，w边权
{
    edge[cnt].to = v; //终点
    edge[cnt].w = w; //权值
    edge[cnt].next = head[u];//以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
    head[u] = cnt++;//更新以u为起点上一条边的编号
}

  遍历函数是这样的：

for(int i = 1; i <= n; i++)//n个起点
    {
        cout << i << endl;
        for(int j = head[i]; j != -1; j = edge[j].next)//遍历以i为起点的边
        {
            cout << i << " " << edge[j].to << " " << edge[j].w << endl;
        }
        cout << endl;
    }

第一层for循环是找每一个点，依次遍历以【1，n】为起点的边的集合。第二层for循环是遍历以 i 为起点的所有边，k首先等于head[ i ]，注意head[ i ]中存的是以 i 为起点的最后一条边的编号。然后通过edge[ j ].next来找下一条边的编号。我们初始化head为-1，所以找到你最后一个边（也就是以 i 为起点的第一条边）时，你的edge[ j ].next为 -1做为终止条件。

Code

 #include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;//点数最大值
int n, m, cnt;//n个点，m条边
struct Edge
{
    int to, w, next;//终点，边权，同起点的上一条边的编号
}edge[maxn];//边集
int head[maxn];//head[i],表示以i为起点的第一条边在边集数组的位置（编号）
void init()//初始化
{
    for (int i = 0; i <= n; i++) head[i] = -1;
    cnt = 0;
}
void add_edge(int u, int v, int w)//加边，u起点，v终点，w边权
{
    edge[cnt].to = v; //终点
    edge[cnt].w = w; //权值
    edge[cnt].next = head[u];//以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
    head[u] = cnt++;//更新以u为起点上一条边的编号
}
int main()
{
    cin >> n >> m;
    int u, v, w;
    init();//初始化
    for (int i = 1; i <= m; i++)//输入m条边
    {
        cin >> u >> v >> w;
        add_edge(u, v, w);//加边
        /*
        加双向边
        add_edge(u, v, w);
        add_edge(v, u, w);
        */
    }
    for (int i = 1; i <= n; i++)//n个起点
    {
        cout << i << endl;
        for (int j = head[i]; j != -1; j = edge[j].next)//遍历以i为起点的边
        {
            cout << i << " " << edge[j].to << " " << edge[j].w << endl;
        }
        cout << endl;
    }
    return 0;
}

 

三.图的遍历

  从图中的某个顶点出发，按某种方法对图中的所有顶点访问且仅访问一次。为了保证图中的顶点在遍历过程中仅访问一次，要为每一个顶点设置一个访问标志。 

  1.DFS

概念

深度优先搜索(Depth-First Search)遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某 个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访 问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 

Code

Code

 #include<bits/stdc++.h>
#define Maxn 205
using namespace std;
int n, m;
bool a[Maxn][Maxn], vis[Maxn];
void DFS(int i) {
    cout << i << ' ';
    vis[i] = 1;
    for (int j = 1; j <= n; j++) {
        if (a[i][j]) {
            if (!vis[j]) {
                vis[j] = 1;
                DFS(j);
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i])
            DFS(i);
    }
    return 0;
}

2.BFS

对(a)进行广度优先搜索 遍历的过程如图(b)所示， 得到的顶点访问序列为: v1->v2->v3->v4->v5->v6->v7->v8 

       

概念

广度优先搜索(Breadth-First Search)遍历类似于树的按层次遍历的过程。 假设从图中某顶点v出发，在访问v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接 点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的 顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以v为起始点，由近至远，依次访问和v有路径相通 且路径长度为1，2，…的顶点。

Code

 #include<bits/stdc++.h>
using namespace std;  
int n,m;
int a[205][205],vis[205];
void bfs(int x){
	queue<int> Q;
	Q.push(x); 
	printf("%d ",x);
	vis[x]=1;
	while(!Q.empty()){
		int now=Q.front();
		Q.pop();
		for(int i=1;i<=n;i++){
			if(a[now][i]&&!vis[i]){
				Q.push(i);
				printf("%d ",i);
				vis[i]=1;
			}
		}
	}
}
int main() {  
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		a[u][v]=a[v][u]=1;
	}
	int k;
	scanf("%d",&k);
	bfs(k);
    return 0;  
}

3.欧拉路径和欧拉回路

  欧拉路是指存在这样一种图 , 可以从其中一点出发 , 不重复地走完其所有的边 .  如果欧拉路的起点与终点相同  则称之为欧拉回路 

  欧拉路存在的充要条件 : 图是连通的 ,因为若不连通不可能一次性遍历所有边。

  对于无向图有且仅有两个点 ,与其相连的边数为奇数 ,其他点相连边数皆为偶数 ;对于两个奇数点 , 一个为起点 , 一个为终点 . 起点需要出去 ,终点需要进入 ,故其必然与奇数个边相连 .

  对于有向图 除去起点和终点 , 所有点的出度与入度相等 。且起点出度比入度大 1。终点入度比出度大 1。 若起点终点出入度也相同 ，则称为欧拉回路。
可参见鸽巢原理

1. 欧拉通路

只通过一次图中的每条边，且经过图中所有顶点的通路为欧拉通路；

2. 欧拉回路

只通过一次图中的每条边，且经过图中所有顶点的回路为欧拉回路；

3. 有向图的基图

忽略有向边的方向，得到的无向图则为该有向图的基图；

4. 欧拉图

存在欧拉回路的图称为欧拉图；

5. 半欧拉图

存在欧拉通路的图称为半欧拉图；

二、判断与证明

1. 无向图

若无向图 G 为连通图，则可通过度的奇偶性判断图 G 是否存在欧拉通路或回路，有；

1. 若图 G 不存在度为奇数的端点时，则图 G 有欧拉回路，即，无向连通多重图中存在欧拉回路当且仅当图中所有顶点的度数为偶数；

   对于上述定理，证明如下；

   1. 先证明其充分性，即存在欧拉回路则图中的所有顶点的度数必然为偶数；

      由于要遍历完图中所有的节点，则对于除起点外的每一个节点，一定在一次遍历时，通过一条边来到这个节点，并通过另一条边离开，所以其度数一定为偶数，则对于起点，通过一条边从起点出发，遍历所有节点，遍历完后，则再通过一条边返回，所以起点的度数也一定为偶数；

      则得证；

   2. 再证明其必要性，即若连通图中所有顶点的度数为偶数，则必然存在欧拉回路；

      使用构造性的存在性证明，则在所有顶点的度数为偶数的连通图中，选取一条回路，则

      1. 若此回路为欧拉回路，则结论成立了；
      2. 若此回路不为欧拉回路，则将则回路上的边删除，若出现孤点，则忽略，则删除边后的子图仍然保有原图的性质，即子图中间的节点的度数为偶数，且子图与删除掉的回路一定有公共顶点，以该点作为起点继续找回路，然后删除，重复以上过程，直到所有的边都被删除为止，则所有这些删除的回路一定可连接，构成了一条欧拉回路；

      综上，得证；

   综上，得证；

2. 若图 G 存在且仅存在 2 个度为奇数的端点时，则图 G 有欧拉通路，其起点为其中 1 个度为奇数的端点，终点为另一个度为奇数的端点，即在无向连通多重图中存在欧拉通路且不存在欧拉回路当且仅当连通图中有且只用两个顶点的度数为奇数；

   对于上述定理，证明如下，

   1. 先证明其充分性，即存在欧拉通路则图中有且只有两个顶点的度数为奇数，其他顶点的度数皆为偶数；

      由于要遍历完图中所有的节点，则对于除起点与终点外的每一个节点，一定在一次遍历时，通过一条边来到这个节点，并通过另一条边离开，所以其度数一定为偶数，则对于起点与终点，通过一条边从起点出发，遍历所有节点，遍历完后，则再通过一条边到达终点，所以起点与终点的度数为奇数；

      则得证；

   2. 再证明其必要性，即连通图中有且只有两个奇数度顶点，则必然存在欧拉通路；

      则可将起点与终点进行连接，则原图中所有得节点度数均为偶数，又由于 连通图中所有顶点的度数为偶数，则必然存在欧拉回路 ，所以将连接的边删除后，可得到欧拉通路；

      则得证；

   综上，得证；

3. 若不满足上述情况，则不存在欧拉回路与欧拉通路；

2. 有向图

若有向图 G 为连通图，则可通过出，入度的大小判断图 G 是否存在欧拉通路或回路，有；

1. 若图 G 所有节点的入度等于出度，则图 G 有欧拉回路，即有向连通多重图中存在欧拉回路当且仅当图中所有顶点的入度数等于出度数；

   证明如下，

   由于要遍历完图中所有的节点，则对于除起点外的每一个节点，一定在一次遍历时，通过一条边来到这个节点，并通过另一条边离开，所以其入度等于出度，则对于起点，通过一条边从起点出发，遍历所有节点，遍历完后，则再通过一条边返回，所以起点的入度也一定等于出度；

   则得证；

2. 若图 G 存在且仅存在 2 个节点的入度不等于出度，且一个节点入度比出度大 1 ，一个入度比出度小 1 ，则图 G 有欧拉通路，其起点为入度比出度小 1 的节点，终点为节点入度比出度大 1 节点，即有向连通多重图中存在欧拉通路且不存在欧拉回路当且仅当连通图中有且只用两个顶点的入度不等于出度，且一个节点入度比出度大 1 ，另一个入度比出度小 1 ；

   证明如下，

   由于要遍历完图中所有的节点，则对于除起点与终点外的每一个节点，一定在一次遍历时，通过一条边来到这个节点，并通过另一条边离开，所以其入度等于出度，则对于起点，通过一条边从起点出发，遍历所有节点，不需返回，所以入度比出度小 1 ，对于终点，通过一条边到达，所以其入度比出度大 1 ；

   则得证；

3. 若不满足上述情况，则不存在欧拉回路与欧拉通路；

三、解法

1. DFS

思路

对于无向图，则寻找图中的度数为奇数的点，若没有则从任意节点开始搜索；

对于有向图，则寻找图中入度比出度小 1 的点，若没有则从任意节点开始搜索；

对节点  搜索时，搜索与  相邻的节点  ，并删除  边，继续递归搜索  即可；

代码

以 欧拉回路 为例；

 

code

 #include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAXN 200005
using namespace std;
int f, n, m, in[MAXN], out[MAXN], s, pos = 1, ans[MAXN], cnt;
bool vis[MAXN], vise[MAXN];
struct edge {
	int to, tot;
};
vector <edge> g[MAXN];
void dfs(int i) {
	vis[i] = true;
	while (!g[i].empty()) { // 遍历并删除
		int v = g[i].back().to, tot = g[i].back().tot;
		g[i].pop_back();
		if (!vise[abs(tot)]) {
			vise[abs(tot)] = true; // 标记已走过的边
			dfs(v);
			ans[++cnt] = tot; // 存入路径
		}
	}
	return;
}
int main() {
	scanf("%d", &f);
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		g[x].push_back(edge({y, i}));
		if (f == 1) g[y].push_back(edge({x, -i})); // 双向存边，记录反向
		in[x]++, out[y]++;
	}
	if (m == 0) {
		printf("YES\n");
		return 0;
	}
	if (f == 1) {
		for (int i = 1; i <= n; i++) {
			if ((in[i] + out[i]) % 2 == 1) { // 找起点
				printf("NO");
				return 0;
			} else if (in[i] + out[i]) {
				pos = i;
			}
		}
	} else {
		for (int i = 1; i <= n; i++) {
			if (in[i] != out[i]) { // 找起点
				printf("NO");
				return 0;
			} else if (in[i]) {
				pos = i;
			}
		}
	}
	dfs(pos); // 搜索
	for (int i = 1; i <= n; i++) {
		if ((in[i] || out[i]) && !vis[i]) { // 判断合法
			printf("NO\n");
			return 0;
		}
	}

	printf("YES\n");
	for (int i = cnt; i >= 1; i--) { // 输出
		if (f == 2) ans[i] = abs(ans[i]);
		printf("%d ", ans[i]);
	}
	return 0; 
}

 

2 . Fleury

思路

设 G 为无向欧拉图，则求 G 中欧拉回路算法为，

1. 取 G 中一顶点  ，另  ；
2. 假设沿  走到点  ，则按下方法从  中选  ；
   1.  与  有连边；
   2. 除非无边选择，否则  不应是  的桥；
3. 2 无法继续时，算法停止；

结束时，得到的回路  为欧拉回路；

代码

以 欧拉回路 为例；

Code

 #include <cstdio>
#include <stack>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAXN 200005
using namespace std;
int f, n, m, in[MAXN], out[MAXN], pos = 1, ans[MAXN], cnt;
bool vis[MAXN], vise[MAXN];
struct edge {
	int to, tot;
};
vector <edge> g[MAXN];
stack <int> s;
void dfs(int i) {
	vis[i] = true;
	while (!g[i].empty()) { // 遍历并删除
		int v = g[i].back().to, tot = g[i].back().tot;
		g[i].pop_back();
		if (!vise[abs(tot)]) {
			vise[abs(tot)] = true; // 标记已走过的边
			dfs(v);
			ans[++cnt] = tot; // 存入路径
		}
	}
	return;
}
void fleury(int x) {
    s.push(x);
    while (!s.empty()) {
        bool flag = false;
        if (!g[s.top()].empty()) { // 有边相连
            int y = s.top();
            s.pop();
            dfs(y);
        } else { // 无边相连
            s.pop();
        }
    }
    return;
}
int main() {
	scanf("%d", &f);
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		g[x].push_back(edge({y, i}));
		if (f == 1) g[y].push_back(edge({x, -i})); // 双向存边，记录反向
		in[x]++, out[y]++;
	}
	if (m == 0) {
		printf("YES\n");
		return 0;
	}
	if (f == 1) {
		for (int i = 1; i <= n; i++) {
			if ((in[i] + out[i]) % 2 == 1) { // 找起点
				printf("NO");
				return 0;
			} else if (in[i] + out[i]) {
				pos = i;
			}
		}
	} else {
		for (int i = 1; i <= n; i++) {
			if (in[i] != out[i]) { // 找起点
				printf("NO");
				return 0;
			} else if (in[i]) {
				pos = i;
			}
		}
	}
	fleury(pos); // 搜索
	for (int i = 1; i <= n; i++) {
		if ((in[i] || out[i]) && !vis[i]) { // 判断合法
			printf("NO\n");
			return 0;
		}
	}

	printf("YES\n");
	for (int i = cnt; i >= 1; i--) { // 输出
		if (f == 2) ans[i] = abs(ans[i]);
		printf("%d ", ans[i]);
	}
	return 0; 
}

 

eg.一笔画问题

Code

 #include <bits/stdc++.h>
using namespace std;
int g[1005][1005], ans[1005], num[1005], idx = 0, n, m, st = 1;
;
void dfs(int i) {
    for (int j = 1; j <= n; j++) {
        if (g[i][j]) {
            g[i][j] = g[j][i] = 0;
            dfs(j);
        }
    }
    ans[++idx] = i;
}
int main() {
    memset(g, 0, sizeof(g));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x][y] = g[y][x] = 1;
        num[x]++;
        num[y]++;
    }
    for (int i = 1; i <= n; i++) {
        if (num[i] % 2)
            st = i;
    }
    dfs(st);
    for (int i = 1; i <= idx; i++) {
        printf("%d ", ans[i]);
    }
    return 0;
}

4.哈密顿路

  哈密顿路径也称作哈密顿链，指在一个图中沿边访问每个顶点恰好一次的路径。

Code

 #include<bits/stdc++.h>
using namespace std;
int n,a[105][105],ans=0;
bool mp[105];
void dfs(int k,int t)
{
    if(t==n){
        ans++;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(a[k][i]==1 &&mp[i]==true)
        {
            mp[i]=false;
            dfs(i,t+1);
            mp[i]=true;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++){
        memset(mp,true,sizeof(mp));
        mp[i]=false;
        dfs(i,1);
    }
    printf("%d",ans);
    return 0;
}

四.最短路问题

  最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

1.Floyd

佛洛伊德是最简单的最短路径算法，可以计算图中任意两点间的最短路径。时间复杂度为O(N³)，适用于出现负边权的情况。 

算法描述：

(a)初始化：点u、v如果有边相连，则F[u][v]=w[u][v] 

如果不相连，则

for(int k=1;k<=n;k++) {
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				F[i][j]=max(F[i][j],F[i][k]+F[k][j]);
			}
		}
	}

(c)算法结束：F[i][j]得出的就是任意起点i到任意终点j的最短路径。

疑问：为什么枚举中间点的循环k要放在最外层？ 

Answer

 可以从一定不经过k点与一定经过k点的三维数组比较中推导出来
动态规划以”途径点集大小”为阶段？
决策需要枚举中转点，不妨考虑也以中转点集为阶段
F[k,i,j]表示”可以经过标号≤k的点中转时”从i到j的最短路
F[0,i,j]=W[i,j]，W为前面定义的邻接矩阵
F[k,i,j]=min{F[k-1,i,j] , F[k-1,i,k]+F[k-1,k,j]}，O(N^3)
k这一维空间可以省略，变成F[i,j]
就成为了我们平时常见的Floyd算法
由于k是DP的阶段循环，所以k循环必须要放在最外层

动态规划以”途径点集大小”为阶段？

决策需要枚举中转点，不妨考虑也以中转点集为阶段 F[k,i,j]表示”可以经过标号≤k的点中转时”从i到j的最短路 F[0,i,j]=W[i,j]，W为前面定义的邻接矩阵 F[k,i,j]=min{F[k-1,i,j] , F[k-1,i,k]+F[k-1,k,j]}，O(N³)

k这一维空间可以省略，变成F[i,j] 就成为了我们平时常见的Floyd算法 由于k是DP的阶段循环，所以k循环必须要放在最外层 。

也就是说每进行一次K的循环，计算的都是任意两点之间只经过前K个中转点（可以不选）的最短路。

使用floyd输出最短路径 

  Floyd算法输出路径也是采用记录前驱点的方式。因为floyd是计算任意两点间最短路径的算法，F[i][j]记录从i到j的最短路径值。故我们定义pre[i][j]为一个二维数组，记录从i到j的最短路径中，j的前驱点是哪一个。递归还原路径。

初始化pre[i][i]为0，输入相连边时，重置相连边尾结点的前驱   

若有无向边：pre[a][b]=a;  pre[b][a]=b; 更新若floyd最短路有更新，那么pre[i][j]=pre[k][j];

Q：(这能不能直接赋值k的值？)

Answer

 不能，因为不一定选了第K个点。

递归输出指两点s，e的最短路，先输出起点s，再将终点e放入递归，输出s+1~e的所有点。 

Code

 void print(int x) {    
    if(pre[s][x]==0) return; 
    print(pre[s][x]);
    printf(“->%d”,x);
}

 

2.Dijkstra

预备知识：松弛操作

  原来用一根橡皮筋连接a,b两点，现在有一点k，使得a->k->b比a->b的距离更短，则把橡皮筋改为a->k->b，这样橡皮筋更加松弛。这样说或许不好理解，毕竟两点之间线段最短是常识。可以这样想，如果今天我要去罗马，有很多种选择。当然选择最短的路。但如果最短的那条路太堵了，还不如选远一点但不堵的呢,就可以试着转站。这就是带权的最短路问题。

if(dis[b]<dis[k]+w[k][b])
    dis[b]=dis[k]+w[k][b]

结点分成两组：已经确定最短路、尚未确定最短路 不断从第2组中选择路径长度最短的点放入第1组并扩展 本质是贪心，只能应用于正权图 普通的Dijkstra算法O(N^2) 堆优化的Dijkstra算法O(NlogN)~O(MlogN)

 

算法描述：

设起点为s，dis[v]表示从指定起点s到v的最短路径，pre[v]为v的前驱，用来输出路径

(a)初始化

memset(dis,+∞)，memset(vis,false)；

(v:1~n)dis[v]=w[s][v]；

dis[s]=0；pre[s]=0；

vis[s]=true；

(b)for(i=1;i<=n-1;i++)

①在没有被访问过的点中找一个相邻顶点k，使得dis[k]是最小的；

②k标记为已确定的最短路vis[k]=true;

③用for循环更新与k相连的每个未确定最短路径的顶点v (所有未确定最短路的点都松弛更新)

if(dis[k]+w[k][v]<dis[v]) dis[v]=dis[k]+w[k][v],pre[v]=k;

(c)算法结束dis[v]为s到v的最短路距离；pre[v]为v的前驱结点，用来输出路径。

 

 

Code

 #include <bits/stdc++.h>
using namespace std;
int n,m,s,t;
const int N =100001;
int dis[N];//从起始点到i的最短路 
int vis[N];//是否确定最短路 
struct edge {
    int v,w;
};
struct node {
    int u,dis;//下标,距离 
    bool operator<(const node &tmp)
    const {
        return dis>tmp.dis;//让还没有确定最短路的数以距离 从小到大，每一次选最小的作为松弛点 
    }
};
priority_queue<node> Q;
vector<edge> G[N];
int Dijkstra(int S,int T) {
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[S]=0; 
	Q.push((node){S,0});//将起点压入队列 
    while(!Q.empty()) {
    	int u=Q.top().u;//取出起点下标  
    	Q.pop();
    	if(vis[u]) continue;//如果已经确定最短路径，continue 
    	vis[u]=1;
    	int v,w,siz=G[u].size();
    	for(int i=0;i<siz;i++) {//枚举与u相邻的点 
    		v=G[u][i].v,w=G[u][i].w;//取出与它相邻点下的标，与它的距离 
    		if(dis[v]>dis[u]+w) {//将起点到此相邻点的距离 与将u作为起点到v的松弛点比较（进行松弛操作） 
    			dis[v]=dis[u]+w;
    			Q.push((node){v,dis[v]}); //如果进行松弛操作，压入队列 
			}
		}
	}
	return dis[T]; 
}
int main()
{
    int u,v,w;
    scanf("%d %d %d %d",&n,&m,&s,&t);
    for(int i=0;i<m;i++) {
        scanf("%d %d %d",&u,&v,&w);
        G[u].push_back((edge){v,w});
        G[v].push_back((edge){u,w});
    }
    cout<<Dijkstra(s,t);
    return 0;
}

3.Bellman-Ford算法 与SPFA算法

Bellman-Ford算法：对每条边执行更新，迭代N-1次。 具体操作是对图进行最多n-1次松弛操作，每次操作对所有的边进行松弛，为什么是n-1次操作呢？这是因为我们输入的边不一定是按源点由近至远，万一是由远至近最坏情况就得n-1次，我们可以以一个单链A→B→C→D来举例(由老师写黑板吧) 可以应用于负权图 

SPFA:对每条边执行更新，迭代N-1次 SPFA = 队列优化的Bellman-Ford算法 本质上还是迭代——每更新一次就考虑入队 稀疏图上O(kN)，稠密图上退化到O(N^2)

SLF优化：Small Label First, 新入队点与队头比较

LLL优化：Large Label Last, 队头与平均值比较 可以应用于有向负权图 

算法实现：

在Bellmanford算法中，有许多松弛是无效的。这给了我们很大的改进的空间。SPFA算法正是对Bellmanford算法的改进。它是由西南交通大学段丁凡1994提出的。它采用了队列和松弛技术。先将源点加入队列。然后从队列中取出一个点(此时该点为源点)，对该点的邻接点进行松弛，如果该邻接点松弛成功且不在队列中，则把该点加入队列。如此循环往复，直到队列为空，则求出了最短路径。          

判断有无负环：如果某个点进入队列的次数超过N次则存在负环 ( 存在负环则无最短路径,如果有负环则会无限松弛,而一个带n个点的图至多松弛n-1次)  

queue<int> Q;
int dis[MAXN+5];
bool vis[MAXN+5];
vector<edge> G[MAXN+5];
int SPFA(int s,int t) {
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0,vis[s]=1,Q.push(s);
	while(!Q.empty()) {
		int u=Q.front();
		Q.pop();
		for(int i=0;i<G[u].size();i++) {
			int v=G[u][i].v,w=G[u][i].w;
			if(dis[v]>=dis[u]+w) {
				dis[v]=dis[u]+w;
				if(!vis[v]) 
					vis[v]=1,Q.push(v);
			}
		}
	}
	return dis[t];
}

 

五.最小生成树

  树有这样一个定理：N个点用N-1条边连接成一个连通块，形成的图形只可能是树，叫做生成树！因此，一个有N个点的连通图，边一定是≥N-1条的！特别的 口袋的天空 ，如果想要连出k棵树，就需要连n-k条边。

1.Kruskal算法 

  利用并查集维护。初始时每个点单独为一个集合，把边的权值从小到大排序后依次扫描。如果这条边的u，v在一个集合，那么如果把u，v连上就会形成一个回路，因此不管（见下图）。如果不在一个集合，就合并。

很显然，按照我们的思路，权值为3的这条边是不应该被连的。又因为前面排过序，保证了最小值的准确性

证明

  思路很简单，为了造出一棵最小生成树，我们从最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了 n-1 条边，即形成了一棵树。

 证明：使用归纳法，证明任何时候 K 算法选择的边集都被某棵 MST 所包含。

 基础：对于算法刚开始时，显然成立（最小生成树存在）。

 归纳：假设某时刻成立，当前边集为F ，令  T为这棵 MST，考虑下一条加入的边e 。

如果 e 属于T ，那么成立。

否则，T+e 一定存在一个环，考虑这个环上不属于 F 的另一条边 f（一定只有一条）。

首先，f 的权值一定不会比 e 小，不然 f 会在  e之前被选取。

然后，f 的权值一定不会比 e 大，不然T+e-f  就是一棵比 T还优的生成树了。

所以，T+e-f 包含了F ，并且也是一棵最小生成树，归纳成立。

具体流程

(a)初始化

①写出找祖先函数int find_father(int x)

②写出合并函数void union_set(int x , int y)

③写出sort的cmp(结构体a.u , a.v , a.w),对存在的边权(a.w)从小到大排序

④主函数里面：for输入边，for把每个点的父节点初始化为自己,sort排序

⑤MST=0

 

(b)for(i=1;i<=m;i++)

①if两个点的祖先不是同一个,连接两个点,MST+=边权,边+1;

②if(边==n-1)break;

 

(c)算法结束：MST即为最小生成树的权值之和。 

Code

 #include<bits/stdc++.h>
using namespace std;
struct edge {
	int u,v,c;
}G[10005];
int fa[10005];
int Find(int x) {
	if(fa[x]==x) return x;
	return fa[x]=Find(fa[x]);
}
bool cmp(edge x,edge y) {
	return x.c<y.c;
}
int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) 
    	fa[i]=i;
    for(int i=1;i<=m;i++) {
    	scanf("%d %d %d",&G[i].u,&G[i].v,&G[i].c);
	}
	sort(G+1,G+m+1,cmp);
	int cnt=0,sum=0;
	for(int i=1;i<=m;i++) {
		int x=Find(G[i].u),y=Find(G[i].v);
		if(x==y) continue;
		fa[x]=y;
		sum=max(G[i].c,sum);
		cnt++;
		if(cnt==n) break;
	}
	printf("%d %d",n-1,sum);
    return 0;
}

2.Prim算法

笔者还是更喜欢Kruskal

以任意一个点为基准点 节点分为两组：

1. 在MST上到基准点的路径已经确定的点

2. 尚未在MST中与基准点相连的点

不断从第2组中选择与第1组距离最近的点加入第1组 类似于Dijkstra，本质也是贪心，O(N^2) 

 

具体流程

  也使用“蓝白点”思想，白点代表已进入最小生成树的点，蓝点代表未进入最小生成树的点。以1为起点生成最小生成树，min[v]表示蓝点v与白点相连的最小边权，MST表示最小生成树的权值之和。

  (a)初始化：min[v]=∞(v≠1);  min[1]=0;  MST=0;

  (b)for(i=1;i<=n;i++)

    ①for寻找min[u],最小的蓝点u;

    ②将u标记为白点;

    ③MST+=min[u];

    ④for与白点u相连的所有蓝点v(可暴力枚举，更好的是求vector的size) 

      if(w[u][v]<min[v])   min[v]=w[u][v];

  (c)算法结束：MST即为最小生成树的权值之和。 

 

Code

 #include<bits/stdc++.h>
using namespace std;
int n,ans, a[105][105],m[105],p[105];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	    for (int j=1;j<=n;j++)
	        scanf("%d",&a[i][j]);
	memset(m,0x3f,sizeof(m));  
	memset(p,0,sizeof(p));
	m[1]=0;  
	for (int i=1;i<=n;i++)
	{
		int k=0;
		for (int j=1;j<=n;j++)
		    if (p[j]==0&&m[j]<m[k])
		       k=j;  
		p[k]=1;
		ans+=m[k];  
		for (int j=1;j<=n;j++)
		    if (p[j]!=1&&a[k][j]<m[j])
		       m[j]=a[k][j];  
	}
	cout<<ans<<endl;
	return 0;
}

堆优化和邻接表就不写了吧……（心虚……）

 

六.严格次小生成树

1. 非严格次小生成树算法

  先使用最小生成树算法（Kruscal）计算最小生成树边权和，再逐一枚举新加的一条边（次小生成树一点是在最小生成树中删去一条边、增加一条边），此时会出现一个环，将环上除了添加的边以外的最大的边删去（贪心），即可得到一种生成树的方法，更新新的生成树的边权和的最小值即可。

  但题目要求严格次小生成树（边权和严格大于最小生成树的边权和）时这种贪心的方法是不正确的，反例如下：

  此图的次小生成树边权和为11（1-2，2-4，3-4，3-5）。

  可以在最小生成树中加上3-4边删去1-3边，但此算法在加入3-4边时处理1-2-4-3-1的环时最大值在2-4边，为3，此时次小生成树的边权与最小生成树一样，因为要求严格次小生成树，不会考虑，而会选择用加上4-5边，结果为12，不符。

1. 严格次小生成树生成树算法（Kruskal+树上倍增lca）

Kruskal

  求解最小生成树，再根据最小生成树的边权和更换边计算严格最小生成树。

树上倍增lca

  求解最小生成树后，通过替换最小生成树上的边可以求解次小生成树。

  在非严格次小生成树中，新添加的边的边权一定不小于最大值（否则就不是最小生成树），不能求出严格次小生成树（最大边可能等于添加的边的权值）。因此，对于严格次小生成树来说，不仅要求环上的最大值，还要求环上的次大值，这样在出现最大值等于边权时可以用次大值更新答案，保证答案正确性。

  设g[x][i] , maxl[x][i] , secl[x][i]分别表示在树上从x点向上走2^i层的结点编号、x点向上走2^i层遇到的边权的最大值、x点向上走2^i层遇到的边权的次大值，设i点与j点的最近公共祖先为k，则可以通过二进制分解和迭代得到i-k的最大值、次大值和j-k的最大值、次大值，枚举每一条不在最小生成树上的边更新答案即可。

 

Show time

图论の题（内含Kuglarz，棋盘上的守卫,走廊泼水节