前言
在计算机科学与算法设计中，图是一种极其重要的数据结构，它不仅是学术研究中的核心概念，也是工程实践中解决复杂问题的利器。无论是社交网络的关系分析、地图导航的路径规划，还是网络通信中的路由算法，图结构都扮演着至关重要的角色。
本文将从图的基本概念入手，介绍有向图、无向图的区别，深入探讨两种常用的存储方式——邻接矩阵与邻接表，并结合 C++ 给出详细实现代码，让你在理解原理的同时，也能快速上手编程实践。
1. 图的基本概念 图是由顶点集合及顶点间的关系组成的一种数据结构：G = (V， E)，其中：
顶点集合V = {x|x属于某个数据对象集}是有穷非空集合；
E = {(x,y)|x,y属于V}或者E = {
做边的集合。
(x, y)表示x到y的一条双向通路，即(x, y)是无方向的；Path(x, y)表示从x到y的一条单向通路，即
Path(x, y)是有方向的。
顶点和边：图中结点称为顶点，第i个顶点记作vi。两个顶点vi和vj相关联称作顶点vi和顶点vj之间
有一条边，图中的第k条边记作ek，ek = (vi，vj)或
有向图和无向图：在有向图中，顶点对
边(弧)，
是无序的，顶点对(x,y)称为顶点x和顶点y相关联的一条边，这条边没有特定方向，(x, y)和(y，x)
是同一条边，比如下图G1和G2为无向图。注意：无向边(x, y)等于有向边
完全图：在有n个顶点的无向图中，若有n * (n-1)/2条边，即任意两个顶点之间有且仅有一条边，
则称此图为无向完全图，比如上图G1；在n个顶点的有向图中，若有n * (n-1)条边，即任意两个
顶点之间有且仅有方向相反的边，则称此图为有向完全图，比如上图G4。
邻接顶点：在无向图中G中，若(u, v)是E(G)中的一条边，则称u和v互为邻接顶点，并称边(u,v)依
附于顶点u和v；在有向图G中，若
点u，并称边
顶点的度：顶点v的度是指与它相关联的边的条数，记作deg(v)。在有向图中，顶点的度等于该顶
点的入度与出度之和，其中顶点v的入度是以v为终点的有向边的条数，记作indev(v);顶点v的出度
是以v为起始点的有向边的条数，记作outdev(v)。因此：dev(v) = indev(v) + outdev(v)。注意：对于无向图，顶点的度等于该顶点的入度和出度，即dev(v) = indev(v) = outdev(v)。
路径：在图G = (V， E)中，若从顶点vi出发有一组边使其可到达顶点vj，则称顶点vi到顶点vj的顶
点序列为从顶点vi到顶点vj的路径。
路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一
条路径的路径长度是指该路径上各个边权值的总和。
简单路径与回路：若路径上各顶点v1，v2，v3，…，vm均不重复，则称这样的路径为简单路
径。若路径上第一个顶点v1和最后一个顶点vm重合，则称这样的路径为回路或环。
子图：设图G = {V, E}和图G1 = {V1，E1}，若V1属于V且E1属于E，则称G1是G的子图。
连通图：在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与顶点v2是连通的。如果图中任
意一对顶点都是连通的，则称此图为连通图。
强连通图：在有向图中，若在每一对顶点vi和vj之间都存在一条从vi到vj的路径，也存在一条从vj
到vi的路径，则称此图是强连通图。
生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点
和n-1条边。
2. 图的存储结构 因为图中既有节点，又有边(节点与节点之间的关系)，因此，在图的存储中，只需要保存：节点和
边关系即可。节点保存比较简单，只需要一段连续空间即可，那边关系该怎么保存呢？
2.1 邻接矩阵 因为节点与节点之间的关系就是连通与否，即为0或者1，因此邻接矩阵(二维数组)即是：先用一
个数组将定点保存，然后采用矩阵来表示节点与节点之间的关系。
注意：
1. 无向图的邻接矩阵是对称的，第i行(列)元素之和，就是顶点i的度。有向图的邻接矩阵则不一
定是对称的，第i行(列)元素之后就是顶点i 的出(入)度。
2. 如果边带有权值，并且两个节点之间是连通的，上图中的边的关系就用权值代替，如果两个
顶点不通，则使用无穷大代替。
3. 用邻接矩阵存储图的有点是能够快速知道两个顶点是否连通，缺陷是如果顶点比较多，边比
较少时，矩阵中存储了大量的0成为系数矩阵，比较浪费空间，并且要求两个节点之间的路径不是很好求。
代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
using namespace std;
template
class Graph {
public:
Graph() = default;
Graph(const T* vertexs, size_t n) {
_vertexs.reserve(n);
for (size_t i = 0; i < n; ++i) {
_vertexs.push_back(vertexs[i]);
_vertexs_map[vertexs[i]] = i;
}
//MAX_W=INT_MAX作为边的默认值
_edges.resize(n, vector
}
size_t GetvertesIndex(const T& v) {
auto ret = _vertexs_map.find(v);
if (ret != _vertexs_map.end()) {
return ret->second;
}
else
throw runtime_error("vertex not found");
return -1;
}
void _AddEdge(size_t srci, size_t desti, const W& w) {
_edges[srci][desti] = w;
if (direction == false) {
_edges[desti][srci] = w;
}
}
void AddEdge(const T& src, const T& dest, const W& w) {
size_t srci = GetvertesIndex(src);
size_t desti = GetvertesIndex(dest);
_AddEdge(srci, desti, w);
}
void Print() {
//打印顶点和下标映射
for (size_t i = 0; i < _vertexs.size(); i++) {
cout << _vertexs[i] << "-" << i << endl;
}
//打印横标
cout << " ";
for (size_t i = 0; i < _vertexs.size(); i++)
printf("%4d ", i);
cout << endl;
//打印矩阵
for (size_t i = 0; i < _edges.size(); i++) {
cout << i << " ";//竖标
for (size_t j = 0; j < _edges[i].size(); j++) {
if (_edges[i][j] == MAX_W) {
if (i == j) {
printf("%4d ", 0);
}
else
printf("%4c ", '*');
}
else {
printf("%4d ", _edges[i][j]);
}
}
cout << endl;
}
cout << endl;
for (size_t i = 0; i < _edges.size(); ++i)
{
for (size_t j = 0; j < _edges[i].size(); ++j)
{
if ( _edges[i][j] != MAX_W)
{
cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _edges[i][j] << endl;
}
}
}
}
private:
vector
map
vector
};
void TestGraph() {
Graph
g.AddEdge('0', '1', 1);
g.AddEdge('0', '3', 4);
g.AddEdge('1', '3', 2);
g.AddEdge('1', '2', 9);
g.AddEdge('2', '3', 8);
g.AddEdge('2', '1', 5);
g.AddEdge('2', '0', 3);
g.AddEdge('3', '2', 6);
g.Print();
}
void TestGraph1()
{
string a[] = { "张三", "李四", "王五", "赵六" };
Graph
g1.AddEdge("张三", "李四", 100);
g1.AddEdge("张三", "王五", 200);
g1.AddEdge("王五", "赵六", 30);
g1.Print();
}
int main() {
TestGraph();
return 0;
}2.2 邻接表 邻接表：使用数组表示顶点的集合，使用链表表示边的关系。
1. 无向图邻接表存储
注意：无向图中同一条边在邻接表中出现了两次。如果想知道顶点vi的度，只需要知道顶点
vi边链表集合中结点的数目即可。
2. 有向图邻接表存储
注意：有向图中每条边在邻接表中只出现一次，与顶点vi对应的邻接表所含结点的个数，就
是该顶点的出度，也称出度表，要得到vi顶点的入度，必须检测其他所有顶点对应的边链
表，看有多少边顶点的dst取值是i。
邻接表数据结构：
使用 unordered_map
vector
有向/无向模式：
构造函数接收 bool directed 参数。
若 directed = false，addEdge(u, v) 时同时加 v->u 和 u->v。
若 directed = true，只加 u->v。
代码语言：javascript复制#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
class Graph {
private:
unordered_map
bool directed; // 是否有向
public:
// 构造函数
Graph(bool isDirected = false) {
directed = isDirected;
}
// 添加顶点
void addVertex(const string& vertex) {
if (adjList.find(vertex) == adjList.end()) {
adjList[vertex] = {};
}
}
// 添加边
void addEdge(const string& src, const string& dest) {
addVertex(src);
addVertex(dest);
adjList[src].push_back(dest);
if (!directed) {
adjList[dest].push_back(src);
}
}
// 删除边
void removeEdge(const string& src, const string& dest) {
if (adjList.find(src) != adjList.end()) {
auto& vec = adjList[src];
vec.erase(remove(vec.begin(), vec.end(), dest), vec.end());
}
if (!directed && adjList.find(dest) != adjList.end()) {
auto& vec = adjList[dest];
vec.erase(remove(vec.begin(), vec.end(), src), vec.end());
}
}
// 删除顶点
void removeVertex(const string& vertex) {
adjList.erase(vertex);
for (auto& pair : adjList) {
auto& vec = pair.second;
vec.erase(remove(vec.begin(), vec.end(), vertex), vec.end());
}
}
// 打印邻接表
void printGraph() {
for (const auto& pair : adjList) {
cout << pair.first << " -> ";
for (const auto& neighbor : pair.second) {
cout << neighbor << " ";
}
cout << endl;
}
}
// 深度优先搜索 (DFS)
void DFS(const string& start) {
unordered_set
stack
st.push(start);
cout << "DFS from " << start << ": ";
while (!st.empty()) {
string vertex = st.top();
st.pop();
if (visited.find(vertex) == visited.end()) {
cout << vertex << " ";
visited.insert(vertex);
for (auto it = adjList[vertex].rbegin(); it != adjList[vertex].rend(); ++it) {
if (visited.find(*it) == visited.end()) {
st.push(*it);
}
}
}
}
cout << endl;
}
// 广度优先搜索 (BFS)
void BFS(const string& start) {
unordered_set
queue
q.push(start);
visited.insert(start);
cout << "BFS from " << start << ": ";
while (!q.empty()) {
string vertex = q.front();
q.pop();
cout << vertex << " ";
for (const auto& neighbor : adjList[vertex]) {
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
q.push(neighbor);
}
}
}
cout << endl;
}
};
// 测试代码
int main() {
cout << "=== 无向图示例 ===" << endl;
Graph g1(false); // 无向图
g1.addEdge("A", "B");
g1.addEdge("A", "C");
g1.addEdge("B", "D");
g1.addEdge("C", "E");
g1.printGraph();
g1.DFS("A");
g1.BFS("A");
cout << "\n=== 有向图示例 ===" << endl;
Graph g2(true); // 有向图
g2.addEdge("A", "B");
g2.addEdge("A", "C");
g2.addEdge("B", "D");
g2.addEdge("C", "E");
g2.printGraph();
g2.DFS("A");
g2.BFS("A");
return 0;
} === 无向图示例 ===
E -> C
B -> A D
D -> B
C -> A E
A -> B C
DFS from A: A B D C E
BFS from A: A B C D E
=== 有向图示例 ===
E ->
B -> D
D ->
C -> E
A -> B C
DFS from A: A B D C E
BFS from A: A B C D E
结束语 图论是算法世界的一座桥梁，它连接着数学的抽象之美与程序设计的实用之道。邻接矩阵与邻接表作为两种经典的图存储方式，各有优劣，选择哪一种取决于具体的应用场景。
掌握了图的存储结构，你就能更高效地实现遍历、最短路径、连通性分析等算法，从而在更广泛的领域中游刃有余。希望本文不仅能帮助你打下图论的基础，也能为你后续深入学习各种图算法奠定坚实的地基。