图的邻接表存储及图的遍历（DFS）

图的表示方式

• 邻接矩阵：G[N][N]，适合稠密图，占用空间大，O(N*N)。
• 邻接表：存储稀疏有向图，避免空间浪费
• 十字链表 ：针对有向图，把邻接表和逆邻接表整合在一起，这样既容易找到以node为尾的弧，也能找到node为头的弧
• 邻接多重表：针对无向图优化的存储结构

数组模拟邻接表存储图 及图的遍历

变量

	const int N=1E5+5,M=2*N;
	int h[N],e[M],ne[M],idx;
	bool st[N]; // 标记是否遍历过
	//初始化
	// 初始化邻接表和标记数组
    memset(h, -1, sizeof h);
    memset(st, false, sizeof st);

• 变量解释

e[idx]：编号为idx的边，值为边指向的顶点，例如边（a->b). e[idx]=b;
ne[idx]：编号为idx的边的下一个边
h[idx]：a这个点所连接的第一个点的编号
idx：当前存储到的边的编号

• 邻接表添加有向边（a->b)：

void add(int a,int b){
	//存入a指向b的点
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}

• 举例说明：

图的遍历

• 图的深度优先搜寻DFS

#include <bits/stdc++.h>
using namespace std;

// 全局变量
const int N = 1e5 + 10;
const int M = 2 * N;
int e[N], h[N], ne[N], idx=0; // 邻接表存图
bool st[N]; // 标记是否遍历过

// 添加一条边a->b
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u){
    if(st[u]) return;
    st[u]=true;		//标记已经被搜过
    cout<<u<<endl;
    for(int i=h[u];~i;i=ne[i]){//注释：～表示按位取反，-1取反=0，即：i！=-1
        int j=e[i];
        if(!st[j]) {
            dfs(j);	//只有没被搜过的才能继续搜索下去
        }
    }
}


int main() {
    // 初始化邻接表和标记数组
    memset(h, -1, sizeof h);
    memset(st, false, sizeof st);

    // 读入图的信息
   add(1 , 3);
   add(1,2);
   add(2,4);
   add (3,5);

    // 从任意一个未被遍历的节点开始 DFS 遍历
    for (int i = 1; i <= 5; i ++ )
        if (!st[i]) dfs(i);

    return 0;
}