无向图的深度优先与广度优先搜索代码实现

 1 //深度优先
 2 void GraphAdjacencyListWeight::DFSAdvanced(int StartVertex) {
 3     int *visited = new int[VertexNumber];
 4     //手动初始化
 5     //不知道为什么memset不好用
 6     for (int lop = 0; lop < VertexNumber; lop++) {
 7         visited[lop] = 0;
 8     }
 9 
10     stack<int> S;
11     S.push(StartVertex);
12 
13     int NextVertex = -1;
14 
15     while (!IsAllVisited(visited)) {
16         //如果有其他的连通分量
17         if (S.empty()) {
18             //随便找一个没被访问的点丢进栈
19             for (int lop = 0; lop < VertexNumber; lop++) {
20                 if (visited[lop] == 0) {
21                     S.push(lop);
22                     break;
23                 }
24             }
25         }
26         while(!S.empty()) {
27             NextVertex = S.top();
28             S.pop();
29 
30             if (visited[NextVertex] != 1) {
31                 //访问该点
32                 VisitVertex(NextVertex);
33                 //标记为访问过
34                 visited[NextVertex] = 1;
35                 //将下一个没被访问过的邻接点入栈
36                 PushValidVertexToStack(S, NextVertex, visited);
37             }
38         }
39     }
40 }

 1 //广度优先
 2 void GraphAdjacencyListWeight::BFSAdvanced(int StartVertex) {
 3     int *visited = new int[VertexNumber];
 4     //手动初始化
 5     //不知道为什么memset不好用
 6     for (int lop = 0; lop < VertexNumber; lop++) {
 7         visited[lop] = 0;
 8     }
 9 
10     queue<int> Q;
11     Q.push(StartVertex);
12 
13     //下一个将要访问的顶点的序号
14     int NextVertex = -1;
15 
16     //当还有顶点没被访问时
17     while (!IsAllVisited(visited)) {
18         //如果有其他的连通分量
19         if (Q.empty()) {
20             //随便找一个没被访问的点丢进队列
21             for (int lop = 0; lop < VertexNumber; lop++) {
22                 if (visited[lop] == 0) {
23                     Q.push(lop);
24                     break;
25                 }
26             }
27         }
28 
29         while (!Q.empty()) {
30             //获取队列前端元素
31             NextVertex = Q.front();
32             Q.pop();
33 
34             //如果该点没被访问过
35             if (visited[NextVertex] != 1) {
36                 //访问该点
37                 VisitVertex(NextVertex);
38                 //标记为访问过
39                 visited[NextVertex] = 1;
40                 //将该点的邻接点入队
41                 EnQueueAllAdjVer(Q, NextVertex);
42             }
43         }
44     }
45 }

 1 int GraphAdjacencyListWeight::IsAllVisited(int visit[]) {
 2     for (int lop = 0; lop < VertexNumber; lop++) {
 3         if (visit[lop] == 0) {
 4             return 0;
 5         }
 6     }
 7     return 1;
 8 }
 9 
10 void GraphAdjacencyListWeight::VisitVertex(int i) {
11     cout << "Vertex : " << VectorVertexList[i]->VertexIndex << endl;
12 }
13 
14 void GraphAdjacencyListWeight::EnQueueAllAdjVer(queue<int> &Q, int index) {
15     for (auto tmpPtr = VectorVertexList[index]->firstArc; tmpPtr != nullptr; tmpPtr = tmpPtr->nextArc) {
16         Q.push(tmpPtr->AdjacencyNode);
17     }
18 }
19 
20 void GraphAdjacencyListWeight::PushValidVertexToStack(stack<int> &S, int index, int visit[]) {
21     for (auto Ptr = VectorVertexList[index]->firstArc; Ptr != nullptr; Ptr = Ptr->nextArc) {
22         if (visit[Ptr->AdjacencyNode] != 1) {
23             S.push(Ptr->AdjacencyNode);
24             return;
25         }
26     }
27 }