深度优先算法和广度优先算法(基于邻接矩阵)

1.写在前面

　　图的存储结构有两种&＃xff1a;一种是基于二维数组的邻接矩阵表示法。

　　　　　　　　　　　　另一种是基于链表的的邻接表。

　　在邻接矩阵中&＃xff0c;可以如下表示顶点和边连接关系&＃xff1a;

说明&＃xff1a;

　　将顶点对应为下标&＃xff0c;根据横纵坐标将矩阵中的某一位置值设为1&＃xff0c;表示两个顶点向联接。

　　图示表示的是无向图的邻接矩阵&＃xff0c;从中我们可以发现它们的分布关于斜对角线对称。

　　我们在下面将要讨论的是下图的两种遍历方法&＃xff08;基于矩阵的&＃xff09;&＃xff1a;

　　我们已经说明了我们要用到的是邻接矩阵表示法&＃xff0c;那么我首先要来构造图&＃xff1a;

　　矩阵图的数据结构如下表示&＃xff1a;

#define MaxVnum 50
typedef double AdjMatrix[MaxVnum][MaxVnum]; //表示一个矩阵&＃xff0c;用来存储顶点和边连接关系
typedef struct {int vexnum,arcnum;　　　　　　　　　　　　　　 //顶点的个数&＃xff0c;边的个数AdjMatrix arcs;　　　　　　　　　　　　　　　　 //图的邻接矩阵
}Graph;

　　这样我们可以首先来创建上述图&＃xff0c;为了方便&＃xff0c;我们直接在代码中书写矩阵&＃xff0c;而不用每次调试手动输入了

void CreateGraph(Graph &G)
{G.vexnum&＃61;8;G.arcnum&＃61;9;G.arcs[0][1]&＃61;1;G.arcs[0][2]&＃61;1;G.arcs[1][3]&＃61;1;G.arcs[1][4]&＃61;1;G.arcs[2][5]&＃61;1;G.arcs[2][6]&＃61;1;G.arcs[3][1]&＃61;1;G.arcs[3][7]&＃61;1;G.arcs[3][6]&＃61;1;G.arcs[4][1]&＃61;1;G.arcs[4][7]&＃61;1;G.arcs[5][2]&＃61;1;G.arcs[5][6]&＃61;1;G.arcs[5][5]&＃61;1;G.arcs[6][2]&＃61;1;G.arcs[6][5]&＃61;1;G.arcs[7][3]&＃61;1;G.arcs[7][4]&＃61;1;
}

　　这样我们就已经完成了准备工作&＃xff0c;我们可以正式来学习我们的两种遍历方式了。

2.深度优先遍历算法

　　分析深度优先遍历

　　　　从图的某个顶点出发&＃xff0c;访问图中的所有顶点&＃xff0c;且使每个顶点仅被访问一次。这一过程叫做图的遍历。

　　　　深度优先搜索的思想&＃xff1a;

　　　　　　①访问顶点v&＃xff1b;
　　　　　　②依次从v的未被访问的邻接点出发&＃xff0c;对图进行深度优先遍历&＃xff1b;直至图中和v有路径相通的顶点都被访问&＃xff1b;
　　　　　　③若此时图中尚有顶点未被访问&＃xff0c;则从一个未被访问的顶点出发&＃xff0c;重新进行深度优先遍历&＃xff0c;直到图中所有顶点均被访问过为止。

　　　　比如&＃xff1a;

　　　　在这里为了区分已经访问过的节点和没有访问过的节点&＃xff0c;我们引入一个一维数组boolvisited[MaxVnum]用来表示与下标对应的顶点是否被访问过&＃xff0c;

流程&＃xff1a;
☐ 首先输出 V1&＃xff0c;标记V1的flag&＃61;true;
☐ 获得V1的邻接边 [V2 V3],取出V2&＃xff0c;标记V2的flag&＃61;true;
☐ 获得V2的邻接边[V1 V4 V5],过滤掉已经flag的&＃xff0c;取出V4&＃xff0c;标记V4的flag&＃61;true;
☐ 获得V4的邻接边[V2 V8],过滤掉已经flag的&＃xff0c;取出V8&＃xff0c;标记V8的flag&＃61;true;
☐ 获得V8的邻接边[V4 V5],过滤掉已经flag的&＃xff0c;取出V5&＃xff0c;标记V5的flag&＃61;true;
☐ 此时发现V5的所有邻接边都已经被flag了&＃xff0c;所以需要回溯。&＃xff08;左边黑色虚线&＃xff0c;回溯到V1&＃xff0c;回溯就是下层递归结束往回返&＃xff09;
☐ 
☐ 回溯到V1&＃xff0c;在前面取出的是V2&＃xff0c;现在取出V3&＃xff0c;标记V3的flag&＃61;true;
☐ 获得V3的邻接边[V1 V6 V7]&＃xff0c;过滤掉已经flag的,取出V6&＃xff0c;标记V6的flag&＃61;true;
☐ 获得V6的邻接边[V3 V7],过滤掉已经flag的,取出V7&＃xff0c;标记V7的flag&＃61;true;
☐ 此时发现V7的所有邻接边都已经被flag了&＃xff0c;所以需要回溯。&＃xff08;右边黑色虚线&＃xff0c;回溯到V1&＃xff0c;回溯就是下层递归结束往回返&＃xff09;

