蓝桥杯之图
图：对于图来说，重点在于之后的最短路径算法，这边简朴做一下相识即可
https://i-blog.csdnimg.cn/direct/ca96428aa7bf462baff9169d33a89758.png
https://i-blog.csdnimg.cn/direct/b94b7b0ba30541068d7a1406bd63afad.png
https://i-blog.csdnimg.cn/direct/729c4c9d3dca4848a4028b0bd5da63a0.png
https://i-blog.csdnimg.cn/direct/f23935d9d6874352bdd2698e653811dc.png
https://i-blog.csdnimg.cn/direct/fb102d7476a248bd8ae142b98d5ea70e.png
代码：
#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 = { 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.data_ << " ";
for (auto a : vertics.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 = true;
while (!que.empty())
{
int vertic=que.front();
que.pop();
cout << vertics.data_ << " ";
for (auto a : vertics.adjList_)
{
if (state == false)
{
que.push(a);
state = 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 = true;
while (!que.empty())
{
int vertic = que.front();
if (vertic == end)
break;
que.pop();
//cout << vertics.data_ << " ";
for (auto a : vertics.adjList_)
{
if (state == false)
{
que.push(a);
state = true;
path = vertic;
}
}
}
printPath(path,end);
cout << endl;
}
private:
void dfs_(int start,vector<bool>&state)
{
if (state)
{
return;
}
cout << vertics.data_ << " ";
state = true;
for (auto a : vertics.adjList_)
{
dfs_(a, state);
}
}
void printPath(vector<int>& path,int end)
{
if (end == 0)
return;
printPath(path, path);
cout << vertics.data_ << " ";
}
};
int main()
{
Digraph graph;
graph.readFile("jiedian.txt");
graph.show();
graph.dfs();
graph.bfs();
graph.shortPath(1, 8);
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]