《数据结构与算法》——图的基本概念、存储方式及基本操作总结

向右看齐 2024-04-18 15:46 12阅读 0赞

# 《数据结构与算法》——图的基本概念、存储方式及基本操作 总结 #

emmm，今天本来只准备做一道算法题的，可是发现它的解题思路是利用图的遍历算法，所以我就开始复习图的遍历算法，刚把基本思想写出来，准备用代码实现却发现，我对图的结构一无所知，所以我又来了复习图的基本概念。?

**目录**

《数据结构与算法》——图的基本概念、存储方式及基本操作 总结

定义

图的存储结构

1. 邻接矩阵法

2. 邻接表法

3. 十字链表法（有向图）

4. 邻接多重表法（无向图）

图的基本操作

总结

参考文献

--------------------

## 定义 ##

首先咱先来几个概念。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0t3emM0_size_16_color_FFFFFF_t_70][]

## 图的存储结构 ##

书上给了四种存储方式，分别为：邻接矩阵法、邻接表法、十字链表法、邻接多重表法。

### **1.** **邻接矩阵法** ###

这种存储结构还是比较亲民（好理解）的，矩阵大家都知道是什么样的，对于每个点来讲它需要两个坐标轴来确定其位置(x,y)，而在这个位置上也可以存储数值，即x点到y点是否有边（/弧）存在，例如：（1，2）0代表1到2没有边/弧，（3，4）1代表3到4有边/弧。

定义如下：

#define MaxVertexNum 100
    typedef char VertexType;//点类型
    typedef int EdgeType;//边类型
    typedef struct{
            VertexType Vex[MaxVertexNum];
            EdgeType Edge[MaxVertexNum][MaxVertexNum];
            int vexnum,arcnum;//记录边数和点数
    }Magraph;

**注意：**

①空间复杂度为n平方，n为顶点数|V|；

②无向图邻接矩阵一定是一个唯一的对称矩阵，实际存储时只需要存储上三角或下三角。

③无向图的邻接矩阵任意一行/列，所有非0非无穷元素的和即为该点的度；

④有向图的邻接矩阵任意一行/列，所有非0非无穷元素的和即为该点的出度/入度；

⑤局限性：无法快速计算该图有多少条边；对于每个顶点的邻接点的个数的查找需要遍历该行/列，即时间为o(n)；

⑥设G的邻接矩阵为A，则A(上角标n)的元素A\[i\]\[j\] (上角标n)代表顶点i到顶点j的长度为n的路径的数目。

### **2.** **邻接表法** ###

当一个图为稀疏图时，使用n\*n的空间存储其邻接表显然比较浪费空间。而当前这种存储方法采取了顺序存储和链式存储相结合的方式，大大减少了不必要的浪费。

邻接表法简单来讲，首先见一个顺序表，将所有的顶点存至其中**（顶点表）**。而对于每个顶点A来讲采用链表结点的方式进行存储，将next指针指向其相邻接点a1→a2→a3…，这个单链表称为该顶点的**边表**（对于有向图则称为**出边表**）。故在此种存储方式中存在两种结点，一种是顶点表结点，一种是边表结点。

<table> 
 <tbody> 
  <tr> 
   <td> 
    <table style="margin-left:7.5pt;"> 
     <tbody> 
      <tr> 
       <td colspan="2" style="vertical-align:top;"> <p style="margin-left:0cm;">顶点表</p> </td> 
      </tr> 
      <tr> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">data</p> </td> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">firstarc</p> </td> 
      </tr> 
     </tbody> 
    </table><p style="margin-left:0cm;">&nbsp;</p> </td> 
   <td> 
    <table> 
     <tbody> 
      <tr> 
       <td colspan="2" style="vertical-align:top;"> <p style="margin-left:0cm;">边点表</p> </td> 
      </tr> 
      <tr> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">adjvex</p> </td> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">nextarc</p> </td> 
      </tr> 
     </tbody> 
    </table><p style="margin-left:0cm;">&nbsp;</p> </td> 
  </tr> 
 </tbody> 
</table>

定义如下:

typedef struct ArcNode{//边表结点 
    	int adjvex;
    	struct ArcNode *next;
    	int vexnum,arcnum;//记录边数和点数 
    	//InfoType info;  //网的边权值 
    }ArcNode;
    
    typedef struct VNode{//顶点表结点 
    	VertexType Vex[MaxVertexNum];
    	struct ArcNode *first;
    }VNode,AdjList[MaxVertexNum];
    
    typedef struct{//图 
    	AdjList vertices;
    	int vexnum,arcnum;//记录边数和点数 
    }ALgraph;

**说明:**

①对于邻接表法存储结构的定义，可以从整体到部分去理解，整体是一张图（ALgraph），然后要定义顶点结点表（VNode,AdjList\[MaxVertexNum\]），最后对于每个顶点来讲，它后面紧接的是边表结点（ArcNode）。

