包括DFS,BFS,树与图的深度优先遍历,树与图的广度优先遍历,拓扑排序,Dijkstra,bellman-ford,spfa,Floyd,Prim,Kruskal,染色法判定二分图,匈牙利算法等内容。
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int N=105;
int map[N][N],ed[N][N],d[N][N];
int n,m;
int bfs(){
//初始化
memset(d,-1,sizeof d);
queue<pair<int,int>> q;
d[0][0]=0;
q.push({0,0});
ed[0][0]= 1;
//移动方向
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
//bfs遍历
while(q.size()){
auto t=q.front();
q.pop();
for(int i=0;i<4;i++){
int x=t.first+dx[i],y=t.second+dy[i];
if(x>=0&& x<n&& y>=0&& y<m && map[x][y]==0 && ed[x][y] ==0){
d[x][y] = d[t.first][t.second] +1;
q.push({x,y});
ed[x][y]=1;
}
}
}
return d[n-1][m-1];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&map[i][j]);
cout<<bfs();
}
#include<iostream>
#include<queue>
#include<unordered_map>
#include<string>
using namespace std;
int bfs(string start){
queue<string> q;
unordered_map<string,int> d;
//初始化
q.push(start);
d[start]=0;
//标记终点
string end ="12345678x";
while(q.size()){//bfs遍历
auto t=q.front();
q.pop();
//判断是否到达终点
if(t==end)return d[t];
//移动方向
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int k=t.find('x');
int x=k/3,y=k%3;
int distant =d[t];
for(int i=0;i<4;i++){
int a=x+dx[i],b=y+dy[i];
if (a >= 0 && a < 3 && b >= 0 && b < 3){
swap(t[k],t[a*3+b]);
if(!d[t]){
q.push(t);
d[t]=distant+1;
}
swap(t[k],t[a*3+b]);
}
}
}
return -1;
}
int main(){
string start;//存入
for(int i=0;i<9;i++){
char c;cin>>c;
start+=c;
}
cout<<bfs(start)<<'\n';
}
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+9;
int e[N],nex[N],h[N],idx;
int n,m;
int q[N],d[N];
void add(int a,int b){
e[idx]=b;
nex[idx]=h[a];
h[a]=idx++;
}
bool topsort(){
int hh=0,tt=-1;
for(int i=1;i<=n;i++){
if(!d[i])
q[++tt]=i;
}
while(hh<=tt){
int t=q[hh++];
for(int i=h[t];i!=-1;i=nex[i]){
int j=e[i];
if(--d[j]==0)q[++tt]=j;
}
}
return n-1==tt;
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
for(int i=0;i<m;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
d[b]++;
}
if(!topsort())
puts("-1");
else {
for(int i=0;i<n;i++)printf("%d ",q[i]);
}
}