# Graph implementation for solving graph problems (java)

Posted on

Problem

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;
Node(int id)
{
this.id =id;
}
}
``````

## 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;
}
{

Node s = check(src) ? getNode(src):new Node(src);
Node d = check(dest) ? getNode(dest):new Node(dest);

}

void print()
{
for(Node temp : nodes)
{
System.out.print(temp.id+" -> ");
System.out.println();
}
}
void dfs(Node root)
{
if(root == null) return;
System.out.print(root.id+" ");
root.visited = true;
{
if(!t.visited)
dfs(t);
}
}
void refresh()
{
for(Node temp : nodes)
{
temp.visited =false;
}
}
void bfs(Node root)
{
root.visited =true;
while(!q.isEmpty())
{
Node temp = q.poll();
System.out.print(temp.id+" ");
{
if(!n.visited)
{
n.visited=true;
}
}
}
}

public static void main(String[] args) {
Graph g = new Graph();
/*
*                0
*             /  |
*            1   2   3
*           /
*          4  5    6   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.

Solution

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.