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 を実行するには?!
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 を実行するには?!
冗長性について心配する必要はありません。また、BFS は通常の形式で実装されます。私は Java をあまり使用していないので、Java と C++ が混在しています。そして、より正確に言うと、 HashMap > の方が適切なオプションですが、両方とも機能します。理由: セットに固有のプロパティがあります。
アルゴリズム:
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);
}
}