图数据结构详解：概念、实现与应用
图是计算机科学中最强大、最灵活的数据结构之一，它能够表示各种复杂的关系和网络。从社交网络到地图导航，从网页链接到电路设计，图无处不在。本教程将深入探讨图的基本概念、实现方法和常见应用，并提供详细的C/C++代码示例。
目录
1. 图的基本概念
1.1 什么是图
图(Graph)是一种非线性数据结构，由顶点(Vertex)和边(Edge)组成。直观地说，图是由点和连接这些点的线组成的。在数学上，图通常表示为G = (V, E)，其中V是顶点集合，E是边集合。
图可以用来表示各种现实世界中的关系：
- 社交网络中的人际关系
- 城市之间的道路连接
- 计算机网络中的连接关系
- 分子结构中的原子连接
- 任务之间的依赖关系
1.2 图的术语
在深入了解图之前，我们需要熟悉一些基本术语：
- 顶点(Vertex)：图中的节点或点，通常用来表示实体。
- 边(Edge)：连接两个顶点的线，表示顶点之间的关系。
- 邻接(Adjacent)：如果两个顶点之间有一条边直接连接，则称这两个顶点是邻接的。
- 路径(Path)：从一个顶点到另一个顶点的顶点序列，其中相邻顶点之间有边相连。
- 环(Cycle)：起点和终点相同的路径。
- 度(Degree)：与某个顶点相连的边的数量。在有向图中，分为入度(In-degree)和出度(Out-degree)。
- 连通图(Connected Graph)：任意两个顶点之间都存在路径的图。
- 连通分量(Connected Component)：图中的最大连通子图。
1.3 图的分类
图可以根据不同的特性进行分类：
1.3.1 按边的方向分类
- 无向图(Undirected Graph)：边没有方向，表示双向关系。例如，朋友关系通常是双向的。
- 有向图(Directed Graph)：边有方向，表示单向关系。例如，网页之间的链接通常是单向的。
1.3.2 按边的权重分类
- 无权图(Unweighted Graph)：边没有权重，只表示连接关系。
- 带权图(Weighted Graph)：边有权重，表示连接的某种度量（如距离、成本等）。
1.3.3 其他分类
- 完全图(Complete Graph)：任意两个顶点之间都有边相连的图。
- 二分图(Bipartite Graph)：顶点可以分为两个不相交的集合，使得每条边的两个端点分别属于这两个集合。
- 树(Tree)：无环连通图，任意两个顶点之间有且仅有一条路径。
- 森林(Forest)：由多棵树组成的图。
- 平面图(Planar Graph)：可以在平面上画出而不让任何边相交的图。
2. 图的表示方法
在计算机中表示图有多种方法，每种方法都有其优缺点。选择哪种表示方法取决于图的特性和需要执行的操作。
2.1 邻接矩阵
邻接矩阵是表示图的最直观方法之一。对于有n个顶点的图，我们使用一个n×n的矩阵，其中矩阵的元素M[i][j]表示从顶点i到顶点j的边。
- 对于无权图，M[i][j] = 1表示存在边，M[i][j] = 0表示不存在边。
- 对于带权图，M[i][j]表示边的权重，通常用一个特殊值（如无穷大）表示不存在边。
下面是一个无向图的邻接矩阵表示示例：
对于有向图，邻接矩阵可能不是对称的：
邻接矩阵的C++实现
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
int V; // 顶点数
vector<vector<int>> adjMatrix; // 邻接矩阵
public:
// 构造函数
Graph(int vertices) {
this->V = vertices;
// 初始化邻接矩阵，所有元素设为0
adjMatrix.resize(V, vector<int>(V, 0));
}
// 添加边（无向图）
void addEdge(int u, int v, int weight = 1) {
// 确保顶点有效
if (u >= 0 && u < V && v >= 0 && v < V) {
adjMatrix[u][v] = weight;
adjMatrix[v][u] = weight; // 对于无向图，矩阵是对称的
}
}
// 添加边（有向图）
void addDirectedEdge(int u, int v, int weight = 1) {
// 确保顶点有效
if (u >= 0 && u < V && v >= 0 && v < V) {
adjMatrix[u][v] = weight;
}
}
// 移除边
void removeEdge(int u, int v) {
// 确保顶点有效
if (u >= 0 && u < V && v >= 0 && v < V) {
adjMatrix[u][v] = 0;
adjMatrix[v][u] = 0; // 对于无向图
}
}
// 检查边是否存在
bool isEdge(int u, int v) {
// 确保顶点有效
if (u >= 0 && u < V && v >= 0 && v < V) {
return adjMatrix[u][v] != 0;
}
return false;
}
// 获取边的权重
int getWeight(int u, int v) {
// 确保顶点有效
if (u >= 0 && u < V && v >= 0 && v < V) {
return adjMatrix[u][v];
}
return 0; // 或者返回一个表示无效的值
}
// 打印邻接矩阵
void printMatrix() {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
}
};
// 使用示例
int main() {
// 创建一个有5个顶点的图
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);
// 打印邻接矩阵
cout << "邻接矩阵表示：" << endl;
g.printMatrix();
return 0;
}
邻接矩阵的优缺点
优点：
- 实现简单直观
- 检查两个顶点之间是否有边的时间复杂度为O(1)
- 适合表示稠密图（边数接近顶点数的平方）
- 方便进行矩阵运算（如求最短路径的Floyd算法）
缺点：
- 空间复杂度为O(V²)，对于大型稀疏图会浪费大量空间
- 添加或删除顶点的操作复杂度高，需要重新调整整个矩阵
- 遍历所有边的时间复杂度为O(V²)，对于稀疏图效率低
2.2 邻接表
邻接表是另一种常用的图表示方法，特别适合表示稀疏图。对于每个顶点，我们维护一个列表，存储与该顶点相邻的所有顶点。
下面是一个无向图的邻接表表示示例：
对于有向图，邻接表只存储出边：
对于带权图，我们可以在邻接表中存储边的权重：
邻接表的C++实现
#include <iostream>
#include <vector>
#include <list>
using namespace std;
// 用于存储边信息的结构体（用于带权图）
struct Edge {
int dest; // 目标顶点
int weight; // 边的权重
Edge(int d, int w) : dest(d), weight(w) {
}
};
class Graph {
private:
int V; // 顶点数
vector<list<Edge>> adjList; // 邻接表
public:
// 构造函数
Graph(int vertices) {
this->V = vertices;
adjList.resize(V);
}
// 添加边（无向图）
void addEdge(int u, int v, int weight = 1) {
// 确保顶点有效
if (u >= 0 && u < V && v >= 0 && v < V) {
adjList[u].push_back(Edge(v, weight));
adjList[v].push_back(Edge(u, weight)); // 对于无向图，添加反向边
}
}
// 添加边（有向图）
void addDirectedEdge(int u, int v, int weight = 1) {
// 确保顶点有效
if (u >= 0 && u < V && v >= 0 && v < V) {
adjList[u].push_back(Edge(v, weight));
}
}
// 移除边
void removeEdge(int u, int v) {
// 确保顶点有效
if (u >= 0 && u < V && v >= 0 && v < V) {
// 移除u到v的边
adjList[u].remove_if([v](const Edge& e) {
return e.dest == v; });
// 对于无向图，还需要移除v到u的边
adjList[v].remove_if([u](const Edge& e) {
return e.dest == u; });
}
}
// 检查边是否存在
bool isEdge(int u, int v) {
// 确保顶点有效
if (u >= 0 && u < V && v >= 0 && v < V) {
for (const Edge& e : adjList[u]) {
if (e.dest == v) {
return true;
}
}
}
return false;
}
// 获取边的权重
int getWeight(int u, int v) {
// 确保顶点有效
if (u >= 0 && u < V && v >= 0 && v < V) {
for (const Edge& e : adjList[u]) {
if (e.dest == v) {
return e.weight;
}
}
}
return 0; // 或者返回一个表示无效的值
}
// 打印邻接表
void printList() {
for (int i = 0; i < V; i++) {
cout << "顶点 " << i << " 的邻接点: ";
for (const Edge& e : adjList[i]) {
cout << "(" << e.dest << ", 权重:" << e.weight << ") ";
}
cout << endl;
}
}
};
// 使用示例
int main() {
// 创建一个有5个顶点的图
Graph g(5);
// 添加边
g.addEdge(0, 1, 2);
g.addEdge(0, 4, 5);
g.addEdge(1, 2, 3);
g.addEdge(1, 3, 1);
g.addEdge(1, 4, 4);
g.addEdge(2, 3, 6);
g.addEdge(3, 4, 7);
// 打印邻接表
cout << "邻接表表示：" << endl;
g.printList();
return 0;
}
邻接表的优缺点
优点：
- 空间效率高，特别是对于稀疏图
- 遍历所有边的时间复杂度为O(V+E)
- 添加顶点操作简单，只需添加一个新的列表
- 适合进行图的遍历操作
缺点：
- 检查两个顶点之间是否有边的时间复杂度为O(degree)，最坏情况下为O(V)
- 删除边的操作较复杂
- 不如邻接矩阵直观
2.3 其他表示方法
除了邻接矩阵和邻接表，还有其他一些表示图的方法：
2.3.1 边列表
边列表是最简单的图表示方法之一，它直接存储所有的边。每条边由起点、终点和权重（如果有）组成。
#include <iostream>
#include <vector>
using namespace std;
// 边结构体
struct Edge {
int src; // 源顶点
int dest; // 目标顶点
int weight; // 边的权重
Edge(int s, int d, int w) : src(s), dest(d), weight(w) {
}
};
class Graph {
private:
int V; // 顶点数
vector<Edge> edges; // 边列表
public:
// 构造函数
Graph(int vertices) {
this->V = vertices;
}
// 添加边
void addEdge(int u, int v, int weight = 1) {
edges.push_back(Edge(
最低0.47元/天 解锁文章
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
