算法：深度优先算法和广度优先算法(基于邻接矩阵) 1.写在前面
图的存储结构有两种：一种是基于二维数组的邻接矩阵表示法。
另一种是基于链表的的邻接表。
在邻接矩阵中，可以如下表示顶点和边连接关系：
说明：
将顶点对应为下标，根据横纵坐标将矩阵中的某一位置值设为1，表示两个顶点向联接。
图示表示的是无向图的邻接矩阵，从中我们可以发现它们的分布关于斜对角线对称。
我们在下面将要讨论的是下图的两种遍历方法（基于矩阵的）：
我们已经说明了我们要用到的是邻接矩阵表示法，那么我首先要来构造图：
矩阵图的数据结构如下表示：
#define MaxVnum 50 typedef double AdjMatrix[MaxVnum][MaxVnum]; //表示一个矩阵，用来存储顶点和边连接关系 typedef struct { int vexnum,arcnum; //顶点的个数，边的个数 AdjMatrix arcs; //图的邻接矩阵 }Graph;
这样我们可以首先来创建上述图，为了方便，我们直接在代码中书写矩阵，而不用每次调试手动输入了
void CreateGraph(Graph &G) { G.vexnum=8; G.arcnum=9; G.arcs[0][1]=1; G.arcs[0][2]=1; G.arcs[1][3]=1; G.arcs[1][4]=1; G.arcs[2][5]=1; G.arcs[2][6]=1; G.arcs[3][1]=1; G.arcs[3][7]=1; G.arcs[3][6]=1; G.arcs[4][1]=1; G.arcs[4][7]=1; G.arcs[5][2]=1; G.arcs[5][6]=1; G.arcs[5][5]=1; G.arcs[6][2]=1; G.arcs[6][5]=1; G.arcs[7][3]=1; G.arcs[7][4]=1; }
这样我们就已经完成了准备工作，我们可以正式来学习我们的两种遍历方式了。
2.深度优先遍历算法 分析深度优先遍历从图的某个顶点出发，访问图中的所有顶点，且使每个顶点仅被访问一次。这一过程叫做图的遍历。
深度优先搜索的思想：
①访问顶点v；
②依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
③若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
比如：
在这里为了区分已经访问过的节点和没有访问过的节点，我们引入一个一维数组bool visited[MaxVnum]用来表示与下标对应的顶点是否被访问过，
流程：
☐ 首先输出 V1，标记V1的flag=true;
☐ 获得V1的邻接边 [V2 V3],取出V2，标记V2的flag=true;
☐ 获得V2的邻接边[V1 V4 V5],过滤掉已经flag的，取出V4，标记V4的flag=true;
☐ 获得V4的邻接边[V2 V8],过滤掉已经flag的，取出V8，标记V8的flag=true;
☐ 获得V8的邻接边[V4 V5],过滤掉已经flag的，取出V5，标记V5的flag=true;
☐ 此时发现V5的所有邻接边都已经被flag了，所以需要回溯。（左边黑色虚线，回溯到V1，回溯就是下层递归结束往回返）
☐
☐ 回溯到V1，在前面取出的是V2，现在取出V3，标记V3的flag=true;
☐ 获得V3的邻接边[V1 V6 V7]，过滤掉已经flag的,取出V6，标记V6的flag=true;
☐ 获得V6的邻接边[V3 V7],过滤掉已经flag的,取出V7，标记V7的flag=true;
☐ 此时发现V7的所有邻接边都已经被flag了，所以需要回溯。（右边黑色虚线，回溯到V1，回溯就是下层递归结束往回返） 深度优先搜索的代码