0
import java.util.ArrayList;
import java.io.*;
import java.util.*;
import java.util.Graph;

public class Graph 
{

    public int[][] adjMatrix;//Edges will be represented as adjacency Matrix
    int size;

    }
    public Graph(int size)
    {
        adjMat = new boolean[size][size];
        for (int i=0; i < adjMat.length; i++)
        {
            for (int j=0; j < adjMat.length; j++)
            {
                adjMat[i][j] = false;
            }
        }     
    }

    //This method will be called to make connect two nodes
    public void connectNode(Node start,Node end)
    {
        if(adjMatrix==null)
        {
            size=nodes.size();
            adjMatrix=new int[size][size];
        }

    public void add(int 0, int 6)
    {
        adjMat[0][6] = true;
    }

        // The frontier is an ArrayList of Paths.
        ArrayList<Path> frontier = new ArrayList<Path>();

        // Initially the frontier contains just the Path
        // containing only the start node.
        Path firstPath = new Path(start);        
        frontier.add(firstPath);

        // Search until the goal is found,
        // or the frontier is empty.

        while (!frontier.isEmpty()) {
            while (!frontier.isEmpty())
    {
        currentNode = frontier.poll();
        explored.add(currentNode);
        for (Node node : currentNode.children) {//adding node children to fronier and checking if they are goal
            if (!frontier.contains(node) || !explored.contains(node)) {
                frontier.add(node);
                prev.put(node, currentNode);//mapping nodes to parent node to return sequence of nodes
                if (node.isGoal) {
                    goalNode = node;
                    break;
                }
            }
        }

  }
  return false;
}

    public static void main(String[] args)
    {

        Graph g = new Graph(7);

        // Add edges to the Graph
        g.add(0, 1);
        g.add(0, 2);
        g.add(1,5);
        g.add(1,6);
        g.add(2, 3);
        g.add(3, 4);

        // select a search type
        boolean depthFirst = true;

        // start searching
        g.search(0,4, depthFirst);
    }
4
Contributors
4
Replies
22
Views
4 Months
Discussion Span
Last Post by AssertNull
0

DFS stands for Depth First Search . it is much similar to depth first traversal of a tree.
<code>

#include<iostream>
#include<list>
using namespace std;

class Graph
{
    int V;    // No. of vertices
    list<int> *adj;
    void DFSUtil(int v, bool visited[]);
public:
    Graph(int V);   // Constructor

    // function to add an edge to graph
    void addEdge(int v, int w);

    // DFS traversal of the vertices
    // reachable from v
    void DFS(int v);
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}

void Graph::DFSUtil(int v, bool visited[])
{
    // Mark the current node as visited and
    // print it
    visited[v] = true;
    cout << v << " ";

    // Recur for all the vertices adjacent
    // to this vertex
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}

// DFS traversal of the vertices reachable from v.
// It uses recursive DFSUtil()
void Graph::DFS(int v)
{
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // Call the recursive helper function
    // to print DFS traversal
    DFSUtil(v, visited);
}

int main()
{
    // Create a graph given in the above diagram
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    cout << "Following is Depth First Traversal"
            " (starting from vertex 2) \n";
    g.DFS(2);

    return 0;
}
1

Also, there are TWO code dumps by TWO different users in TWO different languages in one thread, with no explanation from either user. Is this the same user with two different accounts? Who knows? The first post has more than one bracket mismatch. The second one has a memory leak. Thus neither should be used as a tutorial. In addition, while it's not unthinkable to post C++ code to a Java thread, if you do so, you should have a very good reason for doing so, a reason that you should explain.

I echo RProffitt's comments. You can't expect people to guess. If you want help, you need to make it obvious what the problem is.

Votes + Comments
Obvious +1
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.