前言

在计算机科学与算法设计中，图是一种极其重要的数据结构，它不仅是学术研究中的核心概念，也是工程实践中解决复杂问题的利器。无论是社交网络的关系分析、地图导航的路径规划，还是网络通信中的路由算法，图结构都扮演着至关重要的角色。
本文将从图的基本概念入手，介绍有向图、无向图的区别，深入探讨两种常用的存储方式——邻接矩阵与邻接表，并结合 C++ 给出详细实现代码，让你在理解原理的同时，也能快速上手编程实践。

1. 图的基本概念

子图：设图G = {V, E}和图G1 = {V1，E1}，若V1属于V且E1属于E，则称G1是G的子图。 

2. 图的存储结构

2.1 邻接矩阵

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <map>
using namespace std;
template<class T, class W, W MAX_W = INT_MAX, bool direction = false>
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<W>(n, MAX_W));
	}
	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<T> _vertexs;//顶点集合
	map<T, size_t> _vertexs_map;//顶点集合映射
	vector<vector<W>> _edges;//存储边集合的矩阵
};
void TestGraph() {
	Graph<char, int, INT_MAX, true> g("0123", 4);
	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<string, int, true> g1(a, 4);
	g1.AddEdge("张三", "李四", 100);
	g1.AddEdge("张三", "王五", 200);
	g1.AddEdge("王五", "赵六", 30);
	g1.Print();
}
int main() {
	TestGraph();
	return 0;
}

 

2.2 邻接表

 

2. 有向图邻接表存储 

 

• 邻接表数据结构：

  • 使用 unordered_map<string, vector<string>> 存储，string 表示顶点名（可改为 int）。

  • vector<string> 存储与该顶点相连的所有邻居。

• 有向/无向模式：

  • 构造函数接收 bool directed 参数。

  • 若 directed = false，addEdge(u, v) 时同时加 v->u 和 u->v。

  • 若 directed = true，只加 u->v。

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_set>

using namespace std;

class Graph {
private:
    unordered_map<string, vector<string>> adjList; // 邻接表
    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<string> visited;
        stack<string> st;
        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<string> visited;
        queue<string> q;
        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

结束语

图论是算法世界的一座桥梁，它连接着数学的抽象之美与程序设计的实用之道。邻接矩阵与邻接表作为两种经典的图存储方式，各有优劣，选择哪一种取决于具体的应用场景。
掌握了图的存储结构，你就能更高效地实现遍历、最短路径、连通性分析等算法，从而在更广泛的领域中游刃有余。希望本文不仅能帮助你打下图论的基础，也能为你后续深入学习各种图算法奠定坚实的地基。