| 231 | } |
| 232 | |
| 233 | void ALGraph::DFS(int strtID, bool generateForest){ |
| 234 | if(strtID == -1) |
| 235 | return; |
| 236 | vector<int> awaitVexList; |
| 237 | vector<ALArc*> awaitArcList; |
| 238 | awaitVexList.push_back(strtID); |
| 239 | while(awaitVexList.size() > 0){ |
| 240 | int nextVex = awaitVexList.back(); |
| 241 | ALArc *nextArc = awaitArcList.size() > 0 ? awaitArcList.back() : nullptr; |
| 242 | awaitVexList.pop_back(); |
| 243 | if(nextArc) |
| 244 | awaitArcList.pop_back(); |
| 245 | for(ALArc *p = vexList[nextVex].firstArc; p != nullptr; p = p->nextArc){ |
| 246 | if(vexList[p->eVexID].visited == false){ |
| 247 | awaitVexList.push_back(p->eVexID); |
| 248 | awaitArcList.push_back(p); |
| 249 | if(type == UDG && GetIdOf(p->gArc->edVex()) != p->eVexID) |
| 250 | p->gArc->reverseDirection(); |
| 251 | } |
| 252 | } |
| 253 | if(nextArc && !vexList[nextArc->eVexID].visited) |
| 254 | nextArc->visit(); |
| 255 | vexList[nextVex].visit(); |
| 256 | } |
| 257 | if(generateForest){ |
| 258 | for(int i = 0; i < vexList.size(); i++){ |
| 259 | if(vexList[i].visited) continue; |
| 260 | awaitVexList.clear(); |
| 261 | awaitArcList.clear(); |
| 262 | awaitVexList.push_back(i); |
| 263 | while(awaitVexList.size() > 0){ |
| 264 | int nextVex = awaitVexList.back(); |
| 265 | ALArc *nextArc = awaitArcList.size() > 0 ? awaitArcList.back() : nullptr; |
| 266 | awaitVexList.pop_back(); |
| 267 | if(nextArc) |
| 268 | awaitArcList.pop_back(); |
| 269 | for(ALArc *p = vexList[nextVex].firstArc; p != nullptr; p = p->nextArc){ |
| 270 | if(vexList[p->eVexID].visited == false){ |
| 271 | awaitVexList.push_back(p->eVexID); |
| 272 | awaitArcList.push_back(p); |
| 273 | if(type == UDG && GetIdOf(p->gArc->edVex()) != p->eVexID) |
| 274 | p->gArc->reverseDirection(); |
| 275 | } |
| 276 | } |
| 277 | if(nextArc && !vexList[nextArc->eVexID].visited) |
| 278 | nextArc->visit(); |
| 279 | vexList[nextVex].visit(); |
| 280 | } |
| 281 | } |
| 282 | } |
| 283 | } |
| 284 | |
| 285 | void ALGraph::BFS(int strtID, bool generateForest){ |
| 286 | if(strtID == -1) |
no test coverage detected