Graph implementation for solving graph problems (java)

Question

I've currently started solving some competitive programming Graph questions. But Started using adjacency list as HashMap<Integer,ArrayList<Integer>> list . But in some problems, this doesn't work. so I decided to implement class Graph other than this HashMap. I would like a review of efficiency and general code quality. Please let me know if this follow standard adjacency list implementation and best and worst-case scenarios.

Node class

class Node
{
 public int id;
 public boolean visited;
 public List<Node> adjecent;
 Node(int id)
 {
 this.id =id;
 adjecent = new ArrayList<>();
 }
}

Graph

class Graph
{
 private List<Node> nodes;
 Graph()
 {
 nodes = new ArrayList<>();
 }
 boolean check(int id)
 {
 boolean flag = false;
 for(Node temp:nodes)
 {
 if(temp.id == id)
 flag =true;
 }
 return flag;
 }
 Node getNode(int id)
 {
 for(Node temp:nodes)
 {
 if(temp.id == id)
 return temp;
 }
 return null;
 }
 void addEdge(int src,int dest)
 {
 
 Node s = check(src) ? getNode(src):new Node(src);
 Node d = check(dest) ? getNode(dest):new Node(dest);
 s.adjecent.add(d);
 d.adjecent.add(s);
 
 if(!check(src)) nodes.add(s);
 if(!check(dest)) nodes.add(d);
 }
 void print()
 {
 for(Node temp : nodes)
 {
 System.out.print(temp.id+" -> ");
 temp.adjecent.forEach(e->System.out.print(e.id+" "));
 System.out.println();
 }
 }
 void dfs(Node root)
 {
 if(root == null) return;
 System.out.print(root.id+" ");
 root.visited = true;
 for(Node t : root.adjecent)
 {
 if(!t.visited)
 dfs(t);
 }
 } 
 void refresh()
 {
 for(Node temp : nodes)
 {
 temp.visited =false;
 }
 }
 void bfs(Node root)
 {
 Queue<Node> q =new LinkedList<>();
 root.visited =true;
 q.add(root);
 while(!q.isEmpty())
 {
 Node temp = q.poll();
 System.out.print(temp.id+" ");
 for(Node n:temp.adjecent)
 {
 if(!n.visited)
 {
 n.visited=true;
 q.add(n);
 }
 }
 }
 }
 public static void main(String[] args) {
 Graph g = new Graph();
 /*
 * 0
 * / | \ 
 * 1 2 3
 * / \ \ \
 * 4 5 6 7
 */
 g.addEdge(0, 1);
 g.addEdge(0, 2);
 g.addEdge(0, 3);
 g.addEdge(1, 4);
 g.addEdge(1, 5);
 g.addEdge(2, 6);
 g.addEdge(3, 7);
 g.print();
 System.out.println(g.nodes.size());
 g.dfs(g.getNode(0));
 System.out.println();
 g.refresh();
 g.bfs(g.getNode(0));
 
 }
} 

Any suggestions to make this code leverage to better efficiency is appreciated.

Answer 1

Don't store method flow flags as state in classes. This is a breach in object-oriented design.

class Node
{
 public boolean visited;
 // .. other
}

Search methods like dfs should use a map of some sort to store which nodes are visited.

By storing this flag incorrectly as state, you'll get in trouble when multiple threads search the graph concurrently.

• Ashish Pawar: I just put a visited flag to every node so I check whether it is visited or not
• dfhwze: exactly my point :)