数据结构笔记——图的基本操作

系统管理员 2023-02-17 14:30 35阅读 0赞

**目录**

一、基本操作

1.Adjacent(G,x,y)：判断图G是否存在边或(x,y),y>

2.Neighbors(G,x)：列出图G中与结点x邻接的边

3.InsertVertex(G,x)，在图G中插入顶点x

4.DeleteVertex(G,x)，从图G中删除顶点x

5.AddEdge(G,x,y)：若无向边（x,y）或有向边不存在，则向图G中添加该边,y>

6.RemoveEdge(G,x,y)：若无向边(x,y)或有向边存在，则从图G中删除该边,y>

7.FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号，若x没有邻接点或图中不存在x，则返回-1

8.NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1

9.Get\_edge\_value(G,x,y)：获取图G中边（x,y）或对应的权值,y>

10Set\_edge\_value(G,x,y,v)：获取图G中边(x,y)或对应的权值v,y>

二、总结

## **一、基本操作** ##

### **1.Adjacent(G,x,y)：判断图G是否存在边<x,y>或(x,y)** ###

**无向图**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70][]

邻接矩阵查找时间复杂度：O（1）

邻接表查找时间复杂度：O（1）~O（|V|）

**有向图**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1][]

邻接矩阵查找时间复杂度：O（1）

邻接表查找时间复杂度：O（1）~O（|V|）

### **2.Neighbors(G,x)：列出图G中与结点x邻接的边** ###

**无向图**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70][]

邻接矩阵查找时间复杂度：O（|V|）

邻接表查找时间复杂度：O（1）~O（|V|）

**有向图**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1][]

邻接矩阵查找时间复杂度：O（|V|）

邻接表查找时间复杂度

出边：O（1）~O（|V|）

入边：O（|E|）

### **3.InsertVertex(G,x)，在图G中插入顶点x** ###

**无向图**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2][]

邻接矩阵查找时间复杂度：O（1）

邻接表查找时间复杂度：O（1）

**注：有向图也类似**

### **4.DeleteVertex(G,x)，从图G中删除顶点x** ###

**无向图**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 4][]

邻接矩阵查找时间复杂度：O（|V|）

邻接表查找时间复杂度：O（1）~O（|E|）

**有向图**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 5][]

邻接矩阵查找时间复杂度：O（|V|）

邻接表查找时间复杂度

删出边：O（1）~O（|V|）

删入边：O（|E|）

### **5.AddEdge(G,x,y)：若无向边（x,y）或有向边<x,y>不存在，则向图G中添加该边** ###

**无向图**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 6][]

邻接矩阵查找时间复杂度：O（1）

邻接表查找时间复杂度：O（1）

**注：有向图也类似**

### **6.RemoveEdge(G,x,y)：若无向边(x,y)或有向边<x,y>存在，则从图G中删除该边** ###

**无向图**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 7][]

邻接矩阵查找时间复杂度：O（1）

邻接表查找时间复杂度：O（1）~O（|V|）

**注：有向图也类似**

### **7.FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号，若x没有邻接点或图中不存在x，则返回-1** ###

**无向图**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 8][]

邻接矩阵查找时间复杂度：O（1）~O（|V|）

邻接表查找时间复杂度：O（1）

**有向图**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 9][]

邻接矩阵查找时间复杂度：O（1）~O（|V|）

邻接表查找时间复杂度

找出边邻接点：O（1）

找入边邻接点：O（1）~O（|E|）

### **8.NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 10][]

邻接矩阵查找时间复杂度：O（1）~O（|V|）

邻接表查找时间复杂度：O（1）

### **9.Get\_edge\_value(G,x,y)：获取图G中边（x,y）或<x,y>对应的权值** ###

### **10Set\_edge\_value(G,x,y,v)：获取图G中边(x,y)或<x,y>对应的权值v** ###

## **二、总结** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 11][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200614162739993.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200614162922388.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200614163311806.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200614163433394.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200614163516381.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200614163637214.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/2020061416390483.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/2020061416402524.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200614164309851.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200614164421321.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/2020061416463128.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20200614164822611.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70