algorithm - Constructing a graph using hashmap?

Question

1) Can an undirected graph's adjacency list be represented using HashMap?

HashMap<String,ArrayList<String>>?

Key will be nodes and ArraList will be the edges. If answer is "yes" to (1) - How do I check the redundancy here?

Eg:

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

In this case, How to do a BFS/DFS using this data structure?!

Answer 1

You do not have to worry about redundancy. And BFS will be implemented in normal format. I dnt use Java much so its mix of Java and C++. And just to be more correct HashMap > would be better option though both will work. Reason : Set has unique property.

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);
    }
}