图论
一、基本概念
图（graph）是数据结构和算法学中最强大的框架之一（或许没有之一）。图几乎可以用来表现所有类型的结构或系统，从交通网络到通信网络，从下棋游戏到最优流程，从任务分配到人际交互网络，图都有广阔的用武之地。
而要进入图论的世界，清晰、准确的基本概念是必须的前提和基础。下面对其最核心和最重要的概念作出说明。关于图论的概念异乎寻常的多，先掌握下面最核心最重要的，足够开展一些工作了，其它的再到实践中不断去理解和熟悉吧。
图（graph）并不是指图形图像（image）或地图（map）。通常来说，我们会把图视为一种由“顶点”组成的抽象网络，网络中的各顶点可以通过“边”实现彼此的连接，表示两顶点有关联。注意上面图定义中的两个关键字，由此得到我们最基础最基本的2个概念，顶点（vertex）和边（edge）。直接上图吧。
1.顶点(Vertex)
上图中黑色的带数字的点就是顶点，表示某个事物或对象。由于图的术语没有标准化，因此，称顶点为点、节点、结点、端点等都是可以的。叫什么无所谓，理解是什么才是关键。
2.边(Edge)
上图中顶点之间蓝色的线条就是边，表示事物与事物之间的关系。需要注意的是边表示的是顶点之间的逻辑关系，粗细长短都无所谓的。包括上面的顶点也一样，表示逻辑事物或对象，画的时候大小形状都无所谓。
3.同构(Isomorphism)
先看看下面2张图：
首先你的感觉是这2个图肯定不一样。但从图（graph）的角度出发，这2个图是一样的，即它们是同构的。前面提到顶点和边指的是事物和事物的逻辑关系，不管顶点的位置在哪，边的粗细长短如何，只要不改变顶点代表的事物本身，不改变顶点之间的逻辑关系，那么就代表这些图拥有相同的信息，是同一个图。同构的图区别仅在于画法不同。
4.有向、无向图(Directed Graph/ Undirected Graph)
最基本的图通常被定义为“无向图”，与之对应的则被称为“有向图”。两者唯一的区别在于，有向图中的边是有方向性的。下图即是一个有向图，边的方向分别是：(1->2), (1-> 3), (3-> 1), (1->5), (2->3), (3->4), (3->5), (4->5), (1->6), (4->6)。要注意，图中的边(1->3)和(3->1)是不同的。有向图和无向图的许多原理和算法是相通的。
5.权重(Weight)
边的权重（或者称为权值、开销、长度等），也是一个非常核心的概念，即每条边都有与之对应的值。例如当顶点代表某些物理地点时，两个顶点间边的权重可以设置为路网中的开车距离。下图中顶点为4个城市:Beijing, Shanghai, Wuhan, Guangzhou，边的权重设置为2城市之间的开车距离。有时候为了应对特殊情况，边的权重可以是零或者负数，也别忘了“图”是用来记录关联的东西，并不是真正的地图。
6.路径/最短路径(Path/Shortest path)
在图上任取两顶点，分别作为起点（start vertex）和终点（end vertex），我们可以规划许多条由起点到终点的路线。不会来来回回绕圈子、不会重复经过同一个点和同一条边的路线，就是一条“路径”。两点之间存在路径，则称这2个顶点是连通的（connected）。
还是上图的例子，北京->上海->广州，是一条路径，北京->武汉->广州，是另一条路径，北京—>武汉->上海->广州，也是一条路径。而北京->武汉->广州这条路径最短，称为最短路径。 路径也有权重。路径经过的每一条边，沿路加权重，权重总和就是路径的权重（通常只加边的权重，而不考虑顶点的权重）。在路网中，路径的权重，可以想象成路径的总长度。在有向图中，路径还必须跟随边的方向。
值得注意的是，一条路径包含了顶点和边，因此路径本身也构成了图结构，只不过是一种特殊的图结构。
7.环(Loop)
环，也成为环路，是一个与路径相似的概念。在路径的终点添加一条指向起点的边，就构成一条环路。通俗点说就是绕圈。
上图中，北京->上海->武汉->广州->北京，就是一个环路。北京->武汉->上海->北京，也是一个环路。与路径一样，有向图中的环路也必须跟随边的方向。环本身也是一种特殊的图结构。
8.连通图/连通分量(connected graph/connected component)
如果在图G中，任意2个顶点之间都存在路径，那么称G为连通图（注意是任意2顶点）。上面那张城市之间的图，每个城市之间都有路径，因此是连通图。而下面这张图中，顶点8和顶点2之间就不存在路径，因此下图不是一个连通图，当然该图中还有很多顶点之间不存在路径。
上图虽然不是一个连通图，但它有多个连通子图：0,1,2顶点构成一个连通子图，0,1,2,3,4顶点构成的子图是连通图，6,7,8,9顶点构成的子图也是连通图，当然还有很多子图。我们把一个图的最大连通子图称为它的连通分量。0,1,2,3,4顶点构成的子图就是该图的最大连通子图，也就是连通分量。连通分量有如下特点：
1.是子图
2.子图是连通的
3.子图含有最大顶点数
注意：“最大连通子图”指的是无法再扩展了，不能包含更多顶点和边的子图。0,1,2,3,4顶点构成的子图已经无法再扩展了。
显然，对于连通图来说，它的最大连通子图就是其本身，连通分量也是其本身。
你是不是已经对没完没了的术语感到厌烦了。是的，不能再多了！有了这些，我们可以出发探索图论的世界了！
二、算法
1.图的两种实现：邻接表与邻接矩阵
邻接表：点这里
邻接矩阵：点这里
2.拓扑排序（邻接表实现）
定义：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
打个比方（转载自这儿）：
通常，我们把顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。
要对这些课程进行排序，当是比较少的课程时，我们可以直接理清楚课程的顺序，但是当课程达到很多时，我们就可以借助图来进行排序，首先我们需要建立一个图，在这里很容易想到，将课程作为图的顶点，在这里我们把边v->w看做v是w的预修课。
根据这个思路建立了如图所示的图：
根据建立的图进行拓扑排序将得到课程的顺序： c1 c2 c8 c4
c3 c13 c9 c5
c7 c6
c11 c12 c10 c15
c14
通过这个例子，应该对拓扑排序有了更深的理解.
步骤： 由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。 1.选择一个入度为0的顶点并输出之
2.从网中删除此顶点及所有出边
循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。
示例（默认无环）：
#include <iostream>
#include <cstring>
#define MAX 1005
#include <stack>
using namespace std;
struct nodeEdge
{
int to;
int next;
};
int vex[MAX],indegree[MAX],v_num,e_num,v_start,v_end,res[MAX];
nodeEdge arrPath[2*MAX];
void create_gragh(int v1,int v2,int curPos)
{
arrPath[curPos].to=v2;
arrPath[curPos].next=vex[v1];
vex[v1]=curPos;
indegree[v2]++;
}
void print_gragh()
{
for(int i=1;i<=v_num;i++)
{
cout<<i;
int j=vex[i];
while(j!=-1)
{
cout<<"->"<<arrPath[j].to;
j=arrPath[j].next;
}
cout<<endl;
}
}
void top_sort()
{
int cnt=0;
stack<int> s;
for(int i=1;i<=v_num;i++)
if(indegree[i]==0)
s.push(i);
while(!s.empty())
{
int index=s.top();
res[++cnt]=index;
s.pop();
int n=vex[index];
while(n!=-1)
{
if(--indegree[arrPath[n].to]==0);
{
s.push(arrPath[n].to);
}
n=arrPath[n].next;
}
}
if(cnt<v_num)
cout<<"There is a circle"<<endl;
for(int i=1;i<=v_num;i++)
cout<<res[i]<<" ";
cout<<endl;
}
int main()
{
cin>>v_num>>e_num;
memset(vex,-1,sizeof(vex));
for(int i=1;i<=e_num;i++)
{
cin>>v_start>>v_end;
create_gragh(v_start,v_end,i);
}
top_sort();
}
3.最短路：Floyd算法
#include <iostream>
#define MAX 1005
#define INF 100005
using namespace std;
int arr[MAX][MAX],v,e,v1,v2,w;
int main()
{
cin>>v>>e;
for(int i=1;i<=v;i++)
for(int j=1;j<=v;j++)
arr[i][j]=INF;
for(int i=1;i<=e;i++)
{
cin>>v1>>v2>>w;
arr[v1][v2]=w;
}
for(int k=1;k<=v;k++)
for(int i=1;i<=v;i++)
for(int j=1;j<=v;j++)
arr[i][j]=min(arr[i][j],arr[i][k]+arr[k][j]);
cout<<arr[1][v]<<endl;
}
4.最短路：dijkstra算法
#include <iostream>
#include <string>
#include <cstdio>
#define INF 1000005
#define MAX 1005
using namespace std;
int gragh[MAX][MAX],v,e,v1,v2,power,dij[MAX],minnum,minpos;
bool visit[MAX];
void init()
{
for(int i=1;i<=v;i++)
{
for(int j=1;j<=v;j++)
gragh[i][j]=INF;
gragh[i][i]=0;
}
}
void print_gragh()
{
for(int i=1;i<=v;i++)
{
for(int j=1;j<=v;j++)
printf("%7d ",gragh[i][j]);
cout<<endl;
}
}
void dijkstra()
{
for(int i=1;i<=v;i++)
dij[i]=INF;
dij[1]=0;
for(int i=1;i<=v;i++)
{
minnum=INF;
for(int j=1;j<=v;j++)
{
if(minnum>dij[j]&&!visit[j])
{
minpos=j;
minnum=dij[j];
}
}
visit[minpos]=true;
for(int j=1;j<=v;j++)
{
if(!visit[j])
dij[j]=min(dij[j],dij[minpos]+gragh[minpos][j]);
}
}
}
int main()
{
cin>>v>>e;
init();
for(int i=1;i<=e;i++)
{
cin>>v1>>v2>>power;
gragh[v1][v2]=gragh[v2][v1]=power;
}
dijkstra();
for(int i=1;i<=v;i++)
cout<<dij[i]<<" ";
cout<<endl;
}
5.最短路：SPFA算法
#include <iostream>
#include <queue>
#include <stack>
#define MAX 1005
#define INF 10000005
using namespace std;
int v,e,v1,v2,w,dis[MAX],gragh[MAX][MAX],judge[MAX],path[MAX];
bool visit[MAX];
stack<int> p;
void init()
{
for(int i=1;i<=v;i++)
{
for(int j=1;j<=v;j++)
gragh[i][j]=INF;
gragh[i][i]=0;
dis[i]=INF;
}
}
void spfa(int s)
{
queue<int> q;
q.push(s);
dis[s]=0;
visit[s]=true;
while(!q.empty())
{
int top=q.front();
q.pop();
visit[top]=false;
for(int i=1;i<=v;i++)
{
if(dis[i]>dis[top]+gragh[top][i])
{
dis[i]=dis[top]+gragh[top][i];
path[i]=top;
if(!visit[i])
{
q.push(i);
judge[i]++;
if(judge[i]>v)
{
cout<<"minus circle"<<endl;
return;
}
visit[i]=true;
}
}
}
}
}
void print_path(int k)
{
// if(k==1)
// return;
// else
// {
// cout<<path[k]<<"->";
// print_path(path[k]);
// }
if(k==1)
{
p.push(k);
return;
}
else
{
p.push(k);
print_path(path[k]);
}
}
int main()
{
cin>>v>>e;
init();
for(int i=1;i<=e;i++)
{
cin>>v1>>v2>>w;
gragh[v1][v2]=w;
}
spfa(1);
cout<<dis[v]<<endl;
print_path(v);
while(!p.empty())
{
cout<<p.top()<<" ";
p.pop();
}
}
例：Luogo P3905
#include <iostream>
#include <queue>
#define MAX 105
#define INF 10005
using namespace std;
int v,e,v1,v2,w,a,b,dis[MAX],gragh0[MAX][MAX],gragh[MAX][MAX],d;
bool visit[MAX];
void init()
{
for(int i=1;i<=v;i++)
{
for(int j=1;j<=v;j++)
gragh[i][j]=INF;
gragh[i][i]=0;
dis[i]=INF;
}
}
void create_gragh()
{
for(int i=1;i<=e;i++)
{
cin>>v1>>v2>>w;
gragh0[v1][v2]=gragh0[v2][v1]=w;
gragh[v1][v2]=gragh[v2][v1]=w;
}
cin>>d;
for(int i=1;i<=d;i++)
{
cin>>v1>>v2;
gragh0[v1][v2]=gragh0[v2][v1]=0;
}
for(int i=1;i<=v;i++)
for(int j=1;j<=v;j++)
gragh[i][j]-=gragh0[i][j];
}
void spfa(int s)
{
queue<int> q;
q.push(s);
dis[s]=0;
visit[s]=true;
while(!q.empty())
{
int index=q.front();
q.pop();
visit[index]=false;
for(int i=1;i<=v;i++)
{
if(dis[i]>dis[index]+gragh[index][i])
{
dis[i]=dis[index]+gragh[index][i];
if(!visit[i])
{
q.push(i);
visit[i]=true;
}
}
}
}
}
int main()
{
cin>>v>>e;
init();
create_gragh();
cin>>a>>b;
spfa(a);
cout<<dis[b]<<endl;
}
并查集
#include <iostream>
#define MAX 1005
using namespace std;
int root[MAX],height[MAX],n,m,v1,v2,cnt,a,b;
int find(int x)
{
int r=x;
while(root[r]!=r)
r=root[r];
return r;
}
void merge(int a,int b)
{
int x=find(a),y=find(b);
if(height[x]>height[y])
{
height[x]+=height[y];
root[y]=x;
}
else
{
height[y]+=height[x];
root[x]=y;
}
}
int main()
{
while(cin>>n)
{
cnt=0;
if(n==0)
break;
cin>>m;
for(int i=1;i<=n;i++)
{
root[i]=i;
height[i]=1;
}
for(int i=1;i<=m;i++)
{
cin>>a>>b;
merge(a,b);
}
for(int i=1;i<=n;i++)
if(root[i]==i)
cnt++;
cout<<cnt-1<<endl;
}
}
