当前位置：首页 > news >正文

5.数据结构-图

news 来源：原创 2025/9/21 8:21:10

5.数据结构-图

5.1 图的定义和基本术语
- 5.1.1 图的定义
- 5.1.2 图的基本术语
5.2图的存储结构
- 5.2.1邻接矩阵
- - 采用邻接矩阵表示法创建无向网
  - 邻接表

5.1 图的定义和基本术语

5.1.1 图的定义

图 G由两个集合V和E组成，记为 $G = (V, E)$ ，其中V是有顶点的有穷非空集合，E是V中顶点偶对的有穷集合，这些顶点偶对称为边。

对于图G，若边集 $E (G)$ 为有向边的集合，则称该图为有向图；若边集 $E (G)$ 为无向边的集合，则称该图为无向图。

有向图中，顶点对 $< x, y >$ 是有序的，它与 $< y, x >$ 是不同的两条边；在无向图中， $(x, y)$ 与 $(y, x)$ 是同一条边。为了有别于有向图，无向图的顶点用一对括号括起来。
在这里插入图片描述

5.1.2 图的基本术语

用n表示图中的顶点数目，用e表示边的数目。

子图：假设有两个图 $G = (V, E) 和 G^{'} = (V^{'}, E^{'}), 如果$ $\in V 且 E' \in E$ ，则称 $G^{'}$ 为 $G$ 的子图。
在这里插入图片描述
无向完全图和有向完全图：对于无向图，若具有 $n (n - 1) / 2$ 条边，则称为无向完全图。对于有向图。若具有 $n (n - 1)$ 条弧，则称为有向完全图。

稀疏图和稠密图：有多少条边或弧(如 $e<nlog_2n$ )的图称为稀疏图，反之称为稠密图。

权和网：在实际应用中，每条边可以标上具有某种意义的数值，该数值称为该边上的权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。

邻接点：对于无向图G，如果图的边 $v')\in E$ ，则称顶点v和v‘为邻接点，即v和v’相邻接。边 $(v, v^{'})$ 依附于点v和v‘，或者说边边 $(v, v^{'})$ 与顶点v和v’相关联。

度、入度和出度：顶点v的度是指和v相关联的边的数目，记为 $T D (v)$ 。入度是以顶点v为头的弧的数目，记为 $I D (v)$ ；出度是以顶点v为尾的弧的数目，记为 $O D (v)$ 。且 $T D (v) = I D (v) + O D (v)$ 。

回路或环：第一个顶点和最后一个顶点相同的路径称为回路或环

简单路径、简短回路或简单环：序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简短回路或简单环。

连通、连通图和连通分量：无向图中，若从点v到点v’有路径，则称v和v’是连通的。若对图中任意两个顶点 $v_i、v_j\in E$ ， $v_i、v_j$ 都是连通的，则G是连通图。连通分量则是指无向图中的极大连通子图。
在这里插入图片描述

强连通图和强连通分量：在有向图G中，如果对于每一对 $v_i、v_j\in V， v_i !=v_j$ ，从 $v_i$ 到 $v_j$ 和 $v_j$ 到 $v_i$ 都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。

连通图的生成树：一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的 $n - 1$ 条边，这样的连通子图称为连通图的生成树。
一棵有n个顶点的生成树有且仅有 $n - 1$ 条边。如果一个图有n个顶点和小于 $n - 1$ 条边，则是非连通图。如果它多于 $n - 1$ 条边，则一定有环。但是，有 $n - 1$ 条边的图不一定是生成树。在这里插入图片描述

有向树和生成森林：有一个顶点的入度为0，其余顶点的入度均为1 的有向图称为有向树。一个有向图的生成森林是由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。
在这里插入图片描述

5.2图的存储结构

5.2.1邻接矩阵

设 $G (V, E)$ 是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：
$\left\{\begin{matrix} 1 \ \ 若<v_i, v_j>或(v_i, v_j) \in E\\ 0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 反之 \end{matrix}\right.$

若G是网（带权值），则邻接矩阵可以定义为：
$\left\{\begin{matrix} w_{i,j} \ \ 若<v_i, v_j>或(v_i, v_j) \in E\\ \infty \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 反之 \end{matrix}\right.$
在这里插入图片描述

#define MaxInt 32767
#define MVNum 100 using namespace std;typedef char VerTexType;
typedef int ArcType;
typedef struct{VerTexType vexs[MVNum]; //顶点表ArcType arcs[MVNum][MVNum];int vexnum, arcnum; //图的当前点数和边数 
}AMGraphe;

采用邻接矩阵表示法创建无向网

#include <iostream>
#include <vector>
#include <cstring>#define MaxInt 32767
#define MVNum 100 using namespace std;typedef char VerTexType;
typedef int ArcType;
typedef struct{VerTexType vexs[MVNum]; //顶点表ArcType arcs[MVNum][MVNum];int vexnum, arcnum; //图的当前点数和边数 
}AMGraphe;int LocateVex(AMGraphe G, VerTexType v) {for (int i = 0; i < G.vexnum; i++) {if (G.vexs[i] == v) { // 找到匹配的顶点return i;}}return -1; // 未找到返回 -1
}int CreatUDN(AMGraphe &G){cin >> G.vexnum >> G.arcnum; //输入顶点数和边数for(int i = 0; i < G.vexnum; i ++) cin >> G.vexs[i];for(int i = 0; i < G.vexnum; i ++){ //初始化 for(int j = 0; j < G.vexnum; j ++){G.arcs[i][j] = MaxInt;}} for(int k = 0; k < G.arcnum; k ++){int v1, v2, w;cin >> v1 >> v2 >> w;int i = LocateVex(G, v1), j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标 G.arcs[i][j] = w;G.arcs[j][i] = G.arcs[i][j];} return 1;}int main() {return 0;
}

优点：

1.查询高效
判断两点是否相邻的时间复杂度为 O(1)，直接访问 G.arcs[i][j] 即可。
2.适用于稠密图
若图的边数接近顶点数的平方，邻接矩阵能高效存储和查询边信息。
3.便于矩阵运算
适合用矩阵运算（如图的幂运算）来分析路径问题，例如 Floyd 算法求最短路径。
4.易于实现
结构简单，代码实现直观，初始化和操作都比较容易。

缺点：

1.空间消耗大
需要 O(V2) 的存储空间，即使边数很少（稀疏图），仍要存储所有可能的边信息，浪费空间。
2.插入和删除边的效率低
插入边效率高（O(1)），但删除边可能涉及到维护整个矩阵，在某些情况下效率不如邻接表。
3.不适合稀疏图
当边数远小于 V2时，邻接矩阵会有大量的无效存储（0 或 MaxInt）。
4.不易遍历所有邻接点
查找某个顶点的所有邻接点需要遍历整行，时间复杂度 O(V)，而邻接表可以直接访问邻接链表，效率更高。

邻接表

邻接表 是图的一种链式存储结构。在邻接表中，对图的每个顶点 $v_i$ 建立一个单链表，把与 $v_i$ 相邻接的顶点放在这个链表中。可以把这一节点看出链表的表头，其余结点存放有关边的信息，这样邻接表便由两部分组成：表头结点表和边表。

5.数据结构-图

5.1 图的定义和基本术语

5.1.1 图的定义

5.1.2 图的基本术语

5.2图的存储结构

5.2.1邻接矩阵

采用邻接矩阵表示法创建无向网

邻接表

相关文章：