编写程序创建以下的邻接表G，并使用如下验证代码：另：在源代码中要求对算法代码进行解释说明。提交源代码和运行结果截图。 int main(){ GraphLink G; G.insertVertex('A'); //0号 G.insertVertex('B'); //1号 G.insertVertex('C'); //2号 G.insertVertex('D'); //3号 G.insertVertex(...-DPDK中文网

以下是使用C++编写的邻接表GraphLink类的实现示例代码：

#include <iostream>
#include <vector>
using namespace std;

template<typename T, typename E>
struct Edge {
    int dest;   // 目标顶点索引
    E cost;     // 边权值
    Edge<T, E> *next;  // 下一条边
};

template<typename T, typename E>
struct Vertex {
    T data;               // 顶点数据
    Edge<T, E> *adjList;  // 邻接表头指针
};

template<typename T, typename E>
class GraphLink {
private:
    vector<Vertex<T, E>> vertexList;  // 顶点数组

public:
    GraphLink() {}

    void insertVertex(T data) {
        Vertex<T, E> v;
        v.data = data;
        v.adjList = nullptr;
        vertexList.push_back(v);
    }

    void insertEdge(int srcIndex, int destIndex, E cost) {
        Edge<T, E> *newEdge = new Edge<T, E>;
        newEdge->dest = destIndex;
        newEdge->cost = cost;
        newEdge->next = nullptr;

        if (vertexList[srcIndex].adjList == nullptr) {  // 若源顶点的邻接表为空，则直接插入新边作为头结点
            vertexList[srcIndex].adjList = newEdge;
        } else {                                        // 否则将新边插入到源顶点的邻接表末尾
            Edge<T, E> *edgePtr = vertexList[srcIndex].adjList;
            while (edgePtr->next != nullptr)
                edgePtr = edgePtr->next;
            edgePtr->next = newEdge;
        }
    }

    void disp() {
        for (int i = 0; i < vertexList.size(); i++) {
            cout << "顶点" << i << "(" << vertexList[i].data << "): ";
            Edge<T, E> *edgePtr = vertexList[i].adjList;
            while (edgePtr != nullptr) {
                cout << "(" << vertexList[edgePtr->dest].data << "," << edgePtr->cost << ") ";
                edgePtr = edgePtr->next;
            }
            cout << 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结果截图