以下是使用C++编写的邻接表图的实现代码:
#include <iostream>
#include <vector>
template<typename V, typename E>
class GraphLink {
private:
struct Edge {
int dest; // 目标顶点编号
E cost; // 边的权值
Edge* link; // 指向下一条边的指针
};
struct Vertex {
V data; // 顶点数据
Edge* adjList; // 邻接链表头指针
};
std::vector<Vertex> vertexList; // 顶点列表
public:
GraphLink() {}
void insertVertex(V data) {
Vertex v;
v.data = data;
v.adjList = nullptr;
vertexList.push_back(v);
}
void insertEdge(int src, int dest, E cost) {
Edge* edge = new Edge();
edge->dest = dest;
edge->cost = cost;
edge->link = vertexList[src].adjList;
vertexList[src].adjList = edge;
}
void disp() const {
for (int i = 0; i < vertexList.size(); i++) {
std::cout << "Vertex " << i << ": " << vertexList[i].data << " --> ";
Edge* currEdge = vertexList[i].adjList;
while (currEdge != nullptr) {
std::cout << "(" << currEdge->dest << ", " << currEdge->cost << ") ";
currEdge = currEdge->link;
}
std::cout << std::endl;
}
}
};
int main() {
GraphLink<char, int> G;
G.insertVertex('A'); //0号
G.insertVertex('B'); //1号
G.insertVertex('C'); //2号
G.insertVertex('D'); //3号
G.insertVertex('E'); //4号
G.insertEdge(0, 1, 1);
G.insertEdge(1, 2, 2);
G.insertEdge(2, 3, 10);
G.insertEdge(2, 4, 2);
G.insertEdge(4, 0, 4);
G.disp();
return 0;
}
此代码实现了一个邻接表图的数据结构,其中GraphLink
类表示整个图。通过insertVertex
函数可以插入顶点,使用insertEdge
函数可以插入边。最后,使用disp
函数可以显示整个邻接表图。
你可以将以上代码保存为一个.cpp文件并进行编译运行。输出结果应该与以下截图一致:
内容由零声教学AI助手提供,问题来源于学员提问