深度优先遍历/深度优化搜索DFS

右手原则：在没有碰到重复顶点的1情况下，分叉路口始终是向右手边走，没路过一个顶点就做一个记号

主要思路是右手原则，把自己想象成从一个顶点出发的小人,每次选择下一步要走的路径时，就选择右手方向的路径，并给自己即将离开的顶点做一个已经遍历过的标记，直到碰到右手选择的路径将要到达的顶点是已经遍历过的顶点，这时则判断从右手方向开始的路径的终点顶点是否已遍历，若没有遍历，则选择该路径继续往下，若碰到所有路径终点顶点都是已经遍历过的，则沿到达该顶点的路径返回上一个顶点，检查上一顶点的其他路径顶点是否已经遍历，未遍历的话，则沿该路径走下去，即碰到所有路径顶点都遍历过则返回上一顶点，以此类推，直到返回起点顶点

整个图的遍历过程算法上是一个递归的过程，遍历方式上类似于树的前序遍历

看蓝色的路径即顶点遍历过程
A->B->C->D->E->F->G->H (往回走，看红色路径顶点都已遍历过)->G->F->E->D->I->D->C->B->A

编程思路：
遍历图的邻接矩阵，邻接矩阵建立时注意选择是使用右手原则还是左手原则，从起点开始遍历该顶点所在行，便利到非0值且对应的列顶点未访问过就开始遍历该列顶点对应顶点所在的行，同样遍历非0未遍历过的顶点，如果该行所有顶点都遍历过则返回上一顶点继续重复遍历找未遍历的顶点，直到返回起点位置
代码链接

马踏棋盘问题

国际象棋的棋盘为8*8的方格棋盘，现将“马”放在任意指定的方格中，按照“马”走棋的规则将“马”进行移动
要求每个方格只能进入一次，最终使得“马”走遍棋盘64个方格

一个位置最多有八种选择，如下

代码链接

图的广度优先遍历

主要思路：树的层序遍历
结构：队列
原则：右手原则
将复杂的图调整结构为层的形状，从最上一层结点唯一结点出发，入队列
遍历第二层，从与上一层结点相连的右手边的结点开始遍历，先将上一层相连的结点出队列，然后第二层结点入队列
以此类推，即在本层遍历时，先将与将要遍历的结点的上层结点出队列，然后将本层结点入队列，
遍历完一个上层结点的本层连接点，先将上层下一个结点出队列，在将上层下一个节点的本层链接点入队列
出队列顺序即遍历顺序

选定一个起点结点(A)，依次遍历与该结点相连结点(B、F)，每个结点遍历完后添加遍历标记，
再依次遍历刚刚遍历过的结点(先B后F)的相连结点(CIG、E),同样遍历完要加标记
以此类推，再遍历C的连接点D，G的连接点H

编程思路：
将每次遍历的结点入队列，每遍历完一层，出一次队列，出队列顺序即遍历顺序
代码链接