链式前向星存储模板
2026-01-31 10:18:53
发布于：四川
0阅读
0回复
0点赞
//链式前向星存储模板
#include<iostream>
#include<queue>
using namespace std;
const int maxn=1e5+5; // 适配N,M≤1e5的规模
int head[maxn],node; // head：链式前向星头数组，node：边计数器
int vis[maxn]; // 标记顶点是否被访问（DFS/BFS共用）
// 边结构体（链式前向星）：pre记录上一条边索引，v记录目标顶点
struct Edge{
int pre,v;
}edge[maxn]; // 存储所有边（大小适配1e5条边）
// 功能：添加有向边（u→v）
void add_edge(int u,int v){
edge[++node].v=v; // 边的目标顶点为v
edge[node].pre=head[u];// 边的前驱指向u之前的第一条边
head[u]=node; // u的第一条边更新为当前边
}
// 功能：深度优先遍历（DFS），从u出发遍历所有可达顶点并输出
void dfs(int u){
cout<<u<<" "; // 访问当前顶点并输出
vis[u]=1; // 标记为已访问
// 遍历u的所有出边，递归访问未标记的邻接顶点
for(register int i=head[u];i;i=edge[i].pre){
int v=edge[i].v;
if(!vis[v]){
dfs(v);
}
}
return ;
}
// 功能：广度优先遍历（BFS），从u出发遍历所有可达顶点并输出
void bfs(int u){
queue<int> q; // 存储待访问顶点的队列
q.push(u); // 起始顶点入队
vis[u]=1; // 标记为已访问
while(!q.empty()){
int cur=q.front();// 取出队首顶点
q.pop();
cout<<cur<<" "; // 访问当前顶点并输出
// 遍历当前顶点的所有出边，未标记的邻接顶点入队
for(register int i=head[cur];i;i=edge[i].pre){
int v=edge[i].v;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
return ;
}
int main(){
int n,m,u,v,start;
cin>>n>>m>>start; // 输入顶点数n、边数m、起始遍历顶点start
// 输入m条有向边，构建链式前向星
for(register int i=1;i<=m;++i){
cin>>u>>v;
add_edge(u,v); // 直接构建正向图（u→v）
}
// 执行DFS遍历并输出结果
cout<<"DFS遍历结果：";
dfs(start);
cout<<endl;
// 重置访问标记数组（为BFS做准备）
for(register int i=1;i<=n;++i){
vis[i]=0;
}
// 执行BFS遍历并输出结果
cout<<"BFS遍历结果：";
bfs(start);
cout<<endl;
return 0;
}
这里空空如也
有帮助，赞一个