首页pta6-4 图的创建

pta6-4 图的创建

时间: 2025-07-06 19:53:54 AIGC 浏览: 22

### PTA 6-4 图的创建 #### 创建邻接表表示法下的图为了实现高效的操作，在 C++ 中可以采用邻接表来存储无向图。邻接表是一种链式结构，对于每一个顶点建立一个单链表，第 i 个单链表中的结点表示依附于顶点 vi 的边(对于有向图则是以顶点 vi 为弧尾的弧)，这些结点构成一个线性表，其存储结构用顺序存储结构来表示。 ```cpp #include <iostream> #include <vector> using namespace std; class Edge { public: int to; int weight; Edge* next; Edge(int t, int w) : to(t), weight(w), next(nullptr) {} }; void addEdge(vector<Edge*>& adjList, int from, int to, int weight) { Edge* newEdge = new Edge(to, weight); newEdge->next = adjList[from]; adjList[from] = newEdge; } int main() { int n, m; cin >> n >> m; // 输入节点数量和边的数量 vector<Edge*> adjList(n, nullptr); for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; --u; --v; // 转换为从0开始编号 addEdge(adjList, u, v, w); // 添加双向边 addEdge(adjList, v, u, w); } // 打印邻接表验证正确性 for (int i = 0; i < n; ++i) { cout << "Node " << i + 1 << ": "; for (Edge* e = adjList[i]; e != nullptr; e = e->next) { cout << "(" << e->to + 1 << ", " << e->weight << ") -> "; } cout << endl; } return 0; } ``` 此程序首先定义了一个 `Edge` 类用于保存边的信息以及指向下一个相邻边的指针；接着实现了 `addEdge()` 函数用来往给定位置处添加新的边；最后在主函数里通过循环读入所有的边，并调用上述辅助函数完成整个图的构建工作[^1]。

阅读全文