如果看不懂辅助解释在后面第点
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 = 边的编号 。