以下是使用C++编写的创建邻接表的示例代码:
#include <iostream>
#include <vector>
template<class T, class E>
class GraphLink{
private:
struct EdgeNode{ // 边表节点结构体
int dest; // 目标顶点在顶点数组中的索引
E weight; // 边的权重
EdgeNode* next; // 下一个边表节点指针
EdgeNode(int d = 0, E w = 0): dest(d), weight(w), next(nullptr) {}
};
struct VertexNode{ // 顶点结构体
T data; // 顶点数据
EdgeNode* firstEdge; // 第一个边表节点指针
VertexNode() : firstEdge(nullptr) {}
};
std::vector<VertexNode> vertexList; // 存储顶点列表
public:
void insertVertex(const T& data){
vertexList.push_back(VertexNode());
vertexList[vertexList.size()-1].data = data;
}
void insertEdge(int srcIndex, int destIndex, const E& weight){
if (srcIndex >= 0 && srcIndex < vertexList.size() &&
destIndex >= 0 && destIndex < vertexList.size()) {
EdgeNode* newEdge = new EdgeNode(destIndex, weight);
newEdge->next = vertexList[srcIndex].firstEdge;
vertexList[srcIndex].firstEdge = newEdge;
}
}
void disp(){
for (int i = 0; i < vertexList.size(); ++i) {
std::cout << "Vertex " << i << ": " << vertexList[i].data << std::endl;
EdgeNode* edge = vertexList[i].firstEdge;
while (edge != nullptr) {
std::cout << " --> Destination: " << edge->dest << ", Weight: " << edge->weight << std::endl;
edge = edge->next;
}
}
}
};
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
函数用于打印邻接表。
在示例代码中,首先创建了一个空的图对象 G
。然后依次插入5个顶点,并根据题目要求添加了一些边。最后调用 disp()
函数打印整个邻接表。
你可以将上述代码复制到一个名为 main.cpp
的源文件中,并编译运行来验证结果。注意,代码中已经包含了必要的注释来解释算法代码的作用。
内容由零声教学AI助手提供,问题来源于学员提问