蓝桥杯之图

图：

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

代码：

1. #include<iostream>
2. #include<string>
3. #include<vector>
4. #include<list>
5. #include<queue>
6. using namespace std;
7. class Digraph
8. {
9. private:
10.         //顶点类型
11.         struct Vertic
12.         {
13.                 Vertic(string data) :data_(data) {
14.                 }
15.                 string data_;//存储顶点信息
16.                 list<int>adjList_;//邻接链表
17.         };
18.         vector<Vertic>vertics;//邻接表结构
20. public:
21.         void readFile(string file)//读取配置文件生成邻接表
22.         {
23.                 FILE* pf = fopen(file.c_str(), "r");
24.                 if (pf == nullptr)
25.                 {
26.                         throw file + "not exists!";
27.                 }
28.                 //占用0号位置，利用emplace_back()可以利用自定义对象的构造函数
29.                 vertics.emplace_back("");
30.                 while (!feof(pf))
31.                 {
32.                         char line[1024] = { 0 };
33.                         fgets(line, 1024, pf);
34.                         string Line(line);
36.                         //增加一个节点信息
37.                         vertics.emplace_back(Line.substr(0,Line.size()-1));
38.                         fgets(line, 1024, pf);
39.                         char* vers = strtok(line, ",");
40.                         while (vers != nullptr)
41.                         {
42.                                 int a = atoi(vers);
43.                                 if(a>0)
44.                                         vertics.back().adjList_.emplace_back(a);
45.                                 vers=strtok(NULL, ",");
46.                         }
47.                 }
48.                 fclose(pf);
49.         }
50.         //输出邻接表信息
51.         void show()const
52.         {
53.                 for (int i=1;i<vertics.size();i++)
54.                 {
55.                         cout << vertics[i].data_ << " ";
56.                         for (auto a : vertics[i].adjList_)
57.                         {
58.                                 cout << a << " ";
59.                         }
60.                         cout << endl;
61.                 }
62.         }
63.         //图的深度优先遍历
64.         void dfs()
65.         {
66.                 vector<bool>state(vertics.size(), 0);
67.                 dfs_(1,state);
68.                 cout << endl;
69.         }
70.         //图的广度优先遍历
71.         void bfs()
72.         {
73.                 queue<int>que;
74.                 vector<bool>state(vertics.size(), 0);
75.                 que.push(1);
76.                 state[1] = true;
77.                 while (!que.empty())
78.                 {
79.                         int vertic=que.front();
80.                         que.pop();
81.                         cout << vertics[vertic].data_ << " ";
82.                         for (auto a : vertics[vertic].adjList_)
83.                         {
84.                                 if (state[a] == false)
85.                                 {
86.                                         que.push(a);
87.                                         state[a] = true;
88.                                 }
89.                                        
90.                         }
91.                 }
92.                 cout << endl;
93.         }
94.         //不带权值的最短路径，类似与广度优先遍历，一层一层找肯定会比深度遍历要强
95.         void shortPath(int start,int end)
96.         {
97.                 queue<int>que;
98.                 vector<bool>state(vertics.size(), 0);
99.                 vector<int>path(vertics.size(), 0);
100.                 que.push(start);
101.                 state[start] = true;
102.                 while (!que.empty())
103.                 {
104.                         int vertic = que.front();
105.                         if (vertic == end)
106.                                 break;
107.                         que.pop();
108.                         //cout << vertics[vertic].data_ << " ";
109.                         for (auto a : vertics[vertic].adjList_)
110.                         {
111.                                 if (state[a] == false)
112.                                 {
113.                                         que.push(a);
114.                                         state[a] = true;
115.                                         path[a] = vertic;
116.                                 }
117.                         }
118.                 }
119.                 printPath(path,end);
120.                 cout << endl;
121.         }
122. private:
123.         void dfs_(int start,vector<bool>&state)
124.         {
125.                 if (state[start])
126.                 {
127.                         return;
128.                 }
129.                 cout << vertics[start].data_ << " ";
130.                 state[start] = true;
131.                 for (auto a : vertics[start].adjList_)
132.                 {
133.                         dfs_(a, state);
134.                 }
135.         }
136.         void printPath(vector<int>& path,int end)
137.         {
138.                 if (end == 0)
139.                         return;
140.                 printPath(path, path[end]);
141.                 cout << vertics[end].data_ << " ";
142.         }
143. };
144. int main()
145. {
146.         Digraph graph;
147.         graph.readFile("jiedian.txt");
148.         graph.show();
149.         graph.dfs();
150.         graph.bfs();
151.         graph.shortPath(1, 8);
152.         return 0;
153. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。