[数据结构#2] 图(1) | 概念 | 邻接矩阵 | 邻接表 | 模拟

图是由顶点集合及顶点间的关系（边）组成的数据结构，可用$G=(V,E)$表示，其中：

• 顶点集合$V$: V = { x ∣ x ∈ 某数据对象集 } V=\{x|x\in\text{某数据对象集}\} V={x∣x∈某数据对象集}，为有限非空集合；
• 边集合$E$: $E=\{(x,y)|x,y\in V\}$或$E=\{⟨x,y⟩|x,y\in V\}$，表示顶点间的关系。

顶点和边：

• 顶点$x$代表数据元素，第$i$个顶点记作$v_i$；
• 边$e_k$连接两个顶点，记作$e_k=(v_i,v_j)$或$⟨v_i,v_j⟩$。

**分类：有向图与无向图**

• 有向图：边有方向，$⟨x,y⟩\ne ⟨y,x⟩$。
• 无向图：边无方向，$(x,y)=(y,x)$。

**树与图的关系**

• 树是图的一个特殊形式：无环连通图
• 树的特点：
  • 更关注顶点间的结构关系。
  • 二叉搜索树、AVL树等属于存储型数据结构。
• 图的特点：
  • 表示顶点间的关系（如权值）。
  • 可以用于更广泛的场景，如城市地图、社交网络。

常见应用：

1. 社交网络：
   • 无向图：如微信好友关系。
   • 有向图：如微博关注关系。

下面的图，顶点可能表示城市，边表示城市之间一个关系（高铁距离、高铁价格、高铁时间。。。）

有了这个东西，提出DFS，BFS遍历，最小生成树（最小代价把图连图），最短路径(一个顶点到其他顶点 或者 多个顶点之间 最短路径)的问题。

完全图

完全图是指任意两个顶点之间都有边相连的图。具体来说：

• 在有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>是E(G)中的一条边，则称顶点u邻接到v，而顶点v邻接自顶点u，并称边<u, v>与顶点u和顶点v相关联。

顶点的度

顶点v的度定义为与它相关联的边的数量，记作deg(v)。对于有向图：

• 顶点v的入度是以v为终点的有向边的数量，记作indev(v)；
• 顶点v的出度是以v为起点的有向边的数量，记作outdev(v)。
  因此，在有向图中，顶点v的总度等于其入度加出度：dev(v) = indev(v) + outdev(v)。
• 对于无向图，顶点的度等于该顶点的入度和出度之和，即dev(v) = indev(v) = outdev(v)。
• 类似于树节点的度：子树的个数

路径

在图G = (V， E)中，从顶点vi出发通过一系列边可以到达顶点vj，则称从vi到vj的顶点序列为一条路径。

路径长度

• 对于不带权的图，路径长度指的是路径上的边的数量；
• 对于带权的图，路径长度是指路径上所有边的权值总和。

简单路径与回路

• 如果路径上的所有顶点v1，v2，v3，…，vm都是唯一的，则这样的路径称为简单路径；
• 若路径的 起始顶点v1和结束顶点vm相同，则这样的路径称为回路或环。

子图

如果一个图G1的所有顶点V1属于另一个图G的顶点集V，且G1的所有边E1也属于G的边集E，则称G1是G的一个子图。

连通图

连通图特指无向图，其中任意一对顶点间都存在至少一条路径。如果一个无向图中的任何一对顶点都可以相互到达，则该图被称为连通图。

强连通图

强连通图是对有向图而言的，指在一个有向图中，对于每一对顶点vi和vj，既存在从vi到vj的路径，也存在从vj到vi的路径。此时称此图为强连通图。

生成树

生成树是一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边

2. 图的存储结构

**存储要素**

1. 保存顶点信息；
2. 保存顶点间的关系（边）。

//V 顶点类型,  W 权值类型, Direction  表示有向/无向
template<class V,class W,bool Direction>
class Graph
{

private:
	vector<V> _vertexs;//顶点集合
	map<V, int> _IndexMap;//顶点与下标映射
};

**2.1 邻接矩阵**

使用二维数组存储顶点关系：

1. 顶点编号后用下标表示，如 $a,b,c,d\to 0,1,2,3$；
2. 矩阵值：
   • 若无权图：边对应 $1$ 或 $0$；
   • 若加权图：用权值替代；若无连接，标记为 $\infty$。

无权图：

加权图：

特点：

• 优点：
  • 易于判断两顶点是否连通，$O(1)$；
  • 快速获取边权值。
  • 邻接矩阵存储方式非常适合稠密图
• 缺点：
  • 稀疏图存储低效，存在大量 $0$。
  • 查找一个顶点的所有邻接点需遍历 $O(N)$。

假设有n个顶点，是不是要所有顶点遍历一遍才知道某个顶点到底和那些顶点相连。
时间复杂度是O(N)，N是顶点个数。

假设有100个顶点，我这个顶点只和三个顶点相连只有三条边，但也要遍历100次，能不能有个方法快速把与之相连的三条边都找到呢?

**2.2 邻接表**

将图表示为顶点数组和链表结合的结构：

• 顶点数组：保存所有顶点；
• 边链表：存储某顶点的邻接点及边权值。

邻接表和哈希桶类似。使用一个指针数组，把自己和连接的顶点边都挂在下面。

注意：

• 无向图：同一边在邻接表中存储两次；
• 有向图：边存储一次，出边表表示出度。

无向图邻接表存储

注意：无向图中同一条边在邻接表中出现了两次。如果想知道顶点vi的度，只需要知道顶点vi边链表集合中结点的数目即可。

有向图邻接表存储

注意：有向图中每条边在邻接表中只出现一次，与顶点vi对应的邻接表所含结点的个数，就是该顶点的出度，也称出度表，要得到vi顶点的入度，必须检测其他所有顶点对应的边链表，看有多少边顶点的dst取值是i。

一般情况下有向图，存储一个出边表即可。

特点：

• 优点：
  • 适合稀疏图；
  • 易于查找某顶点的出边；
• 缺点：
  • 判断两顶点是否连通效率低。
    总结一下：邻接矩阵和邻接表其实属于相辅相成，各有优缺点的互补结构。具体还是看场景选择用邻接矩阵和邻接表

图的实现与操作

1. 邻接矩阵实现

**概念简介**

邻接矩阵是一种用于表示图的数据结构。通过一个二维数组来记录顶点间的边关系，可用于无向图和有向图。每个矩阵元素的值代表了边的权重。

**模板设计**

template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph {
private:
    vector<V> _vertexs;        // 顶点集合
    map<V, int> _IndexMap;     // 顶点到下标的映射
    vector<vector<W>> _matrix; // 邻接矩阵

• V: 顶点类型（如int, char）
• W: 权值类型（如int, double）
• MAX_W: 默认最大权值（用来表示不存在的边）
• Direction: 是否为有向图（默认无向）

**图的创建**

可以通过以下几种方式创建图：

1. IO输入（适用于在线评测环境）
2. 文件读取
3. 手动添加边

针对手动添加边的方式：

Graph(const V* a, size_t n) {
    _vertexs.reserve(n);
    for (size_t i = 0; i < n; ++i) {
        _vertexs.push_back(a[i]);
        _IndexMap[a[i]] = i;
    }

    _matrix.resize(n, vector<W>(n, MAX_W));
}

• 初始化顶点集合与邻接矩阵。
• 所有边初始权值为MAX_W（表示“无边”）。

**边的操作**

• 获取顶点下标

size_t GetVertexindex(const V& v) {
    auto it = _IndexMap.find(v);
    if (it != _IndexMap.end()) {
        return it->second;
    } else {
        throw invalid_argument("不存在的顶点");
    }
}

• 添加边

void _AddEdge(const size_t& srci, const size_t& dsti, const W& w) {
    _matrix[srci][dsti] = w;
    if (!Direction) { // 无向图
        _matrix[dsti][srci] = w;
    }
}

void AddEdge(const V& src, const V& dst, const W& w) {
    size_t srci = GetVertexindex(src);
    size_t dsti = GetVertexindex(dst);
    _AddEdge(srci, dsti, w);
}

• 根据图的有向性决定边的存储方向。

**打印图**

void Print() {
    // 打印顶点
    for (size_t i = 0; i < _vertexs.size(); ++i) {
        cout << "[" << i << "] -> " << _vertexs[i] << endl;
    }
    cout << endl;

    // 打印邻接矩阵
    for (size_t i = 0; i < _matrix.size(); ++i) {
        cout << i << " ";
        for (size_t j = 0; j < _matrix[i].size(); ++j) {
            if (_matrix[i][j] == MAX_W) {
                printf("%4c", '*');
            } else {
                printf("%4d", _matrix[i][j]);
            }
        }
        cout << endl;
    }
    cout << endl;
}

2. 邻接表实现

邻接表是一种用来表示稀疏图的数据结构，使用一个数组结合链表的方式存储。适合存储有大量顶点，但边相对较少的图。

**定义边结构**

template<class W>
struct Edge {
    size_t _srci, _dsti; // 起始点和目标点的下标
    W _w;                // 权值
    Edge<W>* _next;

    Edge(const size_t& srci, const size_t& dsti, const W& w) 
        : _srci(srci), _dsti(dsti), _w(w), _next(nullptr) {}
};

**图类设计**

template<class V, class W, bool Direction = false>
class Graph {
    typedef Edge<W> Edge;
private:
    vector<V> _vertexs;        // 顶点集合
    map<V, int> _IndexMap;     // 顶点到下标映射
    vector<Edge*> _tables;     // 邻接表

**图的创建**

Graph(const V* a, size_t n) {
    _vertexs.reserve(n);
    for (size_t i = 0; i < n; ++i) {
        _vertexs.push_back(a[i]);
        _IndexMap[a[i]] = i;
    }
    _tables.resize(n, nullptr);
}

• 和邻接矩阵一样，初始化顶点集合。

**边的操作**

• 添加边

void _AddEdge(const size_t& srci, const size_t& dsti, const W& w) {
    Edge* edge = new Edge(srci, dsti, w);
    edge->_next = _tables[srci];
    _tables[srci] = edge;
    if (!Direction) { // 无向图
        Edge* new_edge = new Edge(dsti, srci, w);
        new_edge->_next = _tables[dsti];
        _tables[dsti] = new_edge;
    }
}

void AddEdge(const V& src, const V& dst, const W& w) {
    size_t srci = GetVertexindex(src);
    size_t dsti = GetVertexindex(dst);
    _AddEdge(srci, dsti, w);
}

• 获取顶点下标 跟邻接矩阵相同。

**打印图**

void Print() {
    for (size_t i = 0; i < _vertexs.size(); ++i) {
        cout << "[" << i << "] -> " << _vertexs[i] << endl;
    }
    cout << endl;

    for (size_t i = 0; i < _tables.size(); ++i) {
        cout << _vertexs[i] << "[" << i << "] ->";
        Edge* cur = _tables[i];
        while (cur) {
            cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "] ->";
            cur = cur->_next;
        }
        cout << "nullptr" << endl;
    }
    cout << endl;
}

sum：

• 邻接矩阵：适合稠密图，快速判断连通性。
• 邻接表：适合稀疏图，快速找到某顶点的所有出边。