已知一个带权有向图,其存储结构为邻接表结构 ,设计一算法,由键盘输入数据,建立邻接表,并将其输出。 用例说明: 第一行输入图的顶点数; 第二行输入顶点信息; 第三行以后,按照顺序,每个顶点对应一行,按行输入该顶点对应边的信息(位置 1 权值 1 位置 2 权值 2 ……. ,以 -1 结束)。 输出格式中,代表链表节点的信息是
时间: 2024-01-25 19:03:06 浏览: 97
好的,我会根据您的要求回答问题。对于您的问题,我可以给出以下 C++ 实现的算法:
```
#include <iostream>
#include <vector>
using namespace std;
struct Edge {
int to;
int weight;
};
int main() {
int num_vertices;
cout << "请输入图的顶点数:";
cin >> num_vertices;
vector<vector<Edge>> adj_list(num_vertices);
cout << "请输入每个顶点的信息:" << endl;
for (int i = 0; i < num_vertices; ++i) {
int vertex_info;
cin >> vertex_info;
}
cout << "请输入每个顶点对应边的信息:" << endl;
for (int i = 0; i < num_vertices; ++i) {
int to, weight;
cout << "顶点 " << i << " 对应边的信息(格式:位置1 权值1 位置2 权值2 ... -1):";
while (true) {
cin >> to;
if (to == -1) {
break;
}
cin >> weight;
adj_list[i].push_back({to, weight});
}
}
cout << "建立的邻接表为:" << endl;
for (int i = 0; i < num_vertices; ++i) {
cout << "顶点 " << i << ":";
for (auto edge : adj_list[i]) {
cout << "(" << edge.to << ", " << edge.weight << ") ";
}
cout << endl;
}
return 0;
}
```
这个算法使用 vector<vector<Edge>> 来存储邻接表,每个顶点的边集合用一个 vector<Edge> 来表示,其中每个 Edge 结构体表示一条边的终点和权值。在输入时,我们按行输入每个顶点对应的边的信息,将其添加到对应顶点的边集合中。最后输出建立的邻接表。
希望这个算法能够帮助您!
阅读全文
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20250102104920.png)
![cpp](https://img-home.csdnimg.cn/images/20250102104920.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)