<1> 创建图很简单,让用户输入一些“边,点,权值"来构建一下图
<2>广度优先
针对下面的“图型结构”,我们如何广度优先呢?其实我们只要深刻理解"广搜“给我们定义的条条框框就行了。 为了避免同一个顶点在遍历时被多
次访问,可以将”顶点的下标”存放在sTrav[]的bool数组,用来标识是否已经访问过该节点。
第一步:首先我们从isTrav数组中选出一个未被访问的节点,如V1。
第二步:访问V1的邻接点V2,V3,V5,并将这三个节点标记为true。
第三步:第二步结束后,我们开始访问V2的邻接点V1,V3,但是他们都是被访问过的。
第四步:我们从第二步结束的V3出发访问他的邻接点V2,V1,V5,V4,还好V4是未被访问的,此时标记一下。
第五步:我们访问V5的邻接点V1,V3,V4,不过都是已经访问过的。
第六步:有的图中通过一个顶点的“广度优先”不能遍历所有的顶点,此时我们重复(1-5)的步骤就可以最终完成广度优先遍历。
<3> 深度优先
同样是这个图,大家看看如何实现深度优先,深度优先就像铁骨铮铮的好汉,遵循“能进则进,不进则退”的原则。
第一步:同样也是从isTrav数组中选出一个未被访问的节点,如V1。
第二步:然后一直访问V1的邻接点,一直到走头无路的时候“回溯”,路线为V1,V2,V3,V4,V5,到V5的时候访问邻接点V1,发现V1是访问过的,
此时一直回溯的访问直到V1。
第三步: 同样有的图中通过一个顶点的“深度优先”不能遍历所有的顶点,此时我们重复(1-2)的步骤就可以最终完成深度优先遍历。
最后上一下总的代码
代码中我们构建了如下的“图”。