《数据结构》学习系列——图（上）

系列文章目录

目录

图

• 基本概念
• • 图的定义
  • 图的度
  • 图的路径与回路
  • 图的子图
  • 图的联通
  • 权图
• 图的存储结构
• • 邻接矩阵
  • 邻接表
  • • 无向图和有向图的邻接表
    • 逆邻接表
    • 带权的邻接表
  • 邻接矩阵vs.邻接链表
  • 基本操作
  • • 邻接矩阵方法
    • 邻接表存储方法

基本概念

图的定义

• 定义 图G由图G由两个集合V和E组成，记为G=(V，E)；其中v是顶点的有穷非空集合，E是连接v中两个不同顶点的边的有穷集合。通常,也将图G的顶点集和边集分别记为V(G)和E(G)
  • 若图中的边限定为从一个顶点指向另一个顶点,则称此图为有向图
  • 若图中的边无方向性,则称之为无向图
• 定义 若G=(V,E)是有向图，则它的一条有向边是由v中两个顶点构成的有序对，亦称为弧,记为<w,v>，其中w是边的始点，又称弧尾；v是边的终点，又称弧头

有向图示例：

• 由于E是边的集合，故一个图中不会多次出现一条边。若去掉此限制,则由此产生的结构称为多重图
  
  
  
  
  

图的度

• 定义 G是无向图，$v\in V(G)，E(G)$中以v为端点的边的个数,称为顶点的度。若G是有向图，则v的出度是以v为始点的边的个数，v的入度是以v为终点的边的个数
• 有向图中，以某顶点为弧头的弧的数目称为该顶点的入度。以某顶点为弧尾的弧的数目称为该顶点的出度
• 顶点的度 = 入度 + 出度
• 设图G（有向或者无向）共有n各顶点，e条边，若顶点$v_i$的度数为TD($v_i$)则
  $$\sum _{i=1}^{n}TD(v_i)=2e$$
• 因为一条边关联两个顶点，而且使得这两个顶点的度数分别增加1，因此顶点的度数之和就是边的两倍

图的路径与回路

• 设G是图，若存在一个顶点序列$v_p,v_1,v_2,\cdots ,v_{q-1},v_q$使得($v_p,v_1$),($v_1,v_2$),$\cdots$,<$v_{q-1},v_q$>或<$v_p,v_1$>,<$v_1,v_2$>,$\cdots$,<$v_{q-1},v_q$>，属于E(G)，则称$v_p$到$v_q$存在一条路径，其中$v_p$称为起点，$v_q$称为终点
• 路径的长度为该路径上边的个数。如果一条路径上除了起点和终点可以相同外，再不能有相同的顶点,则称此路径为简单路径。如果一条简单路径的起点和终点相同，且路径长度大于等于2，利称之为简单回路

设G = (V,E)是图，u，v属于V，如果从u到v有一条路径，则称u与v是相连的

图的子图

设G，H是图，如果$V(H)\subseteq V(G)$，$E(H)\subseteq E(G)$，则称H是G的子图，G是H的母图。如果H是G的子图，且$V(H)=V(G)$，则称H为G的支撑子图

图的联通

• 设G是图，若存在一条从顶点$v_i$到顶点$v_j$的路径，则称$v_i$与$v_j$可及（联通）

  • 若G为无向图，且V(G)中任意两顶点都可及 ，则称G为连通图
  • 若G为有向图，且对于V(G)中任意两个不同的顶$v_i$和$v_j$可及，$v_j$和$v_i$也可及，则称G为强连通图
  • 也可以定义弱联通图的概念。即在任何顶点u和v之间，至少存在一条u到v或者v到u的路径
    

• 设图 G = (V,E)是无向（或有向）图，若G的子图$G_k$是一个(强)连通图，则称$G_k$为G的**(强)连通图**

