蓝桥杯之图

图：

对于图来说，重点在于之后的最短路径算法，这边简单做一下了解即可

代码：

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<queue>
using namespace std;
class Digraph
{
private://顶点类型struct Vertic{Vertic(string data) :data_(data) {}string data_;//存储顶点信息list<int>adjList_;//邻接链表};vector<Vertic>vertics;//邻接表结构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(a>0)vertics.back().adjList_.emplace_back(a);vers=strtok(NULL, ",");}}fclose(pf);}//输出邻接表信息void show()const{for (int i=1;i<vertics.size();i++){cout << vertics[i].data_ << " ";for (auto a : vertics[i].adjList_){cout << a << " ";}cout << endl;}}//图的深度优先遍历void dfs(){vector<bool>state(vertics.size(), 0);dfs_(1,state);cout << endl;}//图的广度优先遍历void bfs(){queue<int>que;vector<bool>state(vertics.size(), 0);que.push(1);state[1] = true;while (!que.empty()){int vertic=que.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){queue<int>que;vector<bool>state(vertics.size(), 0);vector<int>path(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,vector<bool>&state){if (state[start]){return;}cout << vertics[start].data_ << " ";state[start] = true;for (auto a : vertics[start].adjList_){dfs_(a, state);}}void printPath(vector<int>& 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;
}