②对于无向图，所需要的存储空间是o（|V|+2|E|），因为每条边出现了两次；

对于有向图，所需要的存储空间是o（|V|+|E|）。

③优点：对于每个顶点，可以很快找出他的所有邻边，比邻接矩阵快；计算出度，只需遍历该结点的链表即可；

④局限性：判断两点之间是否有边需要对该结点的边结点表进行遍历，比邻接矩阵慢；计算入度需要遍历整个图；因为邻接结点的插入顺序不唯一，所以邻接表不唯一。

### **3.** **十字链表法（有向图）** ###

在总结这个方法之前我先表个态，从名字看来，这个算法相当的\*\*，\*\*\*，\*\*\*，\*\*\*\*\*\*。（粗鄙之语）

到现在为止，前面复习了两种存储结构，这两种存储结构均是基于点点关系进行存储的，如：邻接矩阵中（v,w）位置存储0或1，邻接表法中的ALgraph（图）→VNode（顶点）→ArcNode（边表结点，**当然它也可以被看作为是省略了起点的边结点**）。而十字链表的存储基础则与其不同，它是基于**点弧关系**进行存储的。

图→顶点→弧。

<table> 
 <tbody> 
  <tr> 
   <td> 
    <table style="margin-left:7.5pt;"> 
     <tbody> 
      <tr> 
       <td colspan="5" style="vertical-align:top;"> <p style="margin-left:0cm;">弧结点</p> </td> 
      </tr> 
      <tr> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">tailvex</p> </td> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">headvex</p> </td> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">hlink</p> </td> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">tlink</p> </td> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">info</p> </td> 
      </tr> 
     </tbody> 
    </table><p style="margin-left:0cm;">&nbsp;</p> </td> 
   <td> 
    <table> 
     <tbody> 
      <tr> 
       <td colspan="3" style="vertical-align:top;"> <p style="margin-left:0cm;">顶点结点</p> </td> 
      </tr> 
      <tr> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">data</p> </td> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">firstin</p> </td> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">firstout</p> </td> 
      </tr> 
     </tbody> 
    </table><p style="margin-left:0cm;">&nbsp;</p> </td> 
  </tr> 
 </tbody> 
</table>

其中tailvex和 headvex两个指针分别指向一个弧的首尾结点；

hlink 和tlink两个指针分别指向具有相同弧头结点和相同弧尾结点的弧。

info是隐藏参数，可以存储网的弧权值。

firstin和firstout分别指向第一条入弧和第一条出弧。

结构定义如下：

typedef struct ArcNode{//边表结点 
    	int tailvex,headvex;//两个指针分别指向一个弧的首尾结点
    	struct ArcNode *hlink,*tlink;//两个指针分别指向具有相同弧头结点和相同弧尾结点的弧
    	//InfoType info;  //网的边权值 
    }ArcNode;
    
    typedef struct VNode{//顶点表结点 
    	VertexType data;//顶点信息 
    	struct ArcNode *firstin,*firstout;//指向第一个出入弧 
    }VNode,AdjList[MaxVertexNum];
    
    typedef struct{//图 
    	AdjList xlist; //邻接表 
    	int vexnum,arcnum;//记录边数和点数 
    }GLgraph;

**注意：**

①从上文来看此种存储方法理解起来并不是太复杂，但如果手动演示时，可能会因为位置等问题出错，其原因应归结于对于概念的不清晰。

②一个图可以有很多的十字链表，**但一个十字链表只能确定一张唯一的图。**

### **4.** **邻接多重表法（无向图）** ###

态度同上。（连续写了一天，我要把粗鄙之语重复好几遍。?没事，还能学~）

和十字链表类似，这种存储方式是以**点边关系**进行存储的。

先放出邻接多重表的结构示意图：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <table style="margin-left:7.5pt;"> 
     <tbody> 
      <tr> 
       <td colspan="6" style="vertical-align:top;"> <p style="margin-left:0cm;">边结点</p> </td> 
      </tr> 
      <tr> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">mark</p> </td> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">ivex</p> </td> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">ilink</p> </td> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">jvex</p> </td> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">jlink</p> </td> 
       <td style="vertical-align:top;"> <p style="margin-left:0cm;">info</p> </td> 
      </tr> 
     </tbody> 
    </table><p style="margin-left:0cm;">&nbsp;</p> </td> 
   <td> 
    <table> 
     <tbody> 
      <tr> 
       <td colspan="2"> <p style="margin-left:0cm;">顶点结点</p> </td> 
      </tr> 
      <tr> 
       <td> <p style="margin-left:0cm;">data</p> </td> 
       <td> <p style="margin-left:0cm;">firstedgc</p> </td> 
      </tr> 
     </tbody> 
    </table><p style="margin-left:0cm;">&nbsp;</p> </td> 
  </tr> 
 </tbody> 