　　深度优先搜索的代码

bool visited[MaxVnum];
void DFS(Graph G,int v)
{visited[v]&＃61; true; //从V开始访问&＃xff0c;flag它printf("%d",v); //打印出Vfor(int j&＃61;0;j}void DFSTraverse(Graph G) {for (int v &＃61; 0; v }

 3.广度优先搜索算法

　　　　分析广度优先遍历　　　　

　　　　　　所谓广度&＃xff0c;就是一层一层的&＃xff0c;向下遍历&＃xff0c;层层堵截&＃xff0c;还是这幅图&＃xff0c;我们如果要是广度优先遍历的话&＃xff0c;我们的结果是V1 V2 V3 V4 V5 V6 V7 V8。

　　　　　　广度优先搜索的思想&＃xff1a;

　　　　　　 　　① 访问顶点vi &＃xff1b;

　　　　　　　　 ② 访问vi 的所有未被访问的邻接点w1 ,w2 , …wk &＃xff1b;

　　　　　　　　 ③ 依次从这些邻接点&＃xff08;在步骤②中访问的顶点&＃xff09;出发&＃xff0c;访问它们的所有未被访问的邻接点; 依此类推&＃xff0c;直到图中所有访问过的顶点的邻接点都被访问&＃xff1b;

　　　说明&＃xff1a;

　　　　　　为实现③&＃xff0c;需要保存在步骤②中访问的顶点&＃xff0c;而且访问这些顶点的邻接点的顺序为&＃xff1a;先保存的顶点&＃xff0c;其邻接点先被访问。 这里我们就想到了用标准模板库中的queue队列来实现这种先进现出的服务。

　　　　　　老规矩我们还是走一边流程&＃xff1a;

　　　说明&＃xff1a;　

　　　　 ☐将V1加入队列&＃xff0c;取出V1&＃xff0c;并标记为true(即已经访问)&＃xff0c;将其邻接点加进入队列&＃xff0c;则 <—[V2 V3]　

　　　　 ☐取出V2&＃xff0c;并标记为true(即已经访问)&＃xff0c;将其未访问过的邻接点加进入队列&＃xff0c;则 <—[V3 V4 V5]

☐取出V3&＃xff0c;并标记为true(即已经访问)&＃xff0c;将其未访问过的邻接点加进入队列&＃xff0c;则 <—[V4 V5 V6 V7]

☐取出V4&＃xff0c;并标记为true(即已经访问)&＃xff0c;将其未访问过的邻接点加进入队列&＃xff0c;则 <—[V5 V6 V7 V8]

☐取出V5&＃xff0c;并标记为true(即已经访问)&＃xff0c;因为其邻接点已经加入队列&＃xff0c;则 <—[V6 V7 V8]

☐取出V6&＃xff0c;并标记为true(即已经访问)&＃xff0c;将其未访问过的邻接点加进入队列&＃xff0c;则 <—[V7 V8]

☐取出V7&＃xff0c;并标记为true(即已经访问)&＃xff0c;将其未访问过的邻接点加进入队列&＃xff0c;则 <—[V8]

☐取出V8&＃xff0c;并标记为true(即已经访问)&＃xff0c;将其未访问过的邻接点加进入队列&＃xff0c;则 <—[]

　　广度优先搜索的代码

#include
using namespace std;
....
void BFSTraverse(Graph G)
{for (int v&＃61;0;v Q;for(int v&＃61;0;v}

 两种算法的复杂度分析

　　深度优先

　　　　数组表示&＃xff1a;查找所有顶点的所有邻接点所需时间为O(n²)&＃xff0c;n为顶点数&＃xff0c;算法时间复杂度为O(n²) 　　

　　广度优先

　　　　数组表示&＃xff1a;查找每个顶点的邻接点所需时间为O(n²)&＃xff0c;n为顶点数&＃xff0c;算法的时间复杂度为O(n²)