企业网站建设模块,开通微信公众号需要多少钱,企业小程序开发,南京做南京美容整形网站文章目录 DFS排列数字n皇后 BFS走迷宫 拓扑序列单链表树与图的深度优先搜索模拟队列有向图的拓扑序列 bellman-ford有边数限制的最短路 spfaspfa求最短路spfa判断负环 FloydFloyd求最短路 PrimPrim算法求最小生成树 KruskalKruskal算法求最小生成树 染色法判定二分图染色法判定… 文章目录 DFS排列数字n皇后 BFS走迷宫 拓扑序列单链表树与图的深度优先搜索模拟队列有向图的拓扑序列 bellman-ford有边数限制的最短路 spfaspfa求最短路spfa判断负环 FloydFloyd求最短路 PrimPrim算法求最小生成树 KruskalKruskal算法求最小生成树 染色法判定二分图染色法判定二分图 DFS
排列数字
#includeiostream
using namespace std;
int n ;
int a[10];
bool s[10];
void dfs(int u)
{if(u n){for(int i 0 ; i n ; i) cout a[i] ;cout endl ;return;}for(int i 1; i n ; i){if(!s[i]){a[u] i;s[i] true ;dfs(u1);a[u] 0 ;s[i] false;}}}
int main()
{cin n ;dfs(0);return 0;
}n皇后
#includeiostream
using namespace std;
const int N 20 ;
char g[N][N] ;
bool c[N], x[N] , y[N];
int n , m ;
void dfs(int u)
{if(u n){for(int i 0 ; i n; i) cout g[i] endl;cout endl;return ;}for(int i 0 ; i n ; i){if(!c[i] !x[ui] !y[u-in]){c[i] x[ui] y[u-in] true ;g[u][i] Q;dfs(u1);g[u][i] .;c[i] x[ui] y[u-in] false ;}}
}
int main()
{cin n;for(int i 0 ; i n ; i)for(int j 0 ; j n ; j)g[i][j] . ;dfs(0); return 0 ;
}BFS
走迷宫
#includeiostream
#includecstring
using namespace std;
typedef pairint,int PII ;
const int N 110 ;
PII q[N * N];
int f[N][N] , d[N][N];
int n , m ;
int dx[] {0,1,0,-1} , dy[] {1,0,-1,0} ;
int bfs()
{memset(d , -1 , sizeof d);d[1][1] 0 ;q[0] {1,1};int hh 0 , tt 0 ;while(hh tt){auto t q[hh] ;for(int i 0 ; i 4 ; i){int x t.first dx[i] , y t.second dy[i] ;if(xn x0 ym y0 d[x][y] -1 f[x][y] 0){q[tt] {x,y};d[x][y] d[t.first][t.second] 1 ;}}}return d[n][m];
}
int main()
{cin n m ;for(int i 1 ; i n ; i)for(int j 1 ; j m ; j)cin f[i][j];cout bfs();return 0;
}拓扑序列
单链表
点击跳转至例题 idx存的是指针
树与图的深度优先搜索
树的重心 每个节点都是一个单链表
模拟队列
hh 0 , tt -1
有向图的拓扑序列 都是从前指向后,即有向无环图不能有环 所有入度为0的点都能排在前面的位置 删掉t-j的边仅仅是j的入度减一当j的入度为0的时候放入队列
#includeiostream
#includecstring
using namespace std;
const int N 1e5 10;
int n , m ;
int e[N] , h[N] , ne[N] , idx;
int d[N] , q[N];
void add(int a , int b)
{e[idx] b , ne[idx] h[a] , h[a] idx;
}
bool topool()
{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 ne[i]){int j e[i]; d[j] -- ;if(d[j] 0) q[tt] j ;}}return tt n - 1;
}
int main()
{cin n m ;memset(h , -1 , sizeof h) ;for(int i 0 ; i m ; i){int x,y;cin x y;add(x,y);d[y];}if(topool()){for(int i 0 ; i n ; i) cout q[i] ;}else cout -1 ;return 0;
}bellman-ford
有边数限制的最短路
spfa
spfa求最短路
spfa判断负环
Floyd
Floyd求最短路
Prim
Prim算法求最小生成树
Kruskal
Kruskal算法求最小生成树
染色法判定二分图
染色法判定二分图
