数据结构笔记——图的基本操作
目录
1.Adjacent(G,x,y)：判断图G是否存在边或(x,y),y>
2.Neighbors(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)
无向图
邻接矩阵查找时间复杂度：O（1）
邻接表查找时间复杂度：O（1）~O（|V|）
有向图
邻接矩阵查找时间复杂度：O（1）
邻接表查找时间复杂度：O（1）~O（|V|）
2.Neighbors(G,x)：列出图G中与结点x邻接的边
无向图
邻接矩阵查找时间复杂度：O（|V|）
邻接表查找时间复杂度：O（1）~O（|V|）
有向图
邻接矩阵查找时间复杂度：O（|V|）
邻接表查找时间复杂度
出边：O（1）~O（|V|）
入边：O（|E|）
3.InsertVertex(G,x)，在图G中插入顶点x
无向图
邻接矩阵查找时间复杂度：O（1）
邻接表查找时间复杂度：O（1）
注：有向图也类似
4.DeleteVertex(G,x)，从图G中删除顶点x
无向图
邻接矩阵查找时间复杂度：O（|V|）
邻接表查找时间复杂度：O（1）~O（|E|）
有向图
邻接矩阵查找时间复杂度：O（|V|）
邻接表查找时间复杂度
删出边：O（1）~O（|V|）
删入边：O（|E|）
5.AddEdge(G,x,y)：若无向边（x,y）或有向边<x,y>不存在，则向图G中添加该边
无向图
邻接矩阵查找时间复杂度：O（1）
邻接表查找时间复杂度：O（1）
注：有向图也类似
6.RemoveEdge(G,x,y)：若无向边(x,y)或有向边<x,y>存在，则从图G中删除该边
无向图
邻接矩阵查找时间复杂度：O（1）
邻接表查找时间复杂度：O（1）~O（|V|）
注：有向图也类似
7.FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号，若x没有邻接点或图中不存在x，则返回-1
无向图
邻接矩阵查找时间复杂度：O（1）~O（|V|）
邻接表查找时间复杂度：O（1）
有向图
邻接矩阵查找时间复杂度：O（1）~O（|V|）
邻接表查找时间复杂度
找出边邻接点：O（1）
找入边邻接点：O（1）~O（|E|）
8.NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1
邻接矩阵查找时间复杂度：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
二、总结