图论相关
1、dfs 深度优先搜索 (邻接表存储)
递归 开一个bool数组记录哪些节点遍历过了
void dfs(int u){ //u:从这个结点开始遍历
s[u]=true; //表示遍历过了
for(int i=h[u];i!=-1;i=ne[i]){//遍历相邻的节点
int j=e[i]; //j:指向u
if(!s[j]){ //如果u没有被遍历过
cout<<e[i]<<endl; //visit(u)
dfs(j); //从
}
}
return;
}
2.bfs 宽度优先搜索 (树的层次遍历) (邻接表存储)
不需要开bool数组 但是 要开一个队列
void bfs(int u){
queue<int> q; //initqueue() 开一个队列
q.push(u); //把第一个要输出的节点 放入队列
while(q.size()){
int t=q.front(); //取队头
q.pop(); //弹出队列
for(int i=h[t];i!=-1;i=ne[i]){ //遍历节点
int j=e[i];
cout<<j; //visit(节点)
q.push(j); //放入队列
}
}
return;
}
3.拓扑序列 判断一个图里有没有环
(邻接表存储)
bool topsort(){
//使用堆栈和队列都可以
stack s[MAX_IDX];
int top=-1;
int m;
for(int i=1;i<=n;i++){ //遍历所有点的入度
if(d[i]==0){ //如果入度为0
s[++t]=i; //入栈
}
}
while(top!=-1){ //当栈不为空时
int t=s[top--]; //弹出栈顶元素
m++; //记录有多少元素 出栈
for(int i=h[t];i!=-1;i=ne[i]){ //把弹出栈 的 元素的出边 全部 减1
int j=e[i];
if(--d[j]==0){ //如果有元素的入边为0
s[++top]=j; //入栈
}
}
return m==MAX_IDX; //判断一下弹出元素的数量和图中元素的数量
}
单源最短路 一个节点到其他节点的距离
4.Dijkstra (邻接矩阵存储) Dijkstra算法适用于不存在负权边的图
从一个顶点 到其他顶点的最短距离
bool st[N];
int dist[N];
void Dijkstra(){
dist[1]=0; //第一个节点的距离为0
for(int i=0;i<n;i++){ //有n个点 找n次最小距离
int t=-1; //t代表我们要在图中寻找的到达其他点最小权重的点 初始化为-1
//j代表所有的点
for(int j=1;j<=n;j++){
//如果j没有被遍历
//t==-1 让t先等于一个图中没有被遍历过的点
//dist[t]>dist[j] 找图中到达其他点距离最小的点
if(!st[j]&&(t==-1||dist[t]>dist[j])){
t=j; //更新t
}
}
st[t]=true;//标记t已确定最小权重
//利用t来更新其他点的权重
for(int j=1;i<=n;j++){
dist[j]=min(dist[j],g[t][j]+dist[t]);
}
}
if(dist[n]==0x3f)return -1;
else cout<<dist[n];
}
5.多源最短路
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}