数据结构-图的基本操作
数据结构–图的基本操作
知识总览：
一、图的基本操作
1.Adjacent(G,x,y)，判断图G是否有边—对于有向图和无向图来说，邻间接矩阵的时复杂度更低。
邻接矩阵时间复杂度 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)
- InsertVertex(G,x): 在图G中插入顶点x。
邻接矩阵时间复杂度 O(1) 邻接表时间复杂度 O(1)
在初始化邻接矩阵时，就应当将每个没有相连的顶点设置为0，因此时间复杂度为1.
在邻接表中也是类似的
4.DeleteVertex(G,x):从图G中删除顶点x。
对于无向图：
在邻接矩阵中，删除一个顶点时，将其相连的所有顶点的值设置为0，再设置一个bool类型变量，用于表示该表点是否为空。 时间复杂度为O（v）.
在邻接表中，删除一个顶点，需要删除自己的所有链表外，还需遍历所有顶点的链表，将含有这个顶点的链表中删除。时间复杂度为O(1)~~~O(E)–所有顶点都与该顶点相连。
对于有向图：
在邻接矩阵中，与无向图一样。
在邻接表中，只删除出边，将顶点整个边删除即可，时间复杂度为O(1)~~~O(V)
删除入边，需要遍历整个边链表，时间复杂度为O(E)
5.AddEdge(G,x,y):若无向边（x，y）或有向边（x,y）不存在，则在图G中添加该边。
无向图：邻接矩阵时间复杂度为O(1).
邻接表时间复杂度为O(1)–采用头插法
对于有向图也是类似的
6.FirstNeighbor(G,x):求图G中顶点x的第一个临界点，若有则返回顶点号，若x没有邻接点或图中不存在x，则返回-1.
无向图：邻接矩阵：从左到右进行扫描 发现第一个1返回即可。时间复杂度为O(1)~~O(V)
邻接表：只需要找链表的第一个元素即可 时间复杂度为O(1).
有向图：对于邻接矩阵 出边则扫描行 入边则扫面列。时间复杂度为O(1)~~O(v)
对于邻接表，出边为O(1), 入边时间复杂度为O(1)~~O(E)
7.NextNeighbor(G,x,y):假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
无向图：邻接矩阵直接继续向后扫描即可，时间复杂度为：O(1)~~O(V)
邻接表只需要再向后找一位即可，时间复杂度为：O(1）
8.Get edge_value(G,x,y):获取图G中边(x,y)或<x,y>对应的权值。
Set_edge_value(G,x,y,v):设置图G中边(x,y)或<x,y>对应的权值为v。
与判断图G是否存在边类似，邻接矩阵时间复杂度 O(1) 邻接表时间复杂度 O(1)~~O(v)
总结：
