1 #include<iostream> 2 #include<stack> 3 4 #define MAX_verts 20 5 using namespace std; 6 class Vertex 7 { 8 public: 9 Vertex(char lab) 10 { 11 Label = lab; 12 wasVisited = false; 13 } 14 public: 15 bool wasVisited; 16 char Label; 17 }; 18 19 class Graph 20 { 21 private: 22 Vertex * vertexList[MAX_verts]; 23 int nVerts; 24 int adjMat[MAX_verts][MAX_verts]; 25 int getAdjUnvisitedVertex(int v); 26 public: 27 Graph(); 28 ~Graph(); 29 void addVertex(char lab); 30 void addEdge(int start, int end); 31 void printMatric(); 32 void showVertex(int v); 33 void DFS(); 34 }; 35 void Graph::DFS() 36 { 37 stack<int> gStack; 38 vertexList[0]->wasVisited = true; 39 showVertex(0); 40 gStack.push(0); 41 int v; 42 while (gStack.size()>0) 43 { 44 v = getAdjUnvisitedVertex(gStack.top()); 45 if (v == -1) 46 gStack.pop(); 47 else 48 { 49 vertexList[v]->wasVisited = true; 50 showVertex(v); 51 gStack.push(v); 52 } 53 } 54 cout << endl; 55 for (int j = 0; j < nVerts; j++) 56 { 57 vertexList[j]->wasVisited = false; 58 } 59 } 60 61 Graph::Graph() 62 { 63 nVerts = 0; 64 for (int i = 0; i < MAX_verts; i++) 65 { 66 for (int j = 0; j < MAX_verts; j++) 67 { 68 adjMat[i][j] = 0; 69 } 70 } 71 } 72 73 int Graph::getAdjUnvisitedVertex(int v) 74 { 75 for (int j = 0; j < nVerts; j++) 76 { 77 if ((adjMat[v][j] == 1) && (vertexList[j]->wasVisited == false)) 78 return j; 79 } 80 return -1; 81 } 82 83 void Graph::showVertex(int v) 84 { 85 cout << vertexList[v]->Label << " "; 86 } 87 Graph::~Graph() 88 { 89 for (int i = 0; i < nVerts; i++) 90 { 91 delete vertexList[i]; 92 } 93 } 94 95 void Graph::addVertex(char lab) 96 { 97 vertexList[nVerts++] = new Vertex(lab); 98 } 99 100 void Graph::addEdge(int start, int end) 101 { 102 adjMat[start][end] = 1; 103 adjMat[end][start] = 1; 104 } 105 106 void Graph::printMatric() 107 { 108 for (int i = 0; i < nVerts; i++) 109 { 110 for (int j = 0; j < nVerts; j++) 111 { 112 cout << adjMat[i][j] << " "; 113 } 114 cout << endl; 115 } 116 } 117 118 int main() 119 { 120 Graph g; 121 g.addVertex('A'); 122 g.addVertex('B'); 123 g.addVertex('C'); 124 g.addVertex('D'); 125 g.addVertex('E'); 126 g.addVertex('F'); 127 g.addVertex('G'); 128 129 g.addEdge(0,1); 130 g.addEdge(1,3); 131 g.addEdge(0,2); 132 g.addEdge(2,5); 133 g.addEdge(1,4); 134 g.addEdge(4,6); 135 136 g.printMatric(); 137 cout << "深度优先搜索的结果:" << endl; 138 g.DFS(); 139 system("pause"); 140 return 0; 141 }
深度优先搜索-DFS遍历图-C++
坚持比努力更重要