• 对于G的一个联通子图$G_k$，如果不存在G的另一个联通子图G`，使得$V(G_k)\subset V(G^{\prime })$，则称$G_k$为G的联通分量
  
  

权图

设G = (V,E)是图，若对图中的任意一条边l，都有实数w（l）与其对应，则称G为权图，记为G=(V,E,w)。记w(u,v)表示w((u,v))或者w(<u,v>)，规定：

• $\forall u\in V,\text{有}w((u,u))=0\text{或}w(⟨u,u⟩)=0$
• $\forall u,v\in V,\text{若}(u,v)\notin E(G)\text{或}⟨u,v⟩\notin E(G),\text{则}w((u,v))=+\infty \text{或}w(⟨u,v⟩)=+\infty$

加权路径

• 若$\sigma =\left(v_0,v_1,\dots ,v_{k-1},v_k\right)$是权图G中的一条路径，则$|\sigma |={\sum }_{i=1}^{k}w(v_{i-1},v_i)$称为加权路径的长度或权重
• 权通常用来表示从一个顶点到另一个顶点的距离或费用

图的存储结构

邻接矩阵

用顺序方式或者链接方式存储图的顶点表$v_0,v_1,\dots ,v_{n-1}$，图的边用n×n阶矩阵$A=(a_{ij})$表示，A的定义如下

• 若图为权图，$a_{ij}$对应边$⟨v_i,v_j⟩$或$(v_i,v_j)$

• 若图为非权图

  • $a_{ii}=0$
  • $a_{ij}=1$，当 $i\ne j$ 且 $⟨v_i,v_j⟩$ 或 $(v_i,v_j)$ 存在时
  • $a_{ij}=0$，当 $i\ne j$ 且 $⟨v_i,v_j⟩$ 或 $(v_i,v_j)$ 不存在时

• 称矩阵A为图的邻阶矩阵
  

特点

• 无向图的邻接矩阵对称,可压缩存储;有n个顶点的无向图所需存储空间为n(n+1)/2
• 有向图的邻接矩阵不一定对称;有n个顶点的有向图所需存储空间为$n^2$
• 借助邻接矩阵，可以很容易第求出图中的顶点的度
  • 无向图：邻接矩阵的第i行(或第i列)的非零元素的个数是顶点$v_i$的度
  • 有向图：邻接矩阵第i行非零元素的个数为顶点$v_i$的出度；第i列非零元素的个数为顶点$v_i$的入度
    

邻接表

定义：邻接表是图的一种链接存储结构。对图的每个顶点建立一个单链表(n个顶点建立n个单链表)，第i个单链表中的结点包含顶点$v_i$；的所有邻接顶点。由顺序存储的顶点表和链接存储的边链表构成的图的存储结构被称为邻接表

• 权图中边结点结构为（VerAdj，cost，link）
  
• 非权图中边结点结构为（VerAdj，link）
  
• 顶点的结构
  

无向图和有向图的邻接表

• 无向图的邻接表
  • 把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做边结点，边结点中保存有与该边相关联的另一顶点的顶点下标VerAdj和指向同一链表中下一个边结点的指针link
    
• 有向图的邻接表
  • 在有向图的邻接表中第i个边链表链接的边都是顶点i发出的边，也叫做边表
    
• 对于用邻接表存储的有向图，每条边只对应一个边结点；而对于用邻接表存储的无向图，每条边则对应两个边结点
• 根据邻接表，可统计出有向图中每个顶点的出度。但是，如果要统计一个顶点的入度，就要遍历所有的边结点，其时间复杂度为O(e)(e为图中边的个数)，从而统计所有顶点入度的时间复杂度为O(ne)(n为图的顶点个数)
• 对有向图建立逆邻接表(顶点的指向关系与邻接表恰好相反)，根
  据逆邻接表，很容易统计出图中每个顶点的入度

逆邻接表

• 在有向图的逆邻接表中，第i个边链表链接的边都是进入顶点i的边，也叫入边表
  

带权的邻接表

• 带权图的边结点中保存该边上的权值cost
• 在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定

• 设图中有n个顶点，e条边，则用邻接表表示无向图时，需要n个顶点结点，2e个边结点；
• 用邻接表表示有向图时，若不考虑逆邻接表，只需n个顶点结点，e个边结点

邻接矩阵vs.邻接链表

• 采用邻接矩阵还是用邻接表来存储图，要视对给定图实施的具体操作而定
• 对于边很多的图(也称稠密图)，适于用邻接矩阵存储，因为占用的空间少
• 而对于顶点多而边少的图(也称稀疏图)，若用邻接矩阵存储，对应的邻接矩阵将是一个稀疏矩阵，存储利用率很低。因此，顶点多而边少的图适于用邻接表存储

基本操作

邻接矩阵方法

用邻接矩阵存储的Graph_Matrix类

const int MaxGraphSize = 256; // 图的最大顶点个数
const int MaxWeight = 1000;   // 图中允许的最大权值

class Graph_Matrix {
private:
    int edge[MaxGraphSize][MaxGraphSize]; // 邻接矩阵
    int graphszie;                        // 当前图中顶点个数

public:
    Graph_Matrix();                      // 构造函数
    int GraphEmpty(void) const;          // 检测图是否为空
    int NumberOfVertices(void) const;    // 返回图的顶点个数
    int NumberOfEdges(void) const;       // 返回图的边个数
    int GetWeight(const int v1, const int v2); // 返回指定边的权值
    int GetFirstNeighbor(const int v);   // 返回序号为v的顶点的第一个邻接顶点的序号
    int GetNextNeighbor(const int v1, const int v2); // 返回序号为v1的顶点相对于序号为v2的顶点的下一个邻接顶点的序号

    // 插入一个顶点
    void InsertVertex(const int v);

    // 插入一条边 (v1, v2)，边权值为weight
    void InsertEdge(const int v1, const int v2, int weight);

    // 在图中删除顶点和所有与它相关联的边
    void DeleteVertex(const int v);

    // 在图中删除边 (v1, v2)
    void DeleteEdge(const int v1, const int v2);
};

构造函数

// Graph_Matrix类的实现
// 构造函数
// 将邻接矩阵的所有元素设为0，并将图的大小设为0。
Graph_Matrix::Graph_Matrix() {
    for (int i = 0; i < MaxGraphSize; i++)
        for (int j = 0; j < MaxGraphSize; j++)
            edge[i][j] = 0;
    graphszie = 0;
}

取得序号为v的顶点的第一个邻接顶点的序号

int Graph_Matrix::GetFirstNeighbor(const int v) {
    if (v != -1) {
        for (int i = 0; i < graphszie; i++) {
            if (edge[v][i] > 0 && edge[v][i] < MaxWeight)
                return i;
        }
    }
    return -1;
}

取得顶点v1相对于v2的下一个邻接顶点的序号

int Graph_Matrix::GetNextNeighbor(const int v1, const int v2) {
    if (v1 != -1 && v2 != -1) {
        for (int i = v2 + 1; i < graphszie; i++) {
            if (edge[v1][i] > 0 && edge[v1][i] < MaxWeight)
                return i;
        }
    }
    return -1;
}

删除顶点Vertex
算法思想：不仅要从顶点链表中删除该顶点，还需要删除该顶点所发出的边以及所有的入边，即在邻接矩阵中删除相应的行和列

邻接表存储方法

用邻接表存储的图类Graph_List

// Graph_List类声明
// 边结点的结构
struct Edge {
    friend class Graph_List;
    int VerAdj;   // 邻接顶点序号
    int cost;     // 边的权值
    Edge* link;   // 指向下一个边结点的指针
};

类声明

// 图的类定义
class Graph_List {
private:
    Vertex* Head;    // 顶点表的头指针
    int graphszie;   // 当前顶点个数

public:
    // 返回序号为v的顶点的第一个邻接顶点的序号
    int GetFirstNeighbor(const int v);

    // 返回序号为v1的顶点相对于序号为v2的顶点的下一个邻接顶点的序号
    int GetNextNeighbor(const int v1, const int v2);

    // 其他成员函数
    // ...
};

求序号为v的顶点的第一个邻接顶点的序号

int Graph_List::GetFirstNeighbor(const int v) {
    if (v != -1) {
        Edge* p = head[v].adjacent;
        if (p != NULL)
            return p->VerAdj;
    }
    return -1;
}

求序号为v1的顶点相对于序号为v2的顶点的下一个邻接顶点的序号

int Graph_List::GetNextNeighbor(const int v1, const int v2) {
    if (v1 != -1 && v2 != -1) {
        Edge* p = head[v1].adjacent;
        while (p != NULL) {
            if (p->VerAdj == v2 && p->link != NULL) // p->link 此时为所求邻接顶点
                return p->link->VerAdj;
            else
                p = p->link;
        }
    }
    return -1;
}