链式前向星建图dfs
时间: 2025-04-26 09:11:06 浏览: 22
### 链式前向星简介
链式前向星是一种高效的存储稀疏矩阵的方法,在图论中常用于表示边表。其核心思想是通过数组模拟邻接表结构,能够快速实现图的构建与查询操作[^1]。
### 图的构建过程
为了使用链式前向星构建图,需要定义两个辅助数组`head[]`和`edge[]`以及指针变量`tot`来记录当前已有的边数:
- `head[i]`: 记录节点i的第一条出边在`edge[]`中的位置
- `edge[tot].to`: 当前边指向的目标节点编号
- `edge[tot].next`: 下一条从同一源点出发的边的位置索引
以下是具体的建图代码示例:
```cpp
struct Edge {
int to; // 边所指向的顶点
int next; // 同一始发点下一条边的位置
};
const int MAXN = 1e5 + 7;
Edge edge[MAXN]; // 存储所有的边
int head[MAXN], tot;
void add_edge(int u, int v) {
edge[++tot].to = v; // 新增一条u->v的有向边
edge[tot].next = head[u]; // 将新加入的边连接到原首边上
head[u] = tot; // 更新该起点最新的第一条边序号
}
```
### DFS遍历算法
基于上述建立好的链式前向星数据结构,可以方便地执行深度优先搜索(DFS),从而访问整个连通分量内的所有结点。下面给出完整的DFS函数实现方式:
```cpp
bool vis[MAXN];
void dfs(int node){
cout << "Visit Node:" << node << endl;
vis[node]=true;
for (int i=head[node]; i!=-1 ; i=edge[i].next){
int nxt = edge[i].to;
if (!vis[nxt]){
dfs(nxt);
}
}
}
// 初始化时需设置头指针为-1,表示无任何相连边
memset(head,-1,sizeof(head));
```
此段程序会按照递归的方式依次探索每一个未被标记过的相邻节点,并打印出经过路径上的各个顶点信息[^2]。
阅读全文
相关推荐


















