链式前向星的c++算法实现

链式前向星是一种用于存储图的数据结构，它使用链表来表示每个顶点的邻接顶点集合。下面是一个用C++实现的链式前向星算法：

#include <iostream>
#include <vector>

using namespace std;

struct Edge {
    int to;
    int next;
};

class Graph {
public:
    Graph(int n) : numVertices(n), numEdges(0) {
        head.resize(numVertices, -1);
    }

    void addEdge(int from, int to) {
        edges.push_back({to, head[from]});
        head[from] = numEdges++;
    }

    void printGraph() {
        for (int i = 0; i < numVertices; i++) {
            cout << "Adjacency list of vertex " << i << ": ";
            int edgeIndex = head[i];
            while (edgeIndex != -1) {
                cout << edges[edgeIndex].to << " ";
                edgeIndex = edges[edgeIndex].next;
            }
            cout << endl;
        }
    }

private:
    int numVertices;
    int numEdges;
    vector<int> head;
    vector<Edge> edges;
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 4);
    g.addEdge(4, 0);

    g.printGraph();

    return 0;
}

在这个实现中，Graph类有两个私有成员变量numVertices和numEdges，分别表示图的顶点数和边数。head是一个大小为numVertices的vector，用来存储每个顶点的邻接边的索引。edges是一个存储边的vector，每个边包含一个to成员变量表示边的终点顶点，以及一个next成员变量表示与当前边有相同起点的下一条边的索引。

addEdge函数用来添加一条边到图中。它接受两个参数，表示边的起点和终点。该函数将新的边添加到edges中，并将其索引添加到head[from]的链表头部。

printGraph函数用来打印图的邻接表表示。它遍历每个顶点的链表，将每个邻接顶点打印出来。

在main函数中，我们创建一个包含5个顶点的图，并添加了6条边。然后调用printGraph函数打印图的邻接表表示。

运行这段代码，输出结果为：

Adjacency list of vertex 0: 2 1
Adjacency list of vertex 1: 3
Adjacency list of vertex 2: 4
Adjacency list of vertex 3: 4
Adjacency list of vertex 4: 0

这个结果表示了图中每个顶点的邻接顶点。例如，顶点0的邻接顶点是2和1