| 283 | } |
| 284 | |
| 285 | void ALGraph::BFS(int strtID, bool generateForest){ |
| 286 | if(strtID == -1) |
| 287 | return; |
| 288 | vector<int> awaitVexList; |
| 289 | vector<ALArc*> awaitArcList; |
| 290 | awaitVexList.push_back(strtID); |
| 291 | while(awaitVexList.size() > 0){ |
| 292 | int nextVex = awaitVexList[0]; |
| 293 | ALArc *nextArc = awaitArcList.size() > 0 ? awaitArcList[0] : nullptr; |
| 294 | awaitVexList.erase(awaitVexList.begin()); |
| 295 | if(nextArc) |
| 296 | awaitArcList.erase(awaitArcList.begin()); |
| 297 | for(ALArc *p = vexList[nextVex].firstArc; p != nullptr; p = p->nextArc){ |
| 298 | if(vexList[p->eVexID].visited == false){ |
| 299 | awaitVexList.push_back(p->eVexID); |
| 300 | awaitArcList.push_back(p); |
| 301 | if(type == UDG && GetIdOf(p->gArc->edVex()) != p->eVexID) |
| 302 | p->gArc->reverseDirection(); |
| 303 | } |
| 304 | } |
| 305 | if(nextArc && !vexList[nextArc->eVexID].visited) |
| 306 | nextArc->visit(); |
| 307 | vexList[nextVex].visit(); |
| 308 | } |
| 309 | if(generateForest){ |
| 310 | for(int i = 0; i < vexList.size(); i++){ |
| 311 | if(vexList[i].visited) continue; |
| 312 | awaitVexList.clear(); |
| 313 | awaitArcList.clear(); |
| 314 | awaitVexList.push_back(i); |
| 315 | while(awaitVexList.size() > 0){ |
| 316 | int nextVex = awaitVexList[0]; |
| 317 | ALArc *nextArc = awaitArcList.size() > 0 ? awaitArcList[0] : nullptr; |
| 318 | awaitVexList.erase(awaitVexList.begin()); |
| 319 | if(nextArc) |
| 320 | awaitArcList.erase(awaitArcList.begin()); |
| 321 | for(ALArc *p = vexList[nextVex].firstArc; p != nullptr; p = p->nextArc){ |
| 322 | if(vexList[p->eVexID].visited == false){ |
| 323 | awaitVexList.push_back(p->eVexID); |
| 324 | awaitArcList.push_back(p); |
| 325 | if(type == UDG && GetIdOf(p->gArc->edVex()) != p->eVexID) |
| 326 | p->gArc->reverseDirection(); |
| 327 | } |
| 328 | } |
| 329 | if(nextArc && !vexList[nextArc->eVexID].visited) |
| 330 | nextArc->visit(); |
| 331 | vexList[nextVex].visit(); |
| 332 | } |
| 333 | } |
| 334 | } |
| 335 | } |
| 336 | |
| 337 | void ALGraph::Dijkstra(int strtID){ |
| 338 | //Clear previous result |
no test coverage detected