1) 无向图的邻接表可以用HashMap表示吗?
HashMap<String,ArrayList<String>>
?
Key 是节点,ArraList 是边。如果对 (1) 的回答是"is"- 我如何检查此处的冗余?
例如:
1 -> 2,3,4
2 -> 1,5,6
... The 1->2 & 2->1 are same.
在这种情况下,如何使用这种数据结构进行 BFS/DFS?!
最佳答案
您不必担心冗余。 BFS 将以正常格式实现。 我不经常使用 Java,所以它是 Java 和 C++ 的混合体。 只是为了更正确, HashMap > 会是更好的选择,尽管两者都可以。原因:Set 具有独特的属性。
算法:
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);
}
}
关于algorithm - 使用 HashMap 构建图形?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13428063/