DFS 1 #include<iostream> 2 #include<queue> 3 #include<cstdio> 4 using namespace std; 5 queue<int>q; 6 int map[1001][1001]; 7 int vis[1001]; 8 int n,m; ...
DFS
1 #include<iostream> 2 #include<queue> 3 #include<cstdio> 4 using namespace std; 5 queue<int>q; 6 int map[1001][1001]; 7 int vis[1001]; 8 int n,m; 9 void bfs(int p) 10 { 11 q.push(p); 12 vis[p]=1; 13 printf("%c-->",char(q.front()+64)); 14 while(q.size()!=0) 15 { 16 int k=q.front(); 17 q.pop(); 18 for(int i=1;i<=n;i++) 19 { 20 21 if(vis[i]==0&&map[k][i]==1) 22 { 23 printf("%c-->",char(i+64)); 24 //q.pop(); 25 q.push(i); 26 vis[i]=1; 27 } 28 } 29 } 30 } 31 int main() 32 { 33 34 scanf("%d%d",&n,&m); 35 for(int i=1;i<=m;i++) 36 { 37 char x,y; 38 //scanf("\n%d %d",&x,&y); 39 cin>>x>>y; 40 x=x-64; 41 y=y-64; 42 map[x][y]=map[y][x]=1; 43 } 44 bfs(1); 45 return 0; 46 }DFS
BFS
1 #include<iostream> 2 #include<queue> 3 #include<cstdio> 4 using namespace std; 5 queue<int>q; 6 int map[1001][1001]; 7 int vis[1001]; 8 int n,m; 9 void bfs(int p) 10 { 11 q.push(p); 12 vis[p]=1; 13 printf("%c-->",char(q.front()+64)); 14 while(q.size()!=0) 15 { 16 int k=q.front(); 17 q.pop(); 18 for(int i=1;i<=n;i++) 19 { 20 21 if(vis[i]==0&&map[k][i]==1) 22 { 23 printf("%c-->",char(i+64)); 24 //q.pop(); 25 q.push(i); 26 vis[i]=1; 27 } 28 } 29 } 30 } 31 int main() 32 { 33 34 scanf("%d%d",&n,&m); 35 for(int i=1;i<=m;i++) 36 { 37 char x,y; 38 //scanf("\n%d %d",&x,&y); 39 cin>>x>>y; 40 x=x-64; 41 y=y-64; 42 map[x][y]=map[y][x]=1; 43 } 44 bfs(1); 45 return 0; 46 }BFS
Flyoed
思路：三層迴圈遍歷中間節點
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int a[101][101]; 6 int pass[101][101]; 7 int main() 8 { 9 memset(a,999999,sizeof(a)); 10 int n,m; 11 scanf("%d%d",&n,&m); 12 for(int i=1;i<=m;i++) 13 { 14 int x,y,zhi; 15 scanf("%d%d%d",&x,&y,&zhi); 16 a[x][y]=zhi; 17 a[y][x]=zhi; 18 } 19 for(int k=1;k<=n;k++) 20 { 21 for(int i=1;i<=n;i++) 22 { 23 for(int j=1;j<=n;j++) 24 { 25 if(a[i][j]>a[i][k]+a[k][j]) 26 { 27 a[i][j]=a[i][k]+a[k][j]; 28 pass[i][j]=k; 29 } 30 } 31 } 32 } 33 printf("%d %d\n",a[1][4],a[2][6]); 34 printf("%d %d\n",pass[1][4],pass[2][6]); 35 return 0; 36 }Flyoed
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<cstring> 4 using namespace std; 5 int a[101][101]; 6 int dis[101]; 7 int maxn=0x7f; 8 int vis[1001]; 9 int pass[1001]; 10 void print(int bg,int ed) 11 { 12 int ans[101]; 13 int now=1; 14 ans[now]=ed; 15 now++; 16 // ans[now]=ed; 17 //now++; 18 int tmp=pass[ed]; 19 while(tmp!=bg) 20 { 21 ans[now]=tmp; 22 now++; 23 tmp=pass[tmp]; 24 } 25 ans[now]=bg; 26 for(int i=now;i>=1;i--) 27 { 28 if(i!=1) 29 printf("%d-->",ans[i]); 30 else 31 printf("%d",ans[i]); 32 } 33 } 34 int main() 35 { 36 memset(a,maxn,sizeof(a)); 37 int n,m; 38 int beginn=1; 39 scanf("%d%d",&n,&m); 40 for(int i=1;i<=m;i++) 41 { 42 int x,y,zhi; 43 scanf("%d%d%d",&x,&y,&zhi); 44 a[x][y]=zhi; 45 a[y][x]=zhi; 46 } 47 48 for(int i=1;i<=n;i++) 49 { 50 if(a[beginn][i]!=maxn) 51 { 52 dis[i]=a[beginn][i]; 53 } 54 } 55 dis[beginn]=0; 56 for(int i=1;i<=n;i++) 57 { 58 int minn=maxn; 59 int k=-1; 60 for(int j=1;j<=n;j++) 61 { 62 if(dis[j]<=minn&&vis[j]==0) 63 { 64 minn=dis[j]; 65 k=j; 66 } 67 } 68 vis[k]=1; 69 for(int j=1;j<=n;j++) 70 { 71 if(dis[k]+a[k][j]<=dis[j]) 72 { 73 dis[j]=dis[k]+a[k][j]; 74 pass[j]=k; 75 } 76 } 77 } 78 for(int i=1;i<=n;i++) 79 { 80 cout<<dis[i]<<" "; 81 if(i==1)cout<<i; 82 else 83 print(1,i); 84 cout<<endl; 85 } 86 87 return 0; 88 }Dijkstra
SPFA
主要思想：初始時將起點加入隊列。每次從隊列中取出一個元素，並對所有與它相鄰的點進行修改，若某個相鄰的點修改成功，則將其入隊。直到隊列為空時結束
思路：需要變數：
1.需要一個dis數組記錄需要求的點到其他點的最短路徑
2.pre數組記錄前驅
3.queue隊列
4.vis數組 記錄該點是否在隊列中
begin
1.初始化:dis[]=∞ dis[開始的點]=0 pre[開始的點]=0
2.while(隊列不為空)
（1）取出頂點 vis[頂點]=false
（2）for(與頂點相連的點)
if(dis[find]+w[find][i]<dis[i])
{
1.鬆弛
if(i不在隊列中)
{
加入隊列
vis[i]=true;
}
}
end;
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 int map[101][101]; 7 int dis[101]; 8 bool vis[101]; 9 queue<int>q; 10 int n,m; 11 int bg=1; 12 void spfa() 13 { 14 dis[bg]=0; 15 vis[bg]=1; 16 q.push(bg); 17 dis[bg]=0; 18 do 19 { 20 int k=q.front(); 21 for(int j=1;j<=n;j++) 22 { 23 if(dis[j]>dis[k]+map[k][j]) 24 { 25 dis[j]=dis[k]+map[k][j]; 26 if(vis[j]==0) 27 { 28 q.push(j); 29 vis[j]=1; 30 } 31 } 32 } 33 q.pop(); 34 vis[k]=0; 35 }while(q.size()!=0); 36 for(int i=1;i<=n;i++) 37 cout<<dis[i]<<endl; 38 } 39 int main() 40 { 41 memset(map,0x7f,sizeof(map)); 42 memset(dis,0x7f,sizeof(dis)); 43 memset(vis,0,sizeof(vis)); 44 scanf("%d%d",&n,&m); 45 for(int i=1;i<=m;i++) 46 { 47 int x,y,z; 48 scanf("%d%d%d",&x,&y,&z); 49 map[x][y]=map[y][x]=z; 50 } 51 //int a,b; 52 //scanf("%d%d",&a,&b); 53 spfa(); 54 return 0; 55 }SPFA鄰接矩陣存儲
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 const int MAXN=30001; 7 const int maxn=0x7fffffff; 8 struct node 9 { 10 int u; 11 int v; 12 int w; 13 int next; 14 }edge[MAXN]; 15 int num=1; 16 int head[MAXN]; 17 int n,m,begin,end; 18 int dis[MAXN]; 19 int vis[MAXN]; 20 void spfa() 21 { 22 for(int i=1;i<=n;i++)dis[i]=maxn; 23 queue<int>q; 24 vis[begin]=1; 25 q.push(begin); 26 dis[begin]=0; 27 while(q.size()!=0) 28 { 29 int p=q.front(); 30 q.pop(); 31 vis[p]=0; 32 for(int i=head[p];i!=-1;i=edge[i].next) 33 { 34 if(dis[edge[i].v]>dis[p]+edge[i].w&&dis[p]!=maxn) 35 { 36 dis[edge[i].v]=dis[p]+edge[i].w; 37 if(vis[edge[i].v]==0) 38 { 39 q.push(edge[i].v); 40 vis[edge[i].v]=1; 41 } 42 } 43 } 44 } 45 printf("%d",dis[end]); 46 } 47 int main() 48 { 49 scanf("%d%d%d%d",&n,&m,&begin,&end); 50 for(int i=1;i<=n;i++)head[i]=-1; 51 for(int i=1;i<=m;i++) 52 { 53 scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w); 54 edge[num].next=head[edge[num].u]; 55 head[edge[num].u]=num++; 56 edge[num].w=edge[num-1].w; 57 edge[num].u=edge[num-1].v; 58 edge[num].v=edge[num-1].u; 59 edge[num].next=head[edge[num].u]; 60 head[edge[num].u]=num++; 61 } 62 spfa(); 63 return 0; 64 }SPFA鄰接表存儲
單源最短路徑輸出
主要思想
主要利用遞歸的思想，一層一層的進行迭代
1 void print(int x) 2 { 3 if(pre[a][x]==0)return; 4 print(pre[a][x]); 5 cout<<"->"<<x; 6 } 7 //a為開始的點單源最短路的輸出
Tarjan演算法
思路：
基本思路：
1.初始化
2.入棧
3.枚舉：
1.不在隊列中->訪問，進行賦值，
2.在隊列中->賦值
4.尋找根->輸出結果
1 #include<cstdio> 2 #include<algorithm> 3 #include<string.h> 4 using namespace std; 5 struct node { 6 int v,next; 7 } edge[1001]; 8 int DFN[1001],LOW[1001]; 9 int stack[1001],heads[1001],visit[1001],cnt,tot,index; 10 void add(int x,int y) { 11 edge[++cnt].next=heads[x]; 12 edge[cnt].v = y; 13 heads[x]=cnt; 14 return ; 15 } 16 void tarjan(int x) { //代表第幾個點在處理。遞歸的是點。 17 DFN[x]=LOW[x]=++tot;// 新進點的初始化。 18 stack[++index]=x;//進站 19 visit[x]=1;//表示在棧里 20 for(int i=heads[x]; i!=-1; i=edge[i].next) { 21 if(!DFN[edge[i].v]) { 22 //如果沒訪問過 23 tarjan(edge[i].v);//往下進行延伸，開始遞歸 24 LOW[x]=min(LOW[x],LOW[edge[i].v]);//遞歸出來，比較誰是誰的兒子／父親，就是樹的對應關係，涉及到強連通分量子樹最小根的事情。 25 } else if(visit[edge[i].v ]) { 26 //如果訪問過，並且還在棧里。 27 LOW[x]=min(LOW[x],DFN[edge[i].v]);//比較誰是誰的兒子／父親。就是鏈接對應關係 28 } 29 } 30 if(LOW[x]==DFN[x]) { //發現是整個強連通分量子樹里的最小根。 31 do { 32 printf("%d ",stack[index]); 33 visit[stack[index]]=0; 34 index--; 35 } while(x!=stack[index+1]);//出棧，並且輸出。 36 printf("\n"); 37 } 38 return ; 39 } 40 int main() { 41 memset(heads,-1,sizeof(heads)); 42 int n,m; 43 scanf("%d%d",&n,&m); 44 int x,y; 45 for(int i=1; i<=m; i++) { 46 scanf("%d%d",&x,&
