1 /**2 *图的广度优先为3 **/
4voidBreadthfirstsearch(graphg，intvtx )5 {6 Queue queue； //定义循环队列
7初始队列(queue )； //队列初始化
8if(g.visited[vtx]==false )//是否未访问过
9 G.visited[vtx]=true； //设置访问标志，可以插入顶点访问操作
10enqueue(queue，vtx )； //顶点排队
11 while (！ isempty(queue )/*循环至队列为空) /
12intcurVTX=dequeue(queue )； //队列元素出队
13 for (inttemp=firstadjoinvertex (g，curVtx ) )； 临时！=-1； temp=nextadjoinvertex(g，curVtx，temp ) ) 14if ) g.visited[temp]==false )//是否从未访问过
15 G.visited[temp]=true； //设置访问标志
16enqueue(queue，temp )； //刚刚访问的顶点元素入队
17 } 18 } 19 } 20干扰队列(queue )； 21 ) 22
23 /**24 *图深度优先遍历(递归实现) 25 **/
26 voiddepthfirsttraverse (graphg，intvtx ) 27 ) 28g.visited ) vtx )=true； //设置访问标志
29 for (inttemp VTX=firstadjoinvertex (g，vtx ) )； tempVtx！=-1； tempvtx(//依次访问顶点vtx的相邻顶点
30if(g.visited[tempvtx]==false ) /如果未访问顶点，则递归调用
31depthfirsttraverse(g，tempVtx )； 32 ) 33 ) 34
35 /**36 *图的深度优先遍历的非递归算法37 *思路：根据图的深度优先遍历规则，可以用不同的非递归算法实现图的深度优先搜索遍历。 38 *以下列举三种方法。 39 **/
40 /**41 * 1、找出顶点vtx并采用1个未访问顶点的操作： notvisitadjoinvertex(g，vtx )、42 )通过按照各顶点最初搜索到的邻接点为先的顺序进行深度优先搜索遍历来进行43 **/
44 voiddepthfirstsearch _1(graphg，intvtx ) 45 ) 46堆栈； //从顶点vtx开始深度优先遍历图表g
47initstack(stack，MAXSIZE )； //初始化堆栈堆栈
48if(g.visited[vtx]==false ) (如果未访问vtx，请访问并标记
49 G.visited[vtx]=true； 50 cout vtx '-'； 51 ) 52推式(stack，-1；//将"-1 "作为横移结束的标志
53推式(stack，vtx )； //刚访问的顶点进入堆栈
54 int preVtx=vtx； //preVtx是指刚访问的顶点
55while(prevtx！=-1(//循环直到遇到结束标志
56 inttemp vtx=notvisitadjoinvertex (g，preVtx )； 寻找preVtx未访问的临界点tempVtx
57if(tempVTX！=-1 )找到tempVtx后访问并标记
58 G.visited[tempVtx]=true； 59 cout tempVtx '-'； 60推式(stack，tempVtx )； 将tempVtx放入堆栈
61 preVtx=tempVtx； 继续寻找tempVtx未访问的邻点
62 ) else{63prevtx=pop(stack )； //如果当前顶点的所有相邻点都已被访问，则退出堆栈顶部的顶点并继续循环搜索
64(65 ) 64(65 )
68 /**69 * 2、相对于顶点vtx_1寻找相对于相邻点vtx_2下一个相邻点的操作： nextadjoinvertex(g，vtx_1，vtx_2)、70 )按照最后搜索到顶点的相邻点为先的顺序
72 voiddepthfirstsearch _2(graphg，intvtx ) 73 ) 74堆栈堆栈； //定义堆栈
75 InitStack(stack, MAXSIZE); //初始化栈stack
76 Push(stack, vtx); //起始顶点入栈
77 while(!IsEmpty(stack)) { //循环至栈stack空
78 int currVtx = Pop(stack); //currVtx为栈顶顶点
79 if(G.visited[currVtx] == false) { //若currVtx未被访问过，访问并标记
80 G.visited[currVtx] = true;81 cout << currVtx << "->";82 }83 /*找出刚访问过的顶点currVtx的所有邻接点，并将未被访问过的邻接点依次入栈*/
84 for(int temp = FirstAdjoinVertex(G, currVtx); temp != -1; temp =NextAdjoinVertex(G, currVtx, temp)) {85 if(G.visited[temp] == false)86 Push(stack, temp);87 }88 }89 }90
91 /**92 * 3、利用对顶点vtx_1找相对于邻接点vtx_2的下一个邻接点的操作：NextAdjoinVertex(G, vtx_1, vtx_2)，93 * 以每个顶点最先搜索到的邻接点在先的顺序做深度优先搜索遍历来实现94 **/
95 void DepthFirstSearch_3(Graph &G, intvtx)96 {97 Stack stack; //定义顺序栈
98 InitStack(stack, MAXSIZE); //初始化顺序栈
99 if(G.visited[vtx] == false) { //若顶点vtx未被访问过，访问并标记之
100 G.visited[vtx] = true;101 cout << vtx << "->";102 }103 Push(stack, vtx); //初始顶点入栈
104 while(!IsEmpty(stack)) { //循环遍历直到栈stack空
105 int preVtx = GetTop(stack); //读取出栈顶顶点并赋给preVtx
106 int flag = 1; //当前正在检查的顶点preVtx是否有未被访问的邻接点的标志，“1”表示都被访问过
107 for(int temp = FirstAdjoinVertex(G, preVtx); preVtx != -1; temp =NextAdjoinVertex(G, preVtx, temp)) {108 if(G.visited[temp] == false) { //若找到temp的未被访问过的邻接顶点temp，访问并标记
109 G.visited[temp] = true;110 cout << temp << "->";111 Push(stack, temp); //将stack入栈
112 flag = 0; //置还有未被访问过的邻接点标志“0”
113 break; //继续对刚刚访问的顶点temp查找是否有未被访问过的邻接点
114 }115 }116 if(flag == 1) //若栈顶顶点的所有邻接点都已经访问过，则将其退栈
117 Pop(stack);118 }119 }120
121 /**122 * 寻找图中从顶点vtx_1到顶点vtx_2的简单路径123 * 基本思路：124 * 对依附于顶点vtx_1的每条边，寻找从顶点temp_1到顶点vtx_2的一条简单路径，而且不经过vtx_1，125 * 考虑依附于顶点temp_1的边，寻找从顶点temp_2到顶点vtx_2的一条简单路径，并且不经过顶点vtx_1和126 * 顶点temp_1，如此下去，直到找到解为止，所以这个问题可以利用深度优先遍历实现。127 * 从顶点vtx_1出发做深度优先遍历，如果遇到顶点vtx_2，回溯就可以得到从顶点vtx_1到顶点vtx_2的一条路径。那128 * 如何保证这是一条简单路径，方法是：维护一条路径，依次记录深度优先遍历过程中访问过的顶点；在深度优先遍历过程中，如果129 * 顶点的所有邻接顶点都被访问过，仍然未能到达目标顶点vtx_2，则将此顶点从路径中删除；到达目标顶点后，就可以得到一条简单路径130 **/
131 void SimplePath(Graph &G, int vtx_1, intvtx_2)132 {133 G.visited[vtx_1] = true; //设置访问标志
134 Append(path, vtx_1); //将当前顶点加入路径
135 for (int temp = FirstAdjoinVertex(G, vtx_1); temp != -1; temp =NextAdjoinVertex(G, vtx_1, temp)){136 if (temp == vtx_2) { //查找成功
137 Append(path, vtx_2);138 return;139 }140 if (!G.visited(temp)) //递归调用，深度优先遍历
141 SimplePath(G, temp, vtx_2);142 }143 Delete(path, vtx_1); //删除路径上最后一个顶点
144 }145
146 /**147 * 非连通图的遍历148 **/
149 void DepthFirstTraverse(Graph &G, intvtx)150 {151 for (vtx = 0; vtx < G.vtxCnt; ++vtx) { //只需把每个顶点作为起点进行深度优先遍历即可
152 G.visited[vtx] = true;153 for (int temp = FirstAdjoinVertex(G, vtx); temp != -1; tmep =NextAdjoinVertex(G, vtx, temp)){154 if (G.visited[temp] == false)155 DepthFirstTraverse(G, temp);156 }157 }158 }