1
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I just put a visited flag to every node so I check whether it is visited or not \$\endgroup\$ Sep 11, 2019 at 8:20
  • \$\begingroup\$ exactly my point :) \$\endgroup\$
    – dfhwze
    Sep 11, 2019 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.