C++详细讲解图的遍历_C/C++

图的遍历

要想遍历图，肯定要先储存图啊。

下面我们采用邻接表来存图

也可以看：点这里

1.用 h 数组保存各个节点能到的第一个节点的编号。开始时，h[i] 全部为 -1。

2.用 e 数组保存节点编号，ne 数组保存 e 数组对应位置的下一个节点所在的索引。

3.用 idx 保存下一个 e 数组中，可以放入节点位置的索引

4.插入边使用的头插法，例如插入：a->b。首先把b节点存入e数组，e[idx] = b。然后 b 节点的后继是h[a]，ne[idx] = h[a]。最后，a 的后继更新为 b 节点的编号，h[a] = idx，索引指向下一个可以存储节点的位置，idx ++ 。

模板如下：

				?

									//邻接表

									const int N = 100010, M = N * 2;

									//无向图n条边时，最多2n个idx，因为每条边在邻接表中会出现两次

									int h[N], e[M], ne[M], idx;

									//n个链表头，e每一个结点的值，ne每一个结点的next指针

									void add(int a, int b)//a->b

									{//e记录当前点的值(地址->值),ne下一点的地址(地址->地址)，h记录指向的第一个点的地址(值->地址)

									    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;

									}//头插法

									// 初始化

									idx = 0;

									memset(h, -1, sizeof h);

图的深度优先遍历（DFS, depth first search）

方法：深度优先搜索的遍历顺序为一条路径走到底然后回溯再走下一条路径这种遍历方法很省内存但是不能一次性给出最短路径或者最优解。

深度优先遍历的步骤

访问顶点V
依次从顶点V的未被访问的邻节点出发，进行深度优先搜索，直至和V有路径相通的顶点都被访问到。
对于连通图进行遍历时，从一个顶点出发即可访问图中所有的顶点。
对于非连通图进行遍历时，若图中尚有顶点未被访问，则另选一未曾访问的顶点作为起始点，进行深度优先搜索，直至所有顶点都被访问

				?

									// 需要标记数组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, breadth first search）

方法：从图的某一结点出发，首先依次访问该结点的所有邻接顶点（再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶点均被访问为止。

从顶点V出发广度优先搜索的步骤

访问顶点V
依次访问顶点V的各个未被访问的临接点（横向访问）
从V的这些邻接点出发依次访问他们的邻接点，致使“先被访问的顶点的邻接点先于"后访问的顶点的邻接点"被访问(一般可以借助队列实现），直至图中所有已被访问的顶点的邻接点均被访问。
对于非连通图进行遍历时，若图中尚有顶点未被访问，则另选一未曾访问的顶点作为起始点，进行广度优先搜索，直至所有顶点都被访问

模板及注释

				?

									queue<int> q;//借助队列实现

									st[1] = true; // 表示1号点已经被遍历过

									q.push(1);//1号节点入队列

									while (q.size())//对列非空，就一直往后搜索

									{

									    int t = q.front();//队头出队，找该点能到的点

									    q.pop();//遍历完就出队列

									    for (int i = h[t]; i != -1; i = ne[i])//遍历所有t节点能到的点，i为节点索引

									    {

									        int j = e[i];//通过索引i得到t能到的节点编号

									        if (!st[j])//如果没有遍历过

									        {

									            st[j] = true; // 表示点j已经被遍历过

									            q.push(j);//节点入队

									        }

									    }

									}