大话数据结构--图的存储结构 72图的抽象数据类型 73

发表于

「这是我参与11月更文挑战的第26天，活动详情查看：2021最后一次更文挑战」。

7.2图的抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
markdown复制代码 ADT图(Graph)
 Data
     顶点的有穷非空集合和边的集合。
 Operation
     CreateGraph (*G,V,VR) :按照顶点集V和边弧集VR的定义构造图G。
     DestroyGraph(*G) :图G存在则销毁。
     LocateVex(G,u) :若图G中存在顶点u，则返回图中的位置。
     GetVex (G,v) :返回图G中顶点v的值。
     PutVex (G,v,value) :将图G中顶点v赋值value。
     FirstAdjVex (G,*v) :返回顶点v的一个邻接顶点，若顶点在G中无邻接顶点返回空。
     NextAdjVex (G,v,*w) :返回顶点v相对于顶点w的下一一个邻接顶点，若w是v的最后
                         一个邻接点则返回“空"。
     InsertVex (*G,v) :在图G中增添新顶点V。
     DeleteVex ( *G,v):删除图G中顶点v及其相关的弧。
     InsertArc ( *G,v,w):在图G中增添弧<v,w>,若G是无向图，还需要增添对称弧
                         <w,v>。
     DeleteArc (*G,v,w):在图G中删除弧<v,w>,若G是无向图，则还删除对称弧
     DFSTraverse(G):对围G中进行深度优先遍历，在遍历过程对每个顶点调用。
     HFSTraverse(G) :对图G中进行广度优先遍历，在遍历过程对每个顶点调用。
 endADT
 ​

7.3图的存储结构

7.3.1领接矩阵

图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

1.无向图的邻接矩阵

image-20211117162429916

2.有向图的邻接矩阵

image-20211117173959652

分析1: 有向图的邻接矩阵可能是不对称的。 分析2: 顶点的出度=第i行元素之和 顶点的入度=第列元素之和 顶点的度=第i行元素之和+第j元素之和

3.网(即有权图)的邻接矩阵表示法

image-20211117174436567

代码实现：

用两个数组分别存储顶点表和邻接矩阵

1
2
3
4
5
6
7
8
9
10
arduino复制代码 #define MaxInt 32767    //表示极大值，即∞
 #define MVNum 100   //最大顶点数
 typedef char VerTexType;    //设顶点的数据类型为字符型
 typedef int ArcType;//假设边的权值类型为整型
 ​
 typedef struct{
     VerTexType vexs{MVNum]; //顶点表
     ArcType arcs[MVNum][MVNum];     //邻接矩阵
     int vexnum, arcnum;         //图的当前点数和边数。
 }AMGraph;    // Adjacency Matrix Graph

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%