</table>

参数说明：

mark：标志域，用于标记该条边是否被搜索过；

ivex、jvex为该边依附的两个顶点在图中的位置；

ilink和jlink分别指向下一条分别依附于ivex和jvex的边；

info为隐藏信息域：指向和边相关的各种信息的指针域；

data用于存储该点的值；

firstedgc用于指向第一条依附于该点的边。

定义如下：

/*邻接多重表法*/
    typedef struct ArcNode{//边表结点 
    	bool mark;//标记是否被访问过 
    	int ivex,jvex;//两个指针分别指向一个边的两个结点
    	struct ArcNode *ilink,*jlink;//两个指针分别指向具有相同结点的边 
    	//InfoType info;  //网的边权值 
    }ArcNode;
    
    typedef struct VNode{//顶点表结点 
    	VertexType data;//顶点信息 
    	struct ArcNode *firstarc;//指向第一个依附于此点边 
    }VNode,AdjList[MaxVertexNum];
    
    typedef struct{//图 
    	AdjList xlist; //邻接表 
    	int vexnum,arcnum;//记录边数和点数 
    }AMLgraph;

理解方式同上。

**说明：**

①每个边结点只设一个，即在存储中不会出现两个相同的边结点。

**总结：**

<table> 
 <tbody> 
  <tr> 
   <td style="vertical-align:top;width:113.15pt;"> <p style="margin-left:0cm;">图的存储</p> </td> 
   <td style="vertical-align:top;width:301.65pt;"> <p style="margin-left:0cm;">特点</p> </td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:113.15pt;"> <p style="margin-left:0cm;">邻接矩阵法</p> </td> 
   <td style="vertical-align:top;width:301.65pt;"> <p style="margin-left:0cm;">一个结构，矩阵存储。（x,y）data</p> </td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:113.15pt;"> <p style="margin-left:0cm;">邻接表法</p> </td> 
   <td style="vertical-align:top;width:301.65pt;"> <p style="margin-left:0cm;">三个结构，顺序+链式存储。图-顶点结点-边表结点</p> </td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:113.15pt;"> <p style="margin-left:0cm;">十字链表法</p> </td> 
   <td style="vertical-align:top;width:301.65pt;"> <p style="margin-left:0cm;">仅限<strong>有向图</strong>。三个结构，顺序+链式存储。图-顶点结点-弧结点</p> </td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:113.15pt;"> <p style="margin-left:0cm;">邻接多重表法</p> </td> 
   <td style="vertical-align:top;width:301.65pt;"> <p style="margin-left:0cm;">仅限<strong>无向图</strong>。三个结构，顺序+链式存储。图-顶点结点-边结点</p> </td> 
  </tr> 
 </tbody> 
</table>

## 图的基本操作 ##

Adjacent(G,x,y);//判断图G中是否存在弧<x,y>或边(x,y)。
    Neighbors(G,x);//列出图G中与结点x邻接的边。
    InsertVertex(G,x);//在图G中插入结点x。
    DeleteVertex(G,x);//在图G中删除结点x。
    AddEdge(G,x,y);//如果图G中不存在弧<x,y>或边(x,y)，则插入之。
    RemoveEdge(G,x,y); //如果图G中存在弧<x,y>或边(x,y)，则删除之。
    FirstNeighbor(G,x);//求图G中结点x的第一个邻接点，若有则返回顶点号，若不存在邻接点或者不存在点x，则返回-1。
    NextNeighbor(G,x);//在图G中假设顶点y是顶点x的一个临接点，返回除y之外下一个邻接点，若y是最后一个邻接点，则返回-1。
    Get_edge_value(G,x,y);//获取图G中弧<x,y>或边(x,y)的权值。
    Get_edge_value(G,x,y,v);//设置图G中弧<x,y>或边(x,y)的权值为v。
    /*暂未进行实现*/

## 总结 ##

1.去年复习图这一块是感觉很复杂，因为对于图的存储结构不清晰，对于结点、边结点、弧结点、结点结点（顶点结点）概念的混乱。

2.对于图的方法，去年让自己感到迷茫的是参数，因为不知道不知道参数是什么类型的，因为图中的参数类型很复杂，结点的data不一定是整数，还有可能是字符、字符串等，所以在方法说明的时候并没有进行声明变量类型。

3.因为考纲中对于图这部分的要求不是太高，所以就没对方法进行实现。

## 参考文献 ##

王道论坛 2019年数据结构考研复习指导\[M\]. 北京： 电子工业出版社，2018.

**如有错误，还请朋友不吝指正。**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0t3emM0_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/cdae513a48ff4488b6381aae6af6df18.jpg