运行#include <iostream> #include <vector> using namespace std; class Graph { private: int V; // 图的顶点数 vector<typename vector<int>::vector> adj; // 邻接表存储结构 public: Graph(int V) { this->V = V; adj.resize(V); } void addEdge(int v, int w) { adj[v].push_back(w); adj[w].push_back(v); } void printGraph() { for(int i = 0; i < V; i++) { cout << "顶点 " << i << " 的邻接表: "; for(int j = 0; j < adj[i].size(); j++) { cout << adj[i][j] << " "; } cout << endl; } } };
时间: 2024-01-04 22:02:35 浏览: 31
这是一个图的邻接表存储结构的实现,可以用来表示无向图。其中,类 Graph 有三个成员变量,分别为图的顶点数 V,邻接表 adj,以及构造函数 Graph(int V)。构造函数中会初始化邻接表 adj 的大小为 V,即邻接表中有 V 个元素,每个元素都是一个 vector<int> 类型的向量,用来存储与该顶点相邻的其他顶点编号。addEdge 方法用于添加图的边,其中 v 和 w 分别是边的两个顶点编号,因为是无向图,所以需要把两个顶点互相加入对方的邻接表中。printGraph 方法用于打印整张图的邻接表,依次输出每个顶点的邻接表中存储的相邻顶点编号。
你可以在 main 函数中创建一个 Graph 对象,并调用 addEdge 方法添加边,最后再调用 printGraph 方法打印整张图的邻接表。
相关问题
#include <iostream> #include <vector> using namespace std; class Graph { private: int V; // 图的顶点数 vector<typename vector<int>::vector> adj; // 邻接表存储结构 public: Graph(int V) { this->V = V; adj.resize(V); } void addEdge(int v, int w) { adj[v].push_back(w); adj[w].push_back(v); } void printGraph() { for(int i = 0; i < V; i++) { cout << "顶点 " << i << " 的邻接表: "; for(int j = 0; j < adj[i].size(); j++) { cout << adj[i][j] << " "; } cout << endl; } } };
这是一个 C++ 实现的无向图的邻接表存储结构,包含了以下几个部分:
- 私有成员变量 V 表示图的顶点数,adj 是一个 vector 容器,每个元素都是一个 vector 容器,存储与该顶点相邻的顶点。
- 公有构造函数 Graph(int V) 用于创建一个包含 V 个顶点的图,并初始化邻接表 adj。
- 公有成员函数 addEdge(int v, int w) 用于向图中添加一条从顶点 v 到顶点 w 的边,由于是无向图,所以还需要添加一条从顶点 w 到顶点 v 的边。
- 公有成员函数 printGraph() 用于打印整个图的邻接表,遍历每个顶点的邻接表,输出所有相邻的顶点。
这个实现使用了 vector 容器来存储邻接表,相比于邻接矩阵,邻接表可以节省空间,更适合存储稀疏图。
c++类模板有向图G采用邻接矩阵存储,计算图中出度为零的顶点个数,写一段完整代码,不用#include<vertor>,用tempate<class T>
好的,以下是一段完整的 C++ 代码,用于计算邻接矩阵存储的有向图中出度为零的顶点个数,不使用 vector,只使用类模板和指针:
```c++
#include <iostream>
using namespace std;
template <class T>
class Graph {
public:
Graph(int n) : size(n) {
adj_matrix = new T*[n];
for (int i = 0; i < n; i++) {
adj_matrix[i] = new T[n];
for (int j = 0; j < n; j++) {
adj_matrix[i][j] = 0;
}
}
}
~Graph() {
for (int i = 0; i < size; i++) {
delete[] adj_matrix[i];
}
delete[] adj_matrix;
}
void add_edge(int from, int to, T weight) {
adj_matrix[from][to] = weight;
}
int zero_outdegree_count() const {
int count = 0;
for (int i = 0; i < size; i++) {
bool has_outgoing_edge = false;
for (int j = 0; j < size; j++) {
if (adj_matrix[i][j] != 0) {
has_outgoing_edge = true;
break;
}
}
if (!has_outgoing_edge) {
count++;
}
}
return count;
}
private:
int size;
T** adj_matrix;
};
int main() {
Graph<int> g(5);
g.add_edge(1, 3, 1);
g.add_edge(2, 1, 1);
g.add_edge(2, 4, 1);
g.add_edge(3, 2, 1);
g.add_edge(4, 5, 1);
g.add_edge(5, 2, 1);
int count = g.zero_outdegree_count();
cout << "Number of vertices with zero outdegree: " << count << endl;
return 0;
}
```
这段代码定义了一个 Graph 类模板,用于表示有向图。它使用邻接矩阵来存储图的边。其中,add_edge() 方法用于向图中添加一条从 from 到 to,权值为 weight 的有向边。zero_outdegree_count() 方法用于计算出度为零的顶点个数。在 main() 函数中,我们创建了一个有向图,并计算出度为零的顶点个数。注意,我们使用了 new 和 delete 运算符来动态分配和释放二维数组 adj_matrix。
相关推荐
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)