有向图：
1. **定义**：有向图是一种图，其中边是有方向的。每条边连接两个顶点，其中一个是起点，另一个是终点。在有向图中，从一个顶点到另一个顶点的边具有方向，因此不能双向移动。
2. **特性**：
- 边是有方向的，从一个顶点到另一个顶点有一定的方向性。
- 有向图中的边可以用箭头表示，箭头指向终点。
- 有向图中可能存在环，即顶点之间形成循环路径。
- 有向图的度可以分为入度和出度，入度是指指向该顶点的边的数量，出度是指从该顶点出发的边的数量。
3. **表示方法**：
- 邻接表：对于每个顶点，存储其指向的其他顶点列表。
- 邻接矩阵：用二维数组表示顶点之间的连接关系，其中1表示有边相连，0表示没有边相连。
4. **应用场景**：
- 网络路由：路由器之间的连接可以用有向图表示，每个路由器是一个顶点，路由器之间的连接是有向边。
- 社交网络：用户之间的关注关系可以用有向图表示，每个用户是一个顶点，关注关系是有向边。
- 流程图：流程中的各个步骤之间的顺序关系可以用有向图表示，每个步骤是一个顶点，步骤之间的执行顺序是有向边。
有向图在各种领域都有广泛的应用，用于建模和解决各种问题。
- 有向图的邻接表表示
#include <iostream>
#include <vector>
#include <list>
using namespace std;
// 有向图的邻接表表示
class Graph {
private:
int V; // 顶点数
vector<list<int>> adjList; // 邻接表
public:
// 在构造函数中对类的成员变量进行初始化,过 : V(vertices) 这样的语法，将参数 vertices 的值赋给了类成员变量 V
Graph(int vertices) : V(vertices) {
adjList.resize(V);
}
// 添加边
void addEdge(int src, int dest) {
adjList[src].push_back(dest);
}
// 打印图
void printGraph() {
for (int i = 0; i < V; ++i) {
cout << "顶点" << i << "邻接点: ";
for (auto it = adjList[i].begin(); it != adjList[i].end(); ++it) {
cout << *it << " ";
}
cout << endl;
}
}
};
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, 1);
g.printGraph();
return 0;
}
- 有向图的邻接矩阵表示
#include <iostream>
#include <vector>
using namespace std;
// 有向图的邻接矩阵表示
class Graph {
private:
int V; // 顶点数
vector<vector<int>> adjMatrix; adjMatrix：表示邻接矩阵的整数二维向量。
public:
Graph(int vertices) : V(vertices) {
adjMatrix.resize(V, vector<int>(V, 0)); // 初始化为0
}
// 添加边
void addEdge(int src, int dest) {
adjMatrix[src][dest] = 1;
}
// 打印图
void printGraph() {
for (int i = 0; i < V; ++i) {
cout << "顶点 " << i << " 的邻接顶点: ";
for (int j = 0; j < V; ++j) {
if (adjMatrix[i][j] == 1) {
cout << j << " ";
}
}
cout << endl;
}
}
// 打印邻接矩阵
void printAdjMatrix() {
cout << "邻接矩阵：" << endl;
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
}
};
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, 1);
g.printGraph();
g.printAdjMatrix();
return 0;
}
// Graph 类：
// Graph 类使用邻接矩阵表示有向图。
// 私有成员：
// V：表示图中顶点数的整数。
// adjMatrix：表示邻接矩阵的整数二维向量。
// 公有方法：
// 构造函数：构造函数以顶点数为参数，并初始化邻接矩阵，将所有元素设置为 0。
// addEdge：通过将邻接矩阵中相应元素设置为 1，从顶点 src 添加到顶点 dest 的有向边。
// printGraph：打印图的邻接表表示，显示顶点及其相邻顶点。
// printAdjMatrix：打印图的邻接矩阵表示。 // 邻接表表示
vector<vector<int>> adjList;
// 邻接矩阵表示
vector<vector<int>> adjMatrix;
// 使用邻接表和邻接矩阵表示有向图的C++代码
#include <iostream>
#include <vector>
using namespace std;
// 打印图的邻接矩阵表示的函数
void printAdjMatrix(const vector<vector<int>>& adjMatrix) {
for (const auto& row : adjMatrix) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
}
// 表示边的结构体
struct Edge {
int src, dest;
};
class Graph {
public:
// 初始化有向图的构造函数
Graph(const vector<Edge>& edges, int N) : adjList(N), adjMatrix(N, vector<int>(N, 0)) {
// 向有向图中添加边
for (const auto& edge : edges) {
adjList[edge.src].push_back(edge.dest);
adjMatrix[edge.src][edge.dest] = 1;
}
}
// 打印图的邻接表表示的函数
void printAdjList() {
for (size_t i = 0; i < adjList.size(); ++i) {
cout << "顶点 " << i << " 连接到:";
for (const auto& v : adjList[i]) {
cout << " -> " << v;
}
cout << endl;
}
}
// 打印图的邻接矩阵表示的函数
void printAdjMatrix() {
for (const auto& row : adjMatrix) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
}
private:
// 邻接表表示
vector<vector<int>> adjList;
// 邻接矩阵表示
vector<vector<int>> adjMatrix;
};
int main() {
// 有向图中的边列表
vector<Edge> edges = {{0, 1}, {1, 2}, {2, 0}, {2, 1}, {3, 2}, {4, 5}, {5, 4}};
// 有向图中的顶点数量
int N = 6;
// 构造有向图
Graph graph(edges, N);
// 打印有向图的邻接表表示
cout << "邻接表:" << endl;
graph.printAdjList();
// 打印有向图的邻接矩阵表示
cout << "\n邻接矩阵:" << endl;
graph.printAdjMatrix();
return 0;
}
------------
在 C++ 中，std::vector<std::vector<int>> 是一个非常灵活和强大的数据结构，它实质上表示一个动态的二维数组或表格。这种数据结构是由标准模板库（STL）中的 std::vector 容器嵌套构成的，每个内部 vector 可以独立地改变大小，这提供了很多传统静态二维数组所不具备的特性和优势。下面是 std::vector<std::vector<int>> 能表示的一些主要内容：
1. 不规则的二维数组
不同于传统的二维数组必须有固定的行和列大小，std::vector<std::vector<int>> 允许每一行的长度可以不同，这使得它可以用来表示不规则的数据结构，如三角形或其他更复杂的结构。
2. 动态大小的表格
因为 std::vector 的大小是可以动态改变的，所以使用 std::vector<std::vector<int>> 可以在运行时添加或删除行和列，适合于数据量未知或需要动态调整大小的情况。
3. 易于扩展的数据集
此结构非常适合处理数据集，特别是当你不确定数据集的维度或在程序运行时可能需要扩展数据集的情况。它为添加、删除和修改数据提供了便捷的方式。
4. 表格或矩阵操作
在需要执行表格或矩阵运算（如数学计算、统计分析）的应用中，std::vector<std::vector<int>> 可以用来存储矩阵数据，并进行动态的行列操作。但需要注意的是，对于复杂的数学运算，可能需要实现或使用额外的库来处理矩阵运算。
5. 图的邻接矩阵
在图论中，邻接矩阵是表示图的顶点如何连接的一种方式。使用 std::vector<std::vector<int>>，可以灵活地表示和修改图的结构，尤其是对于动态变化的图结构。
6. 作为数据容器
这种数据结构可以用来存储任何需要二维数组形式的数据，如游戏棋盘、电子表格数据、图像数据等。
7. 数据库结果集
在从数据库查询返回的数据经常是表格式的，std::vector<std::vector<int>> 可以用来存储查询结果，尤其是当结果集的大小不是事先知道的时候。
总之，std::vector<std::vector<int>> 提供了很高的灵活性和动态性，使得它在很多需要使用表格、矩阵或其他形式的二维数据集的应用场景中非常有用。然而，需要注意的是，与单一的 std::vector 相比，嵌套的 vector 在内存使用和管理上可能更复杂，也可能影响性能，特别是在大规模数据处理时。
