使用散列表構建圖形？

Question

1）可以使用HashMap來表示無向圖的鄰接列表嗎？

HashMap<String,ArrayList<String>>？

鍵將是節點並且ArraList將是邊。如果對（1）的回答爲「是」 - 如何在此檢查冗餘？

如：

1 -> 2,3,4 2 -> 1,5,6 ... The 1->2 & 2->1 are same.

在這種情況下，如何做到使用這種數據結構的BFS/DFS？

Answer 1

您不必擔心冗餘。 而BFS將以正常格式實施。 我dnt很多地使用Java，所以它的Java和C++的混合。 只是爲了更正確HashMap>會更好，但兩者都可以。原因：集具有獨特的屬性。

ALGO：

HashMap<String, ArrayList<String> > graph; 
Set<String> visited; 
queue<String> currentTraverse; // a data structure which has efficient front removal and back insertion 
currentTraverse.push_back(sourcePoint); 
visited.insert(sourcePoint); 
while(! currentTraverse.empty()) 
{ 
    String currentNode = currentTraverse.front(); 
    currentTraverse.pop_front(); 
    ArrayList<String> adjacentNodes = graph.find(currentNode)->second; 
    for(String node adjacentNodes) 
    { 
     pair<iterator, bool> isVisited = visited.insert(node); 
     if(!isVisited.second) // if not in visited set 
      currentTraverse.push_back(node); 
    } 
}