在计算机科学中，图是一种非线性数据结构，它表示对象之间的关系，例如通信网络的连接、社交网络中人与人之间的联系，或者是地图上的路径和地标。
图由顶点（或称为节点）和边组成。边连接着两个顶点，表示它们之间的关系。图可以是无向的，这意味着边没有方向，例如社交网络中的朋友关系；也可以是有向的，这意味着边有方向，例如地图上的导航路径。此外，图还可以是加权的，其中每条边都有一个与之相关的数值（权重），表示某种度量或成本。
在C++中，我们可以使用邻接矩阵或邻接表来表示图。邻接矩阵使用二维数组来存储节点之间的连接关系，而邻接表则使用链表或向量来存储每个节点的邻居节点。
下面是一个简单的示例，使用邻接矩阵表示无向图，代码如下。
#include <iostream>
#include <vector>
using namespace std;
class Graph {
int V; // 顶点数量
vector<vector<int>> adj; // 邻接矩阵
public:
Graph(int V); // 构造函数
void addEdge(int v, int w); // 添加边
void printGraph(); // 打印图
};
Graph::Graph(int V) {
this->V = V;
adj.resize(V, vector<int>(V, 0));
}
void Graph::addEdge(int v, int w) {
adj[v][w] = 1;
adj[w][v] = 1; // 对于无向图
}
void Graph::printGraph() {
for (int v = 0; v < V; v++) {
for (int w = 0; w < V; w++) {
cout << adj[v][w] << " ";
}
cout << endl;
}
}
int main() {
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.printGraph();
return 0;
}结果如下图所示。
在上面例子中，`Graph`类有一个整数成员变量`V`，表示图中的顶点数，以及一个二维向量`adj`，作为邻接矩阵。`addEdge`函数用于添加边，`printGraph`函数用于打印图。我们已经在构造函数中初始化了顶点数量，并实现了添加边的功能。如果要添加顶点，我们通常需要重新调整邻接矩阵或邻接表的大小，并可能需要重新初始化新的顶点。
图在许多领域都有广泛的应用，如社交网络分析、网络路由、路径规划等。
实例一：最短路径问题，最短路径问题是图论中的一个经典问题，它要求找到从一个节点到另一个节点的最短路径。Dijkstra算法是解决最短路径问题的常用方法之一。下面是一个使用Dijkstra算法求解最短路径的C++示例代码。
#include <iostream>
#include <vector>
#include <limits>
#include <queue>
#include <utility>
using namespace std;
void dijkstra(vector<vector<pair<int, int>>>& graph, int src, vector<int>& dist) {
int V = graph.size();
dist.assign(V, numeric_limits<int>::max());
dist[src] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, src});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (auto& edge : graph[u]) {
int v = edge.first;
int weight = edge.second;
if (dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
}
int main() {
vector<vector<pair<int, int>>> graph = {
{{1, 4}, {2, 8}},
{{0, 4}, {3, 7}},
{{0, 8}, {1, 11}, {3, 2}},
{{1, 7}, {2, 2}}
};
int src = 0; // 源节点
vector<int> dist;
dijkstra(graph, src, dist);
cout << "最短路径长度为: ";
for (int i = 0; i < graph.size(); i++) {
cout << dist[i] << " ";
}
cout << endl;
return 0;
}假设源节点为0，输出结果如下图所示。
在这个示例中，我们使用一个二维向量`graph`来表示图的邻接表。`graph[i]`存储节点`i`的所有邻居节点和对应的权重。我们使用优先队列（最小堆）来按距离值从小到大选择节点，并使用`dist`向量来存储从源节点到每个节点的最短距离。最后，我们输出从源节点到每个节点的最短路径长度，即从源节点0到其他节点的最短路径长度分别为0、4、12和6。
实例二：拓扑排序：拓扑排序是对有向无环图（DAG）的顶点进行排序，使得对每一条有向边(u, v)，均有u（在排序记录中）比v先出现。拓扑排序常用于任务调度、课程安排等场景。下面是使用Kahn算法进行拓扑排序的C++示例代码。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void topologicalSort(vector<vector<int>>& graph) {
int V = graph.size();
vector<int> inDegree(V, 0);
queue<int> q;
// 计算每个节点的入度
for (int i = 0; i < V; i++) {for (int j = 0; j < graph[i].size(); j++) {
inDegree[graph[i][j]]++;
}
}
// 将入度为0的节点加入队列
for (int i = 0; i < V; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
// 拓扑排序
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
for (int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
inDegree[v]--;
if (inDegree[v] == 0) {
q.push(v);
}
}
}
}
int main() {
vector<vector<int>> graph = {
{2, 3, 4},
{3},
{3},
{4},
{}
};
cout << "拓扑排序结果为: ";
topologicalSort(graph);
cout << endl;
return 0;
}拓扑排序结果如下图所示。
在这个示例中，我们使用一个二维向量`graph`来表示有向图的邻接表。`graph[i]`存储节点`i`的所有出边指向的节点。我们首先计算每个节点的入度，并将入度为0的节点加入队列。然后，我们从队列中取出节点，并输出它，同时将其所有邻居节点的入度减1。如果邻居节点的入度变为0，则将其加入队列。最后，我们得到一个有向无环图的拓扑排序结果。 这个排序结果表示了节点之间的先后关系，可以应用于任务调度等场景。例如，如果每个节点代表一个任务，有向边代表任务之间的依赖关系，则拓扑排序结果可以告诉我们任务的执行顺序。
这两个实例展示了图数据结构在实际问题中的应用，通过编写适当的算法，我们可以利用图解决诸如最短路径、拓扑排序等问题。希望这些例子能够帮助你更好地理解C++中图数据结构的应用。
