数组模拟邻接表

//1.初始定义
const int N=1e5+10;
const int M=2*N;
int h[N],e[M],ne[M],idx;
//N表示预定义图中点的个数，M预定义边的条数
//h[N]存储邻接表的表头节点,相当于存储idx
//e[N]存储了节点信息
//ne[N]表示节点指向的下一个节点下标

//2.邻接表的初始化
memset(h,-1,sizeof h);
//表头初始化为-1表示没有指向

//3.向邻接表中添加元素
void add(int a,int b)//存入由a指向b的点
{
//其实相当于从靠近主链的一侧插入
e[idx]=b;//创建新点
ne[idx]=h[a];//新点的next指针指向h[a]
h[a]=idx++;//让h[a]指向新点 完成替换插入的操作
}
//如果要添加无向图，要执行两次，即add(a,b);add(b,a);

//4.DFS遍历
bool st[N];//记录该点是否被搜索
void dfs(int u)
{
st[u]=true;//标记该点已被搜索
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j]) dfs(j);//只有没有被搜索过的点才能继续搜索
}
}

//BFS遍历
void bfs()
{
while(q.size())
{
auto t=q.front();
q.pop();
//’‘’‘对t进行的操作
}
}