Graph traversal

GRAPH REPRESENTATION

There are 3 ways in which we can represent graphs:

1. Array of edges
2. Adjacency Matrix
3. Adjacency List.

DEPTH FIRST SEARCH

1. Recursive <
2. Iterative -> Stack

BREADTH FIRST SEARCH

1. Recursive is hard.
2. Iterative

CODE

public class GraphRep {

    class Node{
        private int data;
        private boolean visited;

        Node(int data){
            this.data = data;
        }

    }

    class Graph{
        private int nE;
        private int nV;
        private Map<Node, List<Node>> edges;


    }

    public void insertEdge(){}
    public void removeEdge(){}
    public void isAdjacent(Node node1, Node node2){}


    public List<Node> getEdgeList(Node vertex1, Node vertex2){
        List<Node> edge = new ArrayList<Node>();

        edge.add(vertex1);
        edge.add(vertex2);

        return edge;
    }
    public Graph getDummyGraph(){
        Graph graph = new Graph();

        graph.nE = 10;
        graph.nV = 3;

        Node vertex1 = new Node(1);
        Node vertex2 = new Node(2);
        Node vertex3 = new Node(3);

        Map<Node,List<Node>> edges = new HashMap<Node,List<Node>>();
        edges.put(vertex1, getEdgeList(vertex2,vertex3));
        edges.put(vertex2, getEdgeList(vertex1,vertex3));
        edges.put(vertex3, getEdgeList(vertex1,vertex2));

        graph.edges = edges;

        return graph;

    }

    public boolean DfsRecursive(Graph g, Node src, Node dest){
        src.visited = true;

        if(src.equals(dest)){
            return true;
        }
        else{
            for(Node edge:g.edges.get(src)){
                if(!edge.visited){
                    return DfsRecursive(g,edge,dest);
                }
            }
        }

        return false;
    }

    public boolean DfsIterative(Graph g, Node src, Node dest){
        src.visited = true;
        
        if(src.equals(dest)){
            return true;
        }

        Stack<Node> stack = new Stack<Node>();

        stack.push(src);

        while(!stack.empty()){
            Node node = stack.pop();
            node.visited = true;
            if(node.equals(dest)){
                return true;
            }
            for(Node edge:g.edges.get(node)){
                if(!edge.visited){
                    stack.push(edge);
                }
            }
        }

        return false;
    }


    public boolean BfsIterative(Graph g, Node src, Node dest){
        src.visited = true;

        if(src.equals(dest)){
            return true;
        }
        Queue<Node> queue = new LinkedList<Node>();

        queue.add(src);

        while(!queue.isEmpty()){
            Node node = queue.remove();
            node.visited = true;

            if(node.equals(dest)){
                return true;
            }

            for(Node edge:g.edges.get(node)){
                queue.add(edge);
            }
        }

        return false;

    }
}