蓝桥杯之图

图：

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

代码：

#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;
}