有向图采用邻接表存储表示,设计算法,输出各顶点的所有出边及其出度c++
时间: 2024-12-22 22:31:59 浏览: 3
在C++中,我们可以使用邻接表来存储有向图的数据结构,它是一种稀疏图的高效存储方式,因为如果图中大部分节点之间没有边相连,邻接列表会节省大量空间。以下是创建一个简单的邻接表并实现输出每个顶点所有出边及其出度的算法:
```cpp
#include <iostream>
#include <vector>
// 代表图中的一条边,包含起点和终点
struct Edge {
int source;
int destination;
};
// 邻接表表示图的结构
class Graph {
private:
std::vector<std::vector<Edge>> adjList; // 每个节点的邻接列表
int numVertices;
public:
Graph(int vertices) : numVertices(vertices) {
adjList.resize(numVertices);
}
void addEdge(int src, int dest) {
adjList[src].push_back({src, dest}); // 添加边的方向是从src到dest
}
void printEdgesAndDegrees() {
for (int i = 0; i < numVertices; ++i) {
std::cout << "Vertex " << i << ":\n";
for (const Edge &edge : adjList[i]) {
std::cout << "\tOutgoing edge to vertex " << edge.destination << ", with degree: " << adjList[i].size() << '\n';
}
}
}
};
int main() {
int vertices; // 图的顶点数
std::cout << "Enter the number of vertices: ";
std::cin >> vertices;
Graph graph(vertices);
// 你可以在这里添加边到图中
// 示例:
// graph.addEdge(0, 1); // 边从0到1
// graph.addEdge(1, 2); // 边从1到2
// ...
graph.printEdgesAndDegrees(); // 输出各顶点及其出边及其出度
return 0;
}
```
在这个程序中,我们首先创建一个`Graph`类,它维护一个邻接列表,并提供用于添加边和打印出度的方法。在`main()`函数中,用户可以输入顶点数并构造一个图实例,然后根据需要添加边,最后调用`printEdgesAndDegrees()`来显示每个顶点的信息。
阅读全文