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