无向图的DFS遍历(方法之一)

时间:2022-06-29 06:58:12

如果看不懂辅助解释在后面第点


1、录入方式:

输入 u - v  表示一边的2个端点

2、存储结构

struct edge
{
int from;
int to;
int next;
} e[MAXN]; int head[MAXN]; //head[u]表示 以u为父节点的边链表的头

3、建图方法

void build(int u, int v)
{
e[cnt].from = u;
e[cnt].to = v;
e[cnt].next = head[u];// next = 之前u为父节点的边的编号
head[u] = cnt;//更新head[u]
cnt++;
} cin>>u>>v;
build(u,v);
build(v,u);

4、DFS函数编写

void dfs(int u)
{
int edge = head[u];
for(int i = edge; i != -; i = e[i].next )
{
vis[u] = ;
int v = e[i].to;
if(vis[v] == )
{
dfs(v);
}
}
return ;
}

5、一些解释:

 总体方法是head[u]存放以u(顶点)为from的边的编号,通过head[u]找到一条边,并且这条边是 一系列以u为from的边 组成的链表的头,通过这个头用链表的方式(e[i].next)去遍历所有以u为from的边  。  所以数据类型是这样的 : head[顶点编号] = 边的编号 ;   e[边的编号].next = 边的编号 。