图对于图来说重点在于之后的最短路径算法这边简单做一下了解即可代码#includeiostream #includestring #includevector #includelist #includequeue using namespace std; class Digraph { private: //顶点类型 struct Vertic { Vertic(string data) :data_(data) { } string data_;//存储顶点信息 listintadjList_;//邻接链表 }; vectorVerticvertics;//邻接表结构 public: void readFile(string file)//读取配置文件生成邻接表 { FILE* pf fopen(file.c_str(), r); if (pf nullptr) { throw file not exists!; } //占用0号位置利用emplace_back()可以利用自定义对象的构造函数 vertics.emplace_back(); while (!feof(pf)) { char line[1024] { 0 }; fgets(line, 1024, pf); string Line(line); //增加一个节点信息 vertics.emplace_back(Line.substr(0,Line.size()-1)); fgets(line, 1024, pf); char* vers strtok(line, ,); while (vers ! nullptr) { int a atoi(vers); if(a0) vertics.back().adjList_.emplace_back(a); versstrtok(NULL, ,); } } fclose(pf); } //输出邻接表信息 void show()const { for (int i1;ivertics.size();i) { cout vertics[i].data_ ; for (auto a : vertics[i].adjList_) { cout a ; } cout endl; } } //图的深度优先遍历 void dfs() { vectorboolstate(vertics.size(), 0); dfs_(1,state); cout endl; } //图的广度优先遍历 void bfs() { queueintque; vectorboolstate(vertics.size(), 0); que.push(1); state[1] true; while (!que.empty()) { int verticque.front(); que.pop(); cout vertics[vertic].data_ ; for (auto a : vertics[vertic].adjList_) { if (state[a] false) { que.push(a); state[a] true; } } } cout endl; } //不带权值的最短路径类似与广度优先遍历一层一层找肯定会比深度遍历要强 void shortPath(int start,int end) { queueintque; vectorboolstate(vertics.size(), 0); vectorintpath(vertics.size(), 0); que.push(start); state[start] true; while (!que.empty()) { int vertic que.front(); if (vertic end) break; que.pop(); //cout vertics[vertic].data_ ; for (auto a : vertics[vertic].adjList_) { if (state[a] false) { que.push(a); state[a] true; path[a] vertic; } } } printPath(path,end); cout endl; } private: void dfs_(int start,vectorboolstate) { if (state[start]) { return; } cout vertics[start].data_ ; state[start] true; for (auto a : vertics[start].adjList_) { dfs_(a, state); } } void printPath(vectorint path,int end) { if (end 0) return; printPath(path, path[end]); cout vertics[end].data_ ; } }; int main() { Digraph graph; graph.readFile(jiedian.txt); graph.show(); graph.dfs(); graph.bfs(); graph.shortPath(1, 8); return 0; }