栈stack：
1 struct sta 2 { 3 int sz[100001]; 4 int top() 5 { 6 return sz[top]; 7 } 8 void push(int x){ 9 sz[++top]=x; 10 } 11 void pop(){ 12 if(top>0) 13 top--; 14 } 15 void cl() 16 { 17 top=0; 18 } 19 int size(){ 20 return top; 21 } 22 }stack;
队列queue：
1 #define MAXN 10000 2 struct queue{ 3 int sz[10000]; 4 int head,tail; 5 queue() 6 { 7 head=0; 8 tail=0; 9 } 10 queue() 11 { 12 head=0; 13 tail=0; 14 delete []sz; 15 } 16 int front() 17 { 18 if(!empty()) 19 return sz[head]; 20 } 21 bool empty() 22 { 23 return (head>=0&&tail>=0&&head==tail||head>tail); 24 } 25 bool full() 26 { 27 return tail>=MAXN; 28 } 29 int push(int x) 30 { 31 if(!full()) 32 sz[tail++]=x; 33 } 34 void pop() 35 { 36 if(!empty()) 37 ++head; 38 } 39 }
Tarjan：
链接：tarjan算法详解
代码：
1 #include<iostream> 2 using namespace std; 3 #include"cstdio" 4 #include<cstring> 5 int head[1001],DFN[1001],LOW[1001]; 6 struct node{ 7 int next; 8 int v; 9 }edge[1001]; 10 int stack[1001],n,m,tot,num,index; 11 int visit[10001]; 12 void add(int x,int y) 13 { 14 edge[++num].next=head[x]; 15 edge[num].v=y; 16 head[x]=num; 17 return; 18 } 19 void tarjan(int x)//代表第几个点在处理。递归的是点。 20 { 21 DFN[x]=LOW[x]=++tot;//新进的点初始化 22 stack[++index]=x;//jin jnzhan 23 visit[x]=1;//表示在栈里 24 for(int i=head[x];i!=-1;i=edge[i].next) 25 { 26 if(!DFN[edge[i].v]) 27 {//如果没访问过 28 tarjan(edge[i].v);//往下进行延伸，开始递归 29 LOW[x]=min(LOW[x],LOW[edge[i].v]);//递归出来，比较谁是谁的儿子／父亲，就是树的对应关系，涉及到强连通分量子树最小根的事情。 30 } 31 else if(visit[edge[i].v]) 32 {//如果访问过，并且还在栈里。 33 LOW[x]=min(LOW[x],DFN[edge[i].v]);//比较谁是谁的儿子／父亲。就是链接对应关系 34 } 35 } 36 if(LOW[x]==DFN[x]) //发现是整个强连通分量子树里的最小根。 37 { 38 do 39 { 40 printf("%d ",stack[index]); 41 visit[stack[index]]=0; 42 index--; 43 }while(x!=stack[index+1]);//出栈，并且输出. 44 printf(" "); 45 } 46 return ; 47 } 48 49 void chushi() 50 { 51 for(int i=1;i<=n;i++) 52 head[i]=-1; 53 } 54 int main() 55 { 56 scanf("%d%d",&n,&m); 57 chushi(); 58 //memset(head,-1,sizeof(head)); 59 for(int i=1;i<=m;i++) 60 { 61 int x,y; 62 scanf("%d%d",&x,&y); 63 add(x,y); 64 } 65 for(int i=1;i<=n;i++) 66 if(!DFN[i]) tarjan(i);//当这个点没有访问过，就从此点开始。防止图没走完 67 return 0; 68 }
SPFA：
主要思想是：
初始时将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时算法结束。
这个算法，简单的说就是队列优化的bellman-ford，利用了每个点不会更新次数太多的特点发明的此算法。
SPFA 在形式上和广度优先搜索非常类似，不同的是广度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是说一个点修改过其它的点之后，过了一段时间可能会获得更短的路径，于是再次用来修改其它的点，这样反复进行下去。
算法时间复杂度：O(kE)，E是边数。K是常数，平均值为2。
算法实现：
dis[i]记录从起点s到i的最短路径，w[i][j]记录连接i，j的边的长度。pre[v]记录前趋。
team[1..n]为队列，头指针head，尾指针tail。
布尔数组exist[1..n]记录一个点是否现在存在在队列中。
初始化：d[s]=0,d[v]=∞（v≠s），memset(exist,false,sizeof(exist));
起点入队team[1]=s; head=0; tail=1;exist[s]=true;
do
{1、头指针向下移一位，取出指向的点u。
2、exist[u]=false;已被取出了队列
3、for与u相连的所有点v //注意不要去枚举所有点，用数组模拟邻接表存储
if (d[v]>d[u]+w[u][v])
{ d[v]=d[u]+w[u][v];
pre[v]=u;
if (!exist[v]) //队列中不存在v点，v入队。
{ //尾指针下移一位，v入队;
exist[v]=true;
}
｝
}
while (head < tail);
循环队列：
采用循环队列能够降低队列大小，队列长度只需开到2*n+5即可。例题中的参考程序使用了循环队列。
1 //spfa 2 3 #include<iostream> 4 #include<cstdio> 5 #include<cstring> 6 using namespace std; 7 const int maxn=0x7f; 8 bool vis[1001]; 9 int map[1001][1001],dis[1001],queue[1001],path[1001]; 10 int n,m,head=0,tail=1,now; 11 12 13 void spfa(int x) 14 { 15 queue[head]=x; 16 vis[x]=true; 17 dis[x]=0; 18 path[x]=x; 19 while(head<tail) 20 { 21 now=queue[head]; 22 for(int i=1;i<=n;i++) 23 { 24 if(dis[i]>dis[now]+map[now][i]) 25 { 26 dis[i]=dis[now]+map[now][i]; 27 path[i]=now; 28 if(vis[i]==false) 29 { 30 queue[tail++]=i; 31 vis[i]=true; 32 } 33 } 34 } 35 vis[now]=false; 36 head++; 37 } 38 } 39 void print(int st,int en) 40 { 41 int q[1001]; 42 int tot=1; 43 q[tot]=en; 44 tot++; 45 int temp=path[en]; 46 while(temp!=st) 47 { 48 q[tot]=temp; 49 tot++; 50 temp=path[temp]; 51 } 52 q[tot]=st; 53 for(int i=tot;i>=1;i--) 54 { 55 if(i!=1) 56 printf("%d -- >",q[i]); 57 else 58 printf("%d",q[i]); 59 } 60 cout<<endl; 61 } 62 int main() 63 { 64 memset(map,maxn,sizeof(map)); 65 scanf("%d%d",&n,&m); 66 int he,ta,len; 67 for(int i=1;i<=m;i++) 68 { 69 cin>>he>>ta>>len; 70 map[he][ta]=map[ta][he]=len; 71 } 72 memset(dis,maxn,sizeof(dis)); 73 memset(vis,false,sizeof(vis)); 74 memset(queue,0,sizeof(queue)); 75 int start,end; 76 scanf("%d%d",&start,&end); 77 spfa(start); 78 printf("%d ",dis[end]); 79 print(start,end); 80 return 0; 81 }
数组模拟邻接表储存：
详见博客：数组模拟
基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。
每一个单链表设一个表头结点。
第i个单链表表示依附于顶点Vi的边(对有向图是以顶点Vi为头或尾的弧)。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int E=5;//E为最大边数 5 const int N=3;//n为最大定点数 6 struct Edge { 7 int u,v,w,next;//两顶点，权值，下一条边； 8 } edge[E]; 9 int head[N];//表头； 10 int num;//内存指针； 11 void chushi() 12 { 13 for(int i=1; i<=N; i++) 14 head[i]=-1; 15 num=0; 16 } 17 void add_edge(int b,int e,int w) 18 { 19 edge[num].u=b; 20 edge[num].v=e; 21 //edge[num].w=w; 22 edge[num].next=head[b]; 23 head[b]=num++; 24 } 25 int main() 26 { 27 int n,m,a,b,x; 28 chushi(); 29 scanf("%d%d",&n,&m); 30 for(int i=1;i<=m;i++) 31 { 32 scanf("%d %d %d",&a,&b/*,&x*/); //a、b之间有一条长度为x的边 33 add_edge(a,b,x); 34 } 35 cout<<1; 36 for(int i=head[1];i!=-1;i=edge[i].next) //遍历从点1开始的所有边 37 { 38 cout<<"-->"<<edge[i].v; 39 } 40 return 0; 41 }
广搜 bfs
1 //bfs 2 3 #include<iostream> 4 #include<cstdio> 5 using namespace std; 6 int queue[1001],top=0,end=1; 7 int map[1001][1001]; 8 int vis[1001]; 9 int n,m; 10 void bfs(int p) 11 { 12 queue[end]=p; 13 vis[p]=1; 14 printf("%c -->",queue[end]+64); 15 while(top!=end) 16 { 17 top++; 18 int k=queue[top]; 19 for(int i=1;i<=n;i++) 20 { 21 22 if(vis[i]==0&&map[k][i]==1) 23 { 24 printf("%c-->",i+64); 25 queue[++end]=i; 26 vis[i]=1; 27 } 28 } 29 } 30 } 31 int main() 32 { 33 char head,tail; 34 scanf("%d%d",&n,&m); 35 for(int i=1;i<=m;i++) 36 { 37 cin>>head>>tail; 38 head=head-64; 39 tail=tail-64; 40 map[head][tail]=map[tail][head]=1; 41 } 42 bfs(1); 43 return 0; 44 }
深搜 dfs
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 char maps[10][11]; 5 bool vis[1000]; 6 int q,m; 7 void dfs(int a){ 8 vis[a]=1; 9 if(a<q) 10 printf("%c --> ",a+64); 11 else printf("%c",a+64); 12 for(int i=1;i<=q;i++) 13 { 14 if(maps[a][i]==1&&vis[i]==0) 15 dfs(i); 16 } 17 } 18 int main() 19 { 20 21 char a,b; 22 cin>>q>>m; 23 for(int i=1;i<=m;i++) 24 { 25 cin>>a>>b; 26 maps[a-64][b-64]=1; 27 maps[b-64][a-64]=1; 28 } 29 dfs(1); 30 }
Floyed:
思路：三层循环松弛中间节点
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int maps[1001][1001]; 6 int ans; 7 int main() 8 { 9 memset(maps,999999,sizeof(maps)); 10 int n,m; 11 cin>>n>>m; 12 int he,ta,len; 13 for(int i=1;i<=m;i++) 14 { 15 cin>>he>>ta>>len; 16 maps[ta][he]=maps[he][ta]=len; 17 } 18 int x,y; 19 cin>>x>>y; 20 for(int k = 1;k <= n;k++) 21 for(int i = 1;i <= n;i++) 22 for(int j = 1;j <= n;j++) 23 { 24 if(maps[i][j]>maps[i][k]+maps[k][j]) 25 maps[i][j]=maps[i][k]+maps[k][j]; 26 } 27 28 printf("%d",maps[x][y]); 29 }
Dijkstra
主要思想：每次找到一个能到达的最近的点，来更新到达其他点的距离
思路：
1.需要一个dis数组记录需要求的点到其他点的最短路径 pre数组记录前驱
2.（1）初始化:dis[]=∞ dis[开始的点]=0 pre[开始的点]=0
（2）<1>for(int i=1;i<=顶点总数;i++)
找到dis[i]最小的点
vis[找到的点]=1
for(与找到的点相连的点)
if(dis[find]+w[find][i]<dis[i])
{
1.松弛
2.pre[i]=find 记录前驱
}
end
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 int n,m; 7 const int maxn=9999999; 8 int map[1001][1001],start,end; 9 bool vis[1001]; 10 int dis[1001],road[1001],minn,k; 11 12 void add(int now) 13 { 14 for(int i=1;i<=n;i++) 15 { 16 dis[i]=map[now][i]; 17 } 18 vis[now]=true; 19 dis[now]=0; 20 for(int i=1;i<=n-1;i++) 21 { 22 minn=maxn; 23 k=now; 24 for(int j=1;j<=n;j++) 25 if(vis[j]==false&&dis[j]<minn) 26 { 27 minn=dis[j]; 28 k=j; 29 } 30 vis[k]=true; 31 for(int g=1;g<=n;g++) 32 if(vis[g]==false&&dis[g]>dis[k]+map[k][g]) 33 { 34 dis[g]=dis[k]+map[k][g]; 35 } 36 } 37 printf("%d",dis[end]); 38 return ; 39 40 } 41 int main() 42 { 43 memset(map,maxn,sizeof(map)); 44 memset(vis,false,sizeof(vis)); 45 scanf("%d%d",&n,&m); 46 int he,ta,len; 47 for(int i=1;i<=m;i++) 48 { 49 scanf("%d%d%d",&he,&ta,&len); 50 map[ta][he]=map[he][ta]=len; 51 } 52 memset(dis,maxn,sizeof(dis)); 53 cin>>start>>end; 54 add(start); 55 return 0; 56 }
Kruskal算法：
主要思想：
Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序（一般使用快排），并认为每一个点都是孤立的，分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。直到选取了n-1条边为止。
思路：
算法描述:
1.初始化并查集。father[x]=x。
2.tot=0
3.将所有边用快排从小到大排序。sort
4.计数器 k=0;
5.for (i=1; i<=M; i++) //循环所有已从小到大排序的边
if 这是一条u,v不属于同一集合的边(u,v)(因为已经排序，所以必为最小)，
begin
①合并u,v所在的集合，相当于把边(u,v)加入最小生成树。
②tot=tot+W(u,v)
③k++
④如果k=n-1,说明最小生成树已经生成，则break;
end;
6. 结束，tot即为最小生成树的总权值之和。
1 #include<cstdio> 2 #include<algorithm> 3 #include<iostream> 4 using namespace std; 5 struct node{ 6 int x; 7 int y; 8 int v; 9 bool operator < (const node &aa)const 10 { 11 if(v<aa.v)return 1; 12 else return 0; 13 } 14 }a[1001]; 15 int father[10001]; 16 int find(int x) 17 { 18 if(father[x]!=x) father[x]=find(father[x]); 19 return father[x]; 20 } 21 void unionn(int x,int y) 22 { 23 if(find(x)!=find(y))father[find(x)]=father[find(y)]; 24 } 25 int num=0; 26 int main() 27 { 28 int n,m=0,x; 29 scanf("%d",&n); 30 for(int i=1;i<=n;i++) 31 for(int j=1;j<=n;j++) 32 { 33 cin>>x; 34 if(x!=0) 35 { 36 m++; 37 a[++num].x=i; 38 a[num].y=j; 39 a[num].v=x; 40 } 41 } 42 int tot=0,k=0; 43 for(int i=1;i<=n;i++) 44 father[i]=i; 45 sort(a+1,a+m+1); 46 for(int i=1;i<=m;i++) 47 { 48 if(find(a[i].x)!=find(a[i].y)) 49 { 50 unionn(a[i].x,a[i].y); 51 tot+=a[i].v; 52 k++; 53 } 54 if(k==n-1)break; 55 } 56 cout<<tot<<endl; 57 return 0; 58 }