CODEWITHSUNDEEP
javagraph
Zeus
Zeus

Reputation: 2253

Implementing a Graph using a HashMap

I'm new to Java, so please keep that in mind before getting trigger happy down-voting. I'm familiar with the popular implementation of a graph of integers using an array.

Graph{
 int vertices;
 LinkedList<Integer>[] adj;

Graph(int vertices){
   this.vertices = vertices;
   adj = new LinkedList<>();
   for(int i= 0; i <vertices; i++){
      adj[i] = new LinkedList(); 
   }
}

However this implementation is best suited to a graph of integers. In case I want to implmentation graph of Characters, this implemetation doesn't render itself directly usable. So I tried implementing using a HashMap.

public class Graph {
    int vertices;
    HashMap<Character, LinkedList<Character>> adj;


    Graph(int item){

       this.vertices = item;
       adj = new HashMap<>();

    }
}

Where I'm a little stuck syntactically with Java is adding keys and values to this HashTable. What I'm trying to do is implement this method.

public void add(Character a, Character b){

            if (adj.containsKey(a)){

               //get a reference to the existing linked list
               //add to the existing LinkedList
            }else{

               //create a new LinkedList and add to it.
            }

        }
    }

I could use some help with the incomplete add method as also how to iterate through the this adj HashMap once the graph is constructed.

Upvotes: 3

Views: 11425

Answers (2)

Swaraj Kumar
Swaraj Kumar

Reputation: 323

HashMap stores the node number as key and the list of all the adjacent nodes as value. The list has been implemented using LinkedList class. Just change the class of Key and value according to your requirement.

class Graph{
HashMap<Integer,LinkedList<Integer>> map = new HashMap<>();

//add an edge from source to destination
void addEdge(int src, int dest){
    if(!map.containsKey(src)){
        LinkedList<Integer> l= new LinkedList<>();
        l.add(dest);
        map.put(src,l);
    }

    else{
        LinkedList<Integer> l= map.get(src);
        l.add(dest);
        map.put(src,l);
    }
}

//display the adjency list
void displayGraph(){
    for(Map.Entry m: map.entrySet()){
        System.out.println(m.getKey()+"-->"+m.getValue());
    }
}
public static void main(String[] args) {

    Graph g= new Graph();
    g.addEdge(0,1);
    g.addEdge(0,4);
    g.addEdge(0,5);
    g.addEdge(1,4);
    g.addEdge(1,3);
    g.addEdge(3,2);
    g.addEdge(2,1);
    g.addEdge(3,4);
    g.displayGraph();
}
}

Output:

  0-->[1, 4, 5]
  1-->[4, 3]
  2-->[1]
  3-->[2, 4]

Upvotes: 3

Atri
Atri

Reputation: 5831

Since your question is only about syntax, you can do something like this:

public void add(Character a, Character b){

        if (adj.containsKey(a)){

           //get a reference to the existing linked list
           LinkedList<Character> l = adj.get(a);

           //add to the existing LinkedList
           //You need to do a null check here to make sure (l != null)
           l.add(b)
        }else{

           //create a new LinkedList and add to it.
           LinkedList<Character> l = new LinkedList<Character>();
           l.add(b);
           adj.put(a, l);
        }

    }
}

Upvotes: 3

Related Questions