本文共 3256 字，大约阅读时间需要 10 分钟。
图的存储
邻接矩阵
一个简单粗暴的二维数组。一般只会在Floyd算法有用到，适合稠密图。
G[u][v]=1; //表示u->v有一条长为1的边
链式前向星
最常用到的存图方式，用静态链表前插元素的方式存储图。在Dijkstra算法与SPFA中我都用这种方式，适合稀疏图。
邻接表
emmm…大概是链表数组，第一维描述点，第二维记录点所对应的边。操作比较麻烦，还要动态开点。适合稀疏图。
SEARCH
DFS和BFS。
降级八皇后问题。
#include using namespace std;char map[10][10];int co[10],ans,k,n;void dfs(int row,int c){ if(c==k){ ans++; return ; } if(row>=n)return ; for(int j=row;j >n>>k&&k!=-1){ for(int i=0;i >map[i][j]; ans=0; dfs(0,0);//第0行，放了0个棋 cout< <
网格内的最短路问题BFS最适合不过了。（代码有点丑）
#include #include #include using namespace std;struct ooo{ int x,y;}d[4];int map[10][10],la[100];int main(){ d[0].x=1,d[0].y=0; d[1].x=-1,d[1].y=0; d[2].x=0,d[2].y=1; d[3].x=0,d[3].y=-1; for(int i=0;i<5;i++) for(int j=0;j<5;j++) cin>>map[i][j]; queue Q; int now; Q.push(44);// push 00 while(!Q.empty()) { now=Q.front(); Q.pop(); for(int i=0;i<4;i++) if(now/10+d[i].x>=0&&now/10+d[i].x<5&&now%10+d[i].y>=0&&now%10+d[i].y<5&&map[now/10+d[i].x][now%10+d[i].y]==0) { Q.push(now+d[i].x*10+d[i].y); la[now+d[i].x*10+d[i].y]=now; map[now/10+d[i].x][now%10+d[i].y]=2; if(now+d[i].x*10+d[i].y==00)break; } } now=0; while(1) { printf("(%d, %d)\n",now/10,now%10); if(now==44)break; now=la[now]; }}
最短路
4个算法。Dijkstra算法，Floyd算法，SPFA算法，Bellman-Ford算法。
Dijkstra算法
贪心。无负权边时，任何边无法松弛当前离s点最短距离的点v。所以用v松弛一波相邻的点就踢出图。循环n-1次全部踢出，完成。
#include #include #include using namespace std;struct ooo{ int v,len,next;}e[20001];int d[2001],head[2001],vis[2001],cnt=0;void in(int x,int y,int le){ e[cnt].next=head[x]; e[cnt].v=y; e[cnt].len=le; head[x]=cnt++;}int main(){ int n,m,s,t; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); memset(d,63,sizeof(d)); scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=0;i d[cur]+e[i].len) { d[e[i].v]=d[cur]+e[i].len; } int minn=2e8; for(int i=1;i<=n;i++) if(vis[i]==0&&d[i]
Floyd算法
DP。非常暴力地用每一个点去松弛一遍所有的最短路。
#include #include #include using namespace std;int d[101][101];int main(){ int n,m; scanf("%d%d",&n,&m); memset(d,63,sizeof(d)); int tx,ty,tlen; for(int i=0;i
SPFA算法
从s相邻的点开始松弛，松弛过的点有可能影响到它相邻的点，所以再去松弛他周围的点，直到没法松弛了，自然就OK了。
#include #include #include #include using namespace std;struct ooo{ int v,len,next;}e[2000001];int head[100001],d[100001],cnt=0,vis[100001];void add(int x,int y,int lenn){ e[cnt].next=head[x]; e[cnt].v=y; e[cnt].len=lenn; head[x]=cnt++;}int main(){ int n,m,s,t; memset(head,-1,sizeof(head)); memset(d,127,sizeof(d)); memset(vis,0,sizeof(vis)); scanf("%d%d%d%d",&n,&m,&s,&t); int tx,ty,tlen; for(int i=1;i<=m;i++) { scanf("%d%d%d",&tx,&ty,&tlen); add(tx,ty,tlen); add(ty,tx,tlen); } queue Q; Q.push(s); d[s]=0; while(!Q.empty()) { int cur=Q.front(); Q.pop(); vis[cur]=0; for(int i=head[cur];i!=-1;i=e[i].next) if(d[e[i].v]>d[cur]+e[i].len) { d[e[i].v]=d[cur]+e[i].len; if(!vis[e[i].v]) { Q.push(e[i].v); vis[e[i].v]=1; } } } printf("%d",d[t]);}
Bellman-Ford算法
原始版本的SPFA算法
转载地址：http://pwuzi.baihongyu.com/