Graph Traversal: Breadth First Seach and Depth First Search


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 8 of 8

Thread: Graph Traversal: Breadth First Seach and Depth First Search

  1. #1
    Join Date
    Mar 2009
    Posts
    24

    Graph Traversal: Breadth First Seach and Depth First Search

    I don't understand BFS and DFS. How do I visit the vertex and mark it as visited? Not sure how to do DFS with an arraylist of iterators. Need to some how iterate through the adjacency list for each vertex.

    Code:
    public class Graph
    {
        // translate integer vertex to string name
        private final List<String> vertexName = new ArrayList<String>();
        // translate name to integer form of vertex
        private final Map<String, Integer> nameToVertexMap = new HashMap<String, Integer>();
        // represent adjacency list of the graph
        private final List<List<Integer>> adjacencyList = new ArrayList<List<Integer>>();
        
        // Reads data from a scanner and builds the graph.
        public void buildGraph(Scanner sc)
        {
            while (sc.hasNext())
            {
                // get data for the adjacency list of one vertex
                String initVertexName = sc.next();
                int initVertex = this.getVertexForName(initVertexName);
                if (initVertex == -1)
                    initVertex = this.addNewAssociation(initVertexName);
                List<Integer> adjList = this.getNeighbors(initVertex);
                // get the outdegree
                int outDegree = sc.nextInt();
                // collect list of neighbors for this vertex
                for (int k = 0; k < outDegree; k++)
                {
                    // get the string name of the terminal vertex for an edge
                    String finalVertexName = sc.next();
                    //get the vertex number for this vertex name
                    int finalVertex = this.getVertexForName(finalVertexName);
                    // if the vertex name has no number, get it a number
                    if (finalVertex == -1)
                        finalVertex = this.addNewAssociation(finalVertexName);
                    adjList.add(finalVertex);
                }
            }
        }
        
        // string representation of the adjacency list of the graph
        @Override
        public String toString()
        {
            StringBuilder sb = new StringBuilder();
            for (int v = 0; v < this.adjacencyList.size(); v++)
            {
                sb.append(this.vertexName.get(v) + " : ");
                List<Integer> adjL = this.adjacencyList.get(v);
                for (Integer i : adjL)
                    sb.append(vertexName.get(i) + " ");
                sb.append("\n");
            }
            
            return sb.toString();
        }
        
        /**
         * @param vertex: integer representation of a vertex.
         * @return the adjacency list for a specified vertex
         */
        public List<Integer> getNeighbors(int vertex)
        {
            return adjacencyList.get(vertex);
        }
    
        // returns the number of vertices in this graph
        public int getNumberOfVertices()
        {
            return adjacencyList.size();
        }
        
        // returns string name of the vertex to use for output.
        public String getVertexName(int vertex)
        {
            return vertexName.get(vertex);
        }
        
        /**
         * @param name: name of a vertex, read from an input stream or scanner
         * @return the integer (vertex) assigned to that name, or -1 if no integer
         *         vertex has been assigned to that name.
         */
        public int getVertexForName(String name)
        {
            return vertexName.indexOf(name);
        }
        
        /**
         * Adds a new vertex with a given name to the graph and associates
         * the string name of the vertex with an integer used to identify the vertex.
         * @param name: string name for a vertex
         * @return an integer value that will be used to identify the vertex.
         */
        private int addNewAssociation(String name)
        {
            int vertex = getVertexForName(name);
            if (vertex != -1) throw new IllegalStateException("There is already a " +
                    "vector with name " + name);
            this.vertexName.add(name);
            this.adjacencyList.add(new ArrayList<Integer>());
            // The integer associated with the name is its index in the list vertexName
            vertex = vertexName.size() - 1;
            nameToVertexMap.put(name, vertex);
            
            return vertex;
        }
    }
    Code:
    public class GraphTraversal
    {
        /**
         * This version of BFS will stop as soon as it finds a path from the source
         * to the destination.
         * @param source: the vertex where the search should begin.
         * @param dest: the vertex where the search should end.
         * @param graph: the graph to be searched.
         * @param visited: a boolean array used to mark vertices when they are
         *                 visited.
         * @param pred: an integer array that assigns to each vertex its predecessor
         *              in the path that is found.
         */
        static void breadthFirstSearch(int source, int dest, Graph graph,
                boolean [] visited, int [] pred)
        {
            visited = new boolean [graph.getNumberOfVertices()];
            pred = new int [graph.getNumberOfVertices()];
            
            Queue<Integer> q = new LinkedList<Integer>();
            // visit source
            // mark source
            q.offer(source);
          
            while(!q.isEmpty())
            {
                int f = q.peek();
                List<Integer> w = graph.getNeighbors(f);
                for(int i : w)
                {
                    // visit w
                    // mark w
                    q.add(w.remove(i));
                }
            }
            q.remove();
        }
        
        // This version of DFS will stop as soon as it finds a path from the source to the destination.
        static void depthFirstSearch(int source, int dest, Graph graph,
                boolean [] visited, int [] pred)
        {
             ArrayList<Iterator> i = new ArrayList<Iterator>();
        }
        
        /**
         * breadthFirst performs a BFS of a graph.
         * @param source: the initial vertex for the search
         * @param graph: This is the graph to be traversed
         * @param visited: this array indicates which vertices have been visited.
         *                 BFS will set visited[v] = for only those vertices that were
         *                 visited. Here v is the index that identifies a vertex in
         *                 the graph.
         * @param pred: for each vertex v that is visited, pred[v] will be set to its
         *              predecessor, that is, the vertex that led to v in the BFS.
         */
        static void breadthFirstSearch(int source, Graph graph, boolean [] visited,
                int [] pred)
        {
            breadthFirstSearch(source, graph.getNumberOfVertices(), graph, visited,
                    pred);
        }
        
        static void breadthFirstSearch(String s_source, Graph graph,
                boolean [] visited, int [] pred)
        {
            int source = graph.getVertexForName(s_source);
            breadthFirstSearch(source, graph.getNumberOfVertices(), graph, visited,
                    pred);
        }
        
        static void breadthFirstSearch(String s_source, String s_dest, Graph graph,
                boolean [] visited, int [] pred)
        {
            int source = graph.getVertexForName(s_source);
                    int dest = graph.getVertexForName(s_dest);
            breadthFirstSearch(source, dest, graph, visited, pred);
        }
        
        static void depthFirstSearch(String source, Graph graph, boolean[] visited,
                int [] pred)
        {
            int sourceVertex = graph.getVertexForName(source);
            depthFirstSearch(sourceVertex, graph.getNumberOfVertices(), graph,
                    visited, pred);
        }
        
        static void depthFirstSearch(int source, Graph graph, boolean [] visited,
                int [] pred)
        {
            depthFirstSearch(source, graph.getNumberOfVertices(), graph, visited,
                    pred);
        }
        
        static void depthFirstSearch(String source, String dest, Graph graph, 
                boolean [] visited, int [] pred)
        {
            int sourceVertex = graph.getVertexForName(source);
            int destVertex = graph.getVertexForName(dest);
            depthFirstSearch(sourceVertex, destVertex, graph, visited, pred);
        }
        
        /**
         * getPath finds the path that goes from a given start vertex to a
         *         given destination vertex
         * @param source: the start vertex for a path.
         * @param dest: the end vertex for a path.
         * @param pred: an array that specifies the predecessor of each vertex in
         *              a path. If a vertex has no predecessor in the path, its
         *              predecessor is null.
         * @return a list of vertices that form a path from a source vertex to
         *         a destination vertex.
         */
        public static List<Integer> getPath(int source, int dest, int [] pred)
        {
            List<Integer> path = new LinkedList<Integer>();
            int current = dest;
            while (current != source)
            {
                path.add(0, current);
                current = pred[current];
                if (current == -1)
                {
                    path.clear();
                    return path;
                }
            }
            
            path.add(0, source);
            return path;
        }
        
        /**
         * getPath finds a path from a given start vertex to a given destination vertex.
         * It allows the vertices to be specified by name instead of by numeric values.
         * @return a list of vertex names for the vertices on the path.
         */
        static List<String> getPath(String source, String dest, int [] pred, Graph graph)
        {
            int sourceVertex = graph.getVertexForName(source);
            int destVertex = graph.getVertexForName(dest);
            List<Integer> path = getPath(sourceVertex, destVertex, pred);
            List<String> sPath = new ArrayList<String>();
            for (int i : path)
                sPath.add(graph.getVertexName(i));
            return sPath;
        }
    }

  2. #2
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    have you thought of the vertices as objects of a class? if this were so, what could you do to mark an object as "visited"?

  3. #3
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    To keep track of visited vertices: have a data structure which is easily searched so you can look-up that vertex.

    DFS: An easy implementation is using a stack. As you you visit a vertex, store all of the adjacent edges in the stack. When you've finished adding edges, now pop off the edge at the top [or if you are using a list, add to the back of the list and then remove from the back of the list]. Is the terminus of the edge that has been popped been visited? If so, discard that edge and pop another. If it has not been visited, mark it as visited and then visit it.

  4. #4
    Join Date
    Mar 2009
    Posts
    24
    This is what I had written for BFS. I'm supposed to add the source to the queue. Then visit source and mark it as visited by adding it to an array of booleans. After I visit the source I'm supposed to check it's neighbors and add them to the queue. I keep checking the neighbors of each vertex in the queue. What I don't get is how do I visit the vertex and it's neighbors and how do I add it to an array of booleans. Also how do I use pred? I'm not sure where to put that in the code.

    Code:
    /**
         * This version of BFS will stop as soon as it finds a path from the source
         * to the destination.
         * @param source: the vertex where the search should begin.
         * @param dest: the vertex where the search should end.
         * @param graph: the graph to be searched.
         * @param visited: a boolean array used to mark vertices when they are
         *                 visited.
         * @param pred: an integer array that assigns to each vertex its predecessor
         *              in the path that is found.
         */
        static void breadthFirstSearch(int source, int dest, Graph graph,
                boolean [] visited, int [] pred)
        {
            visited = new boolean [graph.getNumberOfVertices()];
            pred = new int [graph.getNumberOfVertices()];
            
            Queue<Integer> q = new LinkedList<Integer>();
            // visit source
            // mark source
            q.offer(source);
          
            while(!q.isEmpty())
            {
                int f = q.peek();
                List<Integer> w = graph.getNeighbors(f);
                for(int i : w)
                {
                    // visit w
                    // mark w
                    q.add(w.remove(i));
                }
            }
            q.remove();
        }

  5. #5
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    You read the first edge in the queue. You "visit" the terminus of the destination of that edge by:

    1. Look in your boolean array to see if this vertex has been visited (is the value at visited[new vertex] TRUE or FALSE). If true, then it has been visited and you do nothing more with this vertex, remove the first edge in the queue, and start over.
    2. If it has not been visited, store the value of the start vertex for this edge in pred[new vertex]; test to see if this is your destination [if so, you're done]; read each of the vertices in the adjacency list for the vertex you're visiting, adding each edge to the end of the queue. Set the value of visited[new vertex] as TRUE. You're done, so now remove this edge from the queue and start over.
    Last edited by nspils; 03-16-2009 at 09:13 AM.

  6. #6
    Join Date
    Mar 2009
    Posts
    24
    I'm still confused.

    So is this what I'm supposed to do:
    - Create an empty visited and pred arrays
    - Create an empty queue
    - Add source (vertex) to the queue
    - Visit the source (vertex) - Not sure how to do this. What does it mean to visit a vertex? Does visiting the vertex mean you peek at it in the queue?
    - Mark it as visited - If the visited arrays are empty how do I know if it has been visited. Can I say that if it has been visited set it to true in the visited array?
    - While the queue is not empty get the neighbors of the first element in the queue.
    - Visit/Mark the neighbor
    - Keep visiting/marking neighbors of the first element in the queue until the first element is the destination
    Last edited by justinsbabe5000; 03-16-2009 at 05:03 PM.

  7. #7
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    the arrays and the queue exist before you do your traversal. Don't create new ones.

    Visit means to do work "at" that vertex. So when you "visit" the source, you do all your processes for that vertex. Then you "discard" that vertex and move to the next you are going to visit - if it has not been visited yet.

    When you visit, check if the destination; check if visited; record pred for this node; add all "neighbors" to the queue ... you don't move on to any, yet. Mark this vertex as having been visited.

    think of this as your graph (written as adjacency list form)

    0 - - 1, 2, 3, 4
    1 - - 5
    2 - - 6, 7, 8
    3 - - null
    4 - - 9, 10
    5 -- 11, 12
    6 -- null
    7 -- 13
    8 -- 14, 15, 16
    9 -- null
    10 -- null
    11 -- 17, 18
    12 -- null
    13 -- null
    14 -- null
    15 -- null
    16 -- null
    17 -- null
    18 -- null

    0 is the source, 9 is your destination

    Now, sketch out your processes as you visit - what will the values of the arrays and the queue before you visit 0? How do the arrays and the queue change as you visit 0? Now, move to the first neighbor. What does the queue look like? What are the values of the arrays?

    Now, ask and answer your questions. Plus: how best do we store the value of both pred and destination of each "edge" as an Integer? How do you mark the value for pred? How do you initialize the arrays so that the values you want as default values are there?

  8. #8
    Join Date
    Mar 2009
    Posts
    24
    Thanks. I kinda got it to work. I did some search online and found an example of how to do both BFS and DFS and I took what you said and I figured it out.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center