11

我知道有两种方法可以表示我的图表：一种是使用矩阵，另一种是使用列表。

如果我使用矩阵，我必须翻转矩阵中的所有位。这不需要 O(V^2) 时间吗？

如果我使用一个列表，我是不是必须一个一个地遍历每个列表并创建一个新集合？这似乎需要 O(V+E) 时间，这是线性的。我对么？

所以，我在这里有另一个问题。例如，考虑我在我的图（矩阵或列表）上使用 Dijkstra 算法，并且我们使用优先级队列作为场景背后的数据结构。图表示和数据结构的使用有什么关系吗？会不会影响算法的性能？

假设我要使用表示列表和 Dijkstra 算法的优先级队列，矩阵和使用 Dijkstra 的优先级队列之间会有区别吗？

我猜它只与makeQueue操作有关？或者他们根本没有什么不同？

4

4 回答 4

25

反转有向图的邻接表可以在线性时间内完成。我们只遍历图一次。复杂度的顺序将是 O(|V|+|E|)。

  1. 维护 Adjaceny Lists 的 HashMap，其中键是顶点标签，值是键顶点的相邻顶点的 ArrayList。
  2. 为了反转，创建一个相同类型的新 HashMap。扫描原始哈希图，并为您遇到的每个键，遍历相应的列表。
  3. 对于值列表中找到的每个顶点，在新的hashMap中添加一个key，将原始HashMap的key作为一个条目放入ArrayList中，对应于新HashMap中的新key。
public static HashMap<Character,ArrayList <Character>> getReversedAdjLists(RGraph g)
{
    HashMap <Character, ArrayList<Character>> revAdjListMap = new HashMap <Character, ArrayList<Character>>();
    Set <Character> oldLabelSet = g.adjListMap.keySet();

    for(char oldLabel:oldLabelSet)
    {
        ArrayList<Character> oldLabelList = g.adjListMap.get(oldLabel);

        for (char newLabel : oldLabelList)
        {
            ArrayList<Character> newLabelList = revAdjListMap.get(newLabel);

            if (newLabelList == null)
            {
                newLabelList = new ArrayList<Character>();
                newLabelList.add(oldLabel);
            }
            else if ( ! newLabelList.contains(oldLabel))
            {
                newLabelList.add(oldLabel);
            }

            revAdjListMap.put(newLabel, newLabelList);
        }
    }

    return revAdjListMap;
}
于 2013-07-06T02:46:52.150 回答
0

我认为通过遍历列表来反转图形需要 O(V 2 )，因为对于每个顶点，您必须添加或删除 (V-1) 边。

至于 Dijkstra 的算法，据我了解，如果您将图形表示为矩阵或列表，则该算法需要 O(V 2 )，但其他一些数据结构更快。已知最快的是斐波那契堆，它给出 O(E + VlogV)。

于 2013-04-23T01:35:59.873 回答
0

由于我看到一些评论询问就地图形转置（反转），这是我的版本。请注意，这仅适用于 DAG。欢迎提供反馈和改进建议

def transpose(G):
    """
    Return the transpose of a directed graph i.e. all the edges are reversed (In Place)
    """
    #note this is not a standard lib function afaik and you would have to 
    #implement topological sort but that should be easy
    topsort = topological_sort(G) 
    topsort.reverse() # we want to process starting from sink node
    for v in topsort:
        for node in G[v]:
            G[node].append(v)
        #  remove all older members of the vertex 'v'  
        G[v] = []
    print(G)
于 2020-09-21T03:35:07.550 回答
0 
G = {"A":["B", "C","D"],"B":["C", "E"], "C":["D", "E"],"D":[],"E":["D"] }
res ={}
for k in G.keys():
    for val in G[k]:
        if val not in res.keys():
            res[val] = [k]
        else:
            res[val].append(k)

print(res)
于 2019-04-29T18:29:01.830 回答