使用 HashMap 实现图

Question

我对Java还不熟悉，请在投票前记得这一点。我熟悉使用数组实现整数图的流行方法。

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

然而，这种实现最适合整数图。如果我想要实现字符图，这种实现就不能直接使用。因此，我尝试使用 HashMap 实现。

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


    Graph(int item){

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

    }
}

在Java语言中，我在向HashTable添加键和值方面遇到了一些句法上的困难。我的目标是实现这个方法。

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.
            }

        }
    }

我需要帮助完成add方法以及如何在构建图后遍历adj HashMap。

- Zeus

Answer 1

HashMap将节点编号作为键，将所有相邻节点的列表作为值进行存储。该列表使用 LinkedList类 实现。根据您的需求，只需更改键和值的类即可。

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

输出：

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

- Swaraj Kumar

Answer 2

既然您的问题只涉及语法，您可以这样做：

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

    }
}

- Atri