图数据结构问题

我在为这些问题设计伪代码时遇到了问题。这不是一个作业问题。我只知道它们与GRAPH数据结构有关。

描述一个计算n顶点m条边的无向图G的所有连通分量的O(n+m)-time算法。

(我猜这与遍历广度优先搜索(BFS)有关，但如果我错了，请纠正我。

Input Graph G
Output sequence of connected vertices with edges
List = empty list
for all u in G.vertices
    setLabel(u, UNEXPLORED)
for all e in G.edges
    setLabel(e, UNEXPLORED)
For all v in G.vertices
    if getLabel(v) = UNEXPLORED
        BFS (G,v,List)
BFS(G,s,List)
Object A = vertex1, vertex2, edge
L0 = new empty sequence
L0.addLast(s)
setLabel(s,VISITED)
i=0
while Li is not Empty
    L(i+1) = new empty sequence
    for all v in L(i).elements
        for all incidentEdges(v)
            if getLabel(e) = UNEXPLORED
                w = opposite(v,e)
                if getLabel(w) = UNEXPLORED
                    setLabel(e,DISCOVERY)
                    setLabel(w,VISITED)
                    setVertex1(A,v)
                    setVertex2(A,w)
                    setEdge(A,e)
                    List.addLast(A)
                    L(i+1).addLast(w)
                else
                    setLabel(e,CROSS)
    i = i + 1

假设一个n顶点有向无环图G是紧的。
如果有某种方法可以用0到n-1的整数对G的顶点进行编号使得G包含边(i,j)当且仅当i

(再次，我猜这与拓扑排序有关，但我不确定如何实现它)。
假设连通图G是双连通的，如果它不包含任何顶点，其移除会将G分成2个或更多连通分量。

给出一个O(n+m)时间的算法，对于有n>= 3个顶点，m>=(n-1)条边的连通图G，最多添加n条边，以保证G是双连通的。(可能跨越森林?)

我玩得很开心!至少，2和3。

1)我不确定我完全理解，但我认为"计算连接的组件"是指"构建顶点的子集，使每个子集都是一个连接的组件"。如果是这样，我认为BFS或DFS将取决于你如何管理内存(即。如何标记已经访问过的顶点)。

2)这里有一个算法，用于任何无环有向图，应该编号的顶点根据"紧凑"的定义，并检测图是否实际上是紧凑的(即。包含所有边(i, j)，使得i

相关内容

最新更新

热门标签：