基本概念
图由顶点（vertex，node）和边（edge）组成
顶点:图中的数据元素称为顶点.
有向图:有方向的图叫有向图.
无向图:没有方向的图叫无向图.
完全图:有n(n-1)/2条边的无向图称为完全图.
有向完全图:具有n(n-1)条弧的有向图称为有向完全图.
稀疏图:有很少条边或弧的图称为稀疏图,反之称为稠密图.
权:与图的边或弧相关的数叫做权(weight).
DAG：没有圈的有向图.
图的表示
1.邻接矩阵
2.邻接表
邻接表的实现：
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
const int MAX_V=10000;
vector<int> G[MAX_V];
//struct edge{ //边上有属性的情况
// int to,cost;
//};
//vector<edge> G[MAX_V];
int main()
{
int V,E,a,b;
scanf("%d%d",&V,&E);
for (int i = 0; i < E; i += 1)
{
scanf("%d%d",&a,&b);
G[a].push_back(b);
// 如果是无向图，加上下面这条
// G[b].push_back(a);
}
// 图的操作
// 。
// 。
// 。
return 0;
}
二分图搜索：（DFS）
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
const int MAX_V=10000;
vector<int> G[MAX_V];
int color[MAX_V];
bool dfs(int v,int c){
color[v]=c;
for (int i = 0; i < G[v].size(); i += 1)
{
if(color[G[v][i]]==c)return false;
if(color[G[v][i]]==0&&!dfs(G[v][i],-c))return false;
}
return true;
}
int main()
{
int V,E,a,b;
scanf("%d%d",&V,&E);
for(int i=0;i<V;i++)color[i]=0; //初始化
for (int i = 0; i < E; i += 1)
{
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
if(!dfs(0,1)){
printf("Not A Bipartite Graph");
}
else{
printf("YES");
}
return 0;
}
单源最短路问题
松弛操作：
void relax(int from,int to,int cost){ //一般不需要单独编写
if(d[from]!=INF&&d[to]>d[from]+cost){
d[to]=d[from]+cost;
}
}
1.Bellman-Ford算法
适用条件&范围：
a) 单源最短路径(从源点s到其它所有顶点v);
b) 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
c) 边权可正可负(如有负权回路输出错误提示);
d) 差分约束系统;
void short_path(int s){
for(int i=0;i<V;i++)D[i]=INF;
D[s]=0;
while(true){
bool update=false;
for (int i = 0; i < E; i += 1)
{
edge e=es[i];
if(D[e.from]!=INF&&D[e.to]>D[e.from]+e.cost){
D[e.to]=D[e.from]+e.cost;
update=true;
}
}
if(!update)break;
}
}
如果在图中不存在从s可达的负圈，那么最短路不会经过同一个顶点两次，（也就是说，最多通过|V|-1条边），while（1）的循环最多执行|V|-1次，因此，复杂度为O（|V|*|E|）。反之，如果存在从s可达的负圈，那么在第|V|次循环时也会更新d的值，因此可以检测负圈。如果一开始对所有的顶点i，都把d[i]初始化为0,那么可以查找出所有的负圈.
bool find_negative_loop(){
memset(D,0,sizeof(D));
for (int i = 0; i < V; i += 1)
{
for (int j = 0; j < E; j += 1)
{
edge e=es[j];
if(D[e.to]>D[e.from]+e.cost){
D[e.to]=D[e.from]+e.cost;
//如果第V次依旧更新了,则存在负圈
if(i==V-1)return true;
}
}
}
return false;
}
2.Dijkstra算法
适用条件&范围：
a) 单源最短路径(从源点s到其它所有顶点v);
b) 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)
c) 所有边权非负(任取(i,j)∈E都有Wij≥0);
struct edge
{
int to,cost;
};
typedef pair<int,int> P; //first是最短距离,second是顶点的编号.
int V;
const int MAX_V=100000,INF=INT32_MAX;
vector<edge> G[MAX_V];
int d[MAX_V];
void dijkstra(int s){
//通过指定greater参数,堆按照first从小到达排列
priority_queue< P,vector<P>,greater<P> > que;
fill(d,d+V,INF);
d[s]=0;
que.push(P(0,s));
while (!que.empty())
{
P p=que.top();que.pop();
int v=p.second;
if(p.first>d[v])continue;
for (unsigned int i = 0; i < G[v].size(); i += 1)
{
edge e=G[v][i];
if (d[e.to]>d[v]+e.cost)
{
d[e.to]=d[v]+e.cost;
que.push(P(d[e.to],e.to));
}
}
}
}
任意两点间的最短路问题(Floyd-Warshall算法)
适用范围：
a) APSP(All Pairs Shortest Paths)
b) 稠密图效果最佳
c) 边权可正可负
利用DP来解决.对于任意两点,只使用顶点0~k和i,j的情况下,记i到j的最短路长度为d[k][i][j].k=-1时,认为只使用i和j,所以d[-1][i][j]=cost[i][j].
接下来把只使用顶点0k的问题归结到只使用0k-1:
只使用0~k-1时,分i到j的最短路正好经过顶点k一次和完全不经过顶点k的情况来讨论.不经过时,d[k][i][j]=d[k-1][i][j];经过时,d[k][i][j]=d[k-1][i][k]+d[k-1][k][i];
所以d[k][i][j]=min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j]),显然可以用一个二维数组,不断进行d[i][j]=min(d[i][j],d[i][k]+d[k][j])更新来实现.
int d[MAX_V][MAX_V]; //d[u][v]表示边e=(u,v)的权值,不存在时设为INF,不过d[i][i]=0;
int V; //顶点数;
void warshall_floyd(){
for (int k = 0; k < V; k += 1)
{
for (int i = 0; i < V; i += 1)
{
for (int j = 0; j < V; j += 1)
{
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
return;
}
路径还原
1.
输出时可能会遇到一点难处，我们记的是每个点“前面的”点是什么，输出却要从最前面往最后面输，这不好办。其实很好办，见如下递归方法
void PrintPath(int k){
if( Path[k] ) PrintPath(Path[k]);
fout<<k<<' ';
}
#include<iostream> #include<memory.h> #include<stdio.h> #include<queue> #include <vector> #include<algorithm>using namespace std;
struct edge
{
int to,cost;
};
typedef pair<int,int> P; //first是最短距离,second是顶点的编号.
int V;
const int MAX_V=100000,INF=INT32_MAX;
vector<edge> G[MAX_V];
int pre[MAX_V]; //
int d[MAX_V];void dijkstra(int s){
priority_queue< P,vector<P>,greater<P> > que;
fill(d,d+V,INF);
fill(pre,pre+V,-1); //
d[s]=0;
que.push(P(0,s));
while (!que.empty())
{
P p=que.top();que.pop();
int v=p.second;
if(p.first>d[v])continue;
for (unsigned int i = 0; i < G[v].size(); i += 1)
{
edge e=G[v][i];
if (d[e.to]>d[v]+e.cost)
{
pre[e.to]=v; //
d[e.to]=d[v]+e.cost;
que.push(P(d[e.to],e.to));
}
}
}
}
vector<int> get_path(int t){ //
vector<int> path;
for (;t!=-1;t=pre[t])path.push_back(t);
//翻转
reverse(path.begin(),path.end()); //#include<algorithm>
return path;
}
int main()
{return 0;}
最小生成树
Prim算法(Dijksta的推广)
适用范围：
a) MST(Minimum Spanning Tree,最小生成树)
b) 无向图(有向图的是最小树形图)
c) 多用于稠密图
#include<iostream>
#include<memory.h>
#include<stdio.h>
#include<queue>
#include <vector>
using namespace std;
int V,E;
const int MAX_V=10000,INF=INT32_MAX;
int cost[MAX_V][MAX_V]; //表示边(u,v)的权值,如果不存在,初始化为INF
int mincost[MAX_V];
bool used[MAX_V];
int prim(){
fill(mincost,mincost+V,INF);
fill(used,used+V,false);
mincost[0]=0;
int ans=0;
while(1){
int v=-1;
for (int i = 0; i < V; i += 1)
{
if(!used[i]&&(v==-1||mincost[v]>mincost[i]))v=i;
}
if(v==-1)break;
used[v]=true;
ans+=mincost[v];
for (int i = 0; i < V; i += 1)
{
mincost[i]=min(mincost[i],cost[v][i]);
}
}
return ans;
}
int main()
{
scanf("%d %d",&V,&E);
int a,b,c;
for (int i = 0; i < V; i += 1)
{
for (int j = 0; j < V; j += 1)
{
cost[i][j]=INF;
}
}
for (int i = 0; i < E; i += 1)
{
scanf("%d %d %d",&a,&b,&c);
cost[a][b]=c;
cost[b][a]=c;
}
cout<<prim()<<endl;
return 0;
}
这是朴素的prim算法,复杂度为O(VV),可用堆来维护mincost数组优化到O(ElogV)但是过于繁杂,不推荐使用.
Kruskal算法
适用范围：
a) MST(Minimum Spanning Tree,最小生成树)
b) 无向图(有向图的是最小树形图)
c) 多用于稀疏图
d) 边已经按权值排好序给出
#include<iostream>
#include<memory.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
int V,E;
const int MAX_V=1000,MAX_E=1000,INF=INT32_MAX;
int par[MAX_V],ranks[MAX_V]; //并查集
int find(int x){
if(par[x]==x)return x;
else return par[x]=find(par[x]);
}
void unite(int x,int y){
x=find(x);
y=find(y);
if(x==y)return;
if(ranks[x]<ranks[y]){
par[x]=y;
}else{
par[y]=x;
if(ranks[x]==ranks[y])ranks[x]++;
}
}
bool same(int x,int y){
return find(x)==find(y);
}
void init(int n){
for (int i = 0; i < n; i += 1)
{
par[i]=i;
ranks[i]=1;
}
}
struct edge //
{
int u,v,cost;
};
edge es[MAX_E];
bool cmp(edge a,edge b){
return a.cost<b.cost;
}
int kruskal(){
sort(es,es+E,cmp);
init(V); //并查集初始化
int res=0;
for (int i = 0; i < E; i += 1)
{
edge e=es[i];
if(!same(e.u,e.v)){
unite(e.u,e.v);
res+=e.cost;
}
}
return res;
}
int main()
{
scanf("%d %d",&V,&E);
int a,b,c;
for (int i = 0; i < E; i += 1)
{
scanf("%d %d %d",&a,&b,&c);
es[i].u=a;
es[i].v=b;
es[i].cost=c;
}
cout<<kruskal()<<endl;
return 0;
}
Kruskal算法在排序上最费时,算法的复杂度为O(E*logV),理解起来很容易,注意写好并查集.
参考博客: [ACM算法]图的基本知识
暂时这么多,剩下的以后再补~
补充:
SPFA算法
求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm，是西南交通大学段凡丁于1994年发表的。从名字我们就可以看出，这种算法在效率上一定有过人之处。很多时候，给定的图存在负权边，这时类似Dijkstra算法等便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。简洁起见，我们约定加权有向图G不存在负权回路，即最短路径一定存在。如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
int spfa_bfs(int s)
{
queue <int> q;
memset(d,0x3f,sizeof(d));
d[s]=0;
memset(c,0,sizeof(c));
memset(vis,0,sizeof(vis));
q.push(s); vis[s]=1; c[s]=1;
//顶点入队vis要做标记，另外要统计顶点的入队次数
int OK=1;
while(!q.empty())
{
int x;
x=q.front(); q.pop(); vis[x]=0;
//队头元素出队，并且消除标记
for(int k=f[x]; k!=0; k=nnext[k]) //遍历顶点x的邻接表
{
int y=v[k];
if( d[x]+w[k] < d[y])
{
d[y]=d[x]+w[k]; //松弛
if(!vis[y]) //顶点y不在队内
{
vis[y]=1; //标记
c[y]++; //统计次数
q.push(y); //入队
if(c[y]>NN) //超过入队次数上限，说明有负环
return OK=0;
}
}
}
}
return OK;
}
int spfa_dfs(int u)
{
vis[u]=1;
for(int k=f[u]; k!=0; k=e[k].next)
{
int v=e[k].v,w=e[k].w;
if( d[u]+w < d[v] )
{
d[v]=d[u]+w;
if(!vis[v])
{
if(spfa_dfs(v))
return 1;
}
else
return 1;
}
}
vis[u]=0;
return 0;
}
