数据结构和算法之图

叁歲伎倆 2024-03-31 12:54 156阅读 0赞

## 什么是图 ##

### 定义 ###

包含

*  1. 一组顶点：通常用V(Vertex)表示顶点集合
 *  2. 一组边：通常用E(Edge)表示边的集合

1.  1.  1.  1. 边是顶点对：(v,w)属于E，其中v,w属于V
        2.  2. 有向边<v,w>表示从v指
        3.  3.不考虑重边和自回路

#### **抽象数据类型定义** ####

*  1.类型名称：图(Graph)
 *  2. 数据对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成(可以一条边都没有，但不 能一个顶点都没有)
 *  3. 操作集：对于任意图G属于Graph，以及v属于V，e属于E

1. Graph Create()：建立并返回空图
    2. Graph InsertVertex(Graph G, Vertex v)：将v插入G
    3. Graph InsertEdge(Graph G, Edge e)：将e插入G;
    4. void DFS(Graph G,Vertex v)：从顶点v出发深度优先遍历图G;
    5. void BFS(Graph G,Vertex v)：从顶点v出发宽度优先遍历图G;
    6. void ShortestPath(Graph G,Vertex v,int Dist[])：计算图G中顶点v到任意其他
    顶点的最短距离
    7. void MST(Graph G)：计算图G的最小生成树

#### 常见术语 ####

1.  无向图：无所谓方向的
2.  有向图：在图中，若用箭头标明了边是有方向性(单向或者双向)的，则称这样的图为有向图，否则  
    称为无向图。
3.  权重：边上显示的数字，可以有各种各样的现实意义
4.  网络：有带权重的图

### **邻接矩阵表示法** ###

#### **怎么在程序中表示一个图** ####

![f853d5d06f5361864a8bc4df722ea0ec.png][]

#### 邻接矩阵——有什么好处？ ####

1.  直观、简单、好理解
2.  方便检查任意一对顶点间是否存在边
3.  方便找任一顶点的所有"邻接点"(有边直接相连的顶点)
4.  方便计算任一顶点的"度"(从该点出发的边数为"出度"，指向该点的边数为"入度")有向图的概念

#### 邻接矩阵——有什么不好? ####

1.  浪费空间——存稀疏图(点很多而边很少)有大量无效元素  
    但对稠密图(特别是完全图)还是很合算的
2.  浪费时间——统计稀疏图中一共有多少条边

**无向图**

对应行(或列)非0元素的个数

**有向图**

对应行非0元素的个数是"出度";对应列非0元素的个数是"入度"

### **邻接表表示法** ###

邻接表：G\[N\]为指针数组，对应矩阵每行一个的链表，只存非0元素

![4a64305ac4008666a57d75723bc5efb0.png][]

#### 优点： ####

1.  方便找任一顶点的所有"邻接点"
2.  节约稀疏图的空间  
    需要N个头指针+2E个结点(每个结点至少2个域)
3.  方便计算任一顶点的"度"  
    对无向图：是的  
    对有向边：只能计算"出度";需要构造"逆邻接表"(存指向自己的边)来方便计算"入度"
4.  方便检查任意一对顶点间是否存在边？NO  
    对于网络，结构中要增加权重的域

[f853d5d06f5361864a8bc4df722ea0ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/438f2484441f47ee9dc45943a24f2a4e.png
[4a64305ac4008666a57d75723bc5efb0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/103e51b9c89a4dfa9acbac9fc1342f28.png