bool visited[MaxVnum]; void DFS(Graph G,int v) { visited[v]= true; //从V开始访问，flag它 printf("%d",v); //打印出V for(int j=0;j<G.vexnum;j++) if(G.arcs[v][j]==1&&visited[j]== false) //这里可以获得V未访问过的邻接点 DFS(G,j); //递归调用，如果所有节点都被访问过，就回溯，而不再调用这里的DFS } void DFSTraverse(Graph G) { for (int v = 0; v < G.vexnum; v++) visited[v] = false; //刚开始都没有被访问过 for (int v = 0; v < G.vexnum; ++v) if (visited[v] == false) //从没有访问过的第一个元素来遍历图 DFS(G, v); }
3.广度优先搜索算法 分析广度优先遍历所谓广度，就是一层一层的，向下遍历，层层堵截，还是这幅图，我们如果要是广度优先遍历的话，我们的结果是V1 V2 V3 V4 V5 V6 V7 V8。
广度优先搜索的思想：
① 访问顶点vi ；
② 访问vi 的所有未被访问的邻接点w1 ,w2 , …wk ；
③ 依次从这些邻接点（在步骤②中访问的顶点）出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问；
说明：
为实现③，需要保存在步骤②中访问的顶点，而且访问这些顶点的邻接点的顺序为：先保存的顶点，其邻接点先被访问。 这里我们就想到了用标准模板库中的queue队列来实现这种先进现出的服务。
老规矩我们还是走一边流程：
说明：
☐将V1加入队列，取出V1，并标记为true(即已经访问)，将其邻接点加进入队列，则 <—[V2 V3]
☐取出V2，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[V3 V4 V5]
☐取出V3，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[V4 V5 V6 V7]
☐取出V4，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[V5 V6 V7 V8]
☐取出V5，并标记为true(即已经访问)，因为其邻接点已经加入队列，则 <—[V6 V7 V8]
☐取出V6，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[V7 V8]
☐取出V7，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[V8]
☐取出V8，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[]
广度优先搜索的代码#include <queue> using namespace std; .... void BFSTraverse(Graph G) { for (int v=0;v<G.vexnum;v++) //先将其所有顶点都设为未访问状态 visited[v]=false; queue<int> Q; for(int v=0;v<G.vexnum;v++) { if(visited[v]==false) //若该点没有访问 { Q.push(v); //将其加入到队列中 visited[v]=true; while (!Q.empty()) //只要队列不空，遍历就没有结束 { int t =Q.front(); //取出对头元素 Q.pop(); printf(" %d ",t+1); for(int j=0;j<G.vexnum;j++) //将其未访问过的邻接点加进入队列 if(G.arcs[t][j]==1&&visited[j]== false) { Q.push(j); visited[j]=true; //在这里要设置true，因为这里该顶点我们已经加入到了队列，为了防止重复加入！ } } } } }
两种算法的复杂度分析深度优先