您的位置:首页 > 健康 > 养生 > 网站建设专家工作内容_网站首页框架图_推广平台软件有哪些_dw友情链接怎么设置

网站建设专家工作内容_网站首页框架图_推广平台软件有哪些_dw友情链接怎么设置

2025/3/15 11:01:43 来源:https://blog.csdn.net/2401_88135404/article/details/146266474  浏览:    关键词:网站建设专家工作内容_网站首页框架图_推广平台软件有哪些_dw友情链接怎么设置
网站建设专家工作内容_网站首页框架图_推广平台软件有哪些_dw友情链接怎么设置

知识总览:

一、图的基本操作

  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)

  3. 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)

  总结:

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com