建立无向图邻接表存储结构,输出深度和宽度优先遍历顶点访问次序。
时间: 2023-04-24 22:07:13 浏览: 166
无向图邻接表存储结构 先深及先广搜索
5星 · 资源好评率100%
建立无向图邻接表存储结构,可以使用链表来表示每个顶点的邻接点。对于每个顶点,我们可以用一个链表来存储它的邻接点,这个链表的头结点就是该顶点本身。
深度优先遍历可以使用递归或者栈来实现。从起始顶点开始,首先访问它的一个邻接点,然后再访问这个邻接点的一个邻接点,以此类推,直到访问完所有的顶点。在访问每个顶点时,我们可以记录下它的访问次序。
宽度优先遍历可以使用队列来实现。从起始顶点开始,首先访问它的所有邻接点,然后再访问这些邻接点的所有邻接点,以此类推,直到访问完所有的顶点。在访问每个顶点时,我们可以记录下它的访问次序。
无论是深度优先遍历还是宽度优先遍历,都需要遍历所有的顶点,因此时间复杂度都是O(V+E),其中V是顶点数,E是边数。
阅读全文