title: Java assignment to use Dijkstras search method, breath-first and depth first
body: <p>Hello StackOverflow community, need your help. I have a final for my java class and its asking for:
  Generate a graph with 100,000 nodes, where each node randomly has between 1 and 5 connections to other nodes. Each node should contain within it a random value between 1 and 300,000. (So generally about 1 in 3 searches will yield a query match). Allow the user to enter a number to search for, and implement each of the following three types of searching algorithms. Breadth-First. (30 points) Depth-First. (30 points) Dijkstra's Algorithm. (40 points)</p>
  
  <p>Do not allow back-tracking in your searches. (Mark nodes that you already searched as complete, and do not re-visit them in the same search). Each search should return the following: The Success/Failure of your search. The length of the shortest path to the found node. The total number of nodes examined during the search. Optionally you may return the exhaustive display of the shortest path, for testing and verification.</p>
  
  <p>For some reason, my IDE shows that BFS and Dijkstras has "duplicated code fragment 17 lines long" can someone look at tell me how to fix it or maybe a better way to implement it? Also, if i try to do nodesNum > 30k in "Driver Class" i get a memory leak. </p>
  
  <p>Here is the code: </p>
  
  <p>Class Graph:</p>
  
  <pre><code>import java.util.*;
  import javax.swing.JOptionPane;
  
  class Graph
  {
      private Listing[] vertex;
      private int[][] edge;
      private int max;
      private int numberOfVertices;
      private int nodeCheck = 0;
      private int selectNum = 0;
  
      Graph(int g)
      {
          vertex = new Listing[g];
          edge = new int[g][g];
          max = g;
          numberOfVertices = 0;
      }
      private void depthFirstSearch(int firstVertex)
      {
          int v;
          Stack&lt;Integer&gt; nodeStack = new Stack&lt;&gt;();
  
          for(int i = 0; i&lt;numberOfVertices; i++)
          {
              if (vertex[i] != null) {
                  vertex[i].setPushed(false);
              }
          }
          nodeStack.push(firstVertex);
          vertex[firstVertex].setPushed(true);
  
          while (!nodeStack.empty())
          {
              v = nodeStack.pop();
              vertex[v].visit();
              nodeCheck++;
              for (int column = 0; column &lt; numberOfVertices; column++)
              {
  
                  if(edge[v][column] == 1 &amp;&amp; vertex[column].getPushed())
                  {
                      nodeStack.push(column);
                      vertex[column].setPushed(true);
                  }
              }
          }
      }
      private void breathFirstSearch(int firstVertex)
      {
          int V;
          Queue&lt;Integer&gt; nodeQueue = new LinkedList&lt;&gt;();
  
          for(int i = 0; i &lt; numberOfVertices; i++)
          {
              if(vertex[i] != null)
                  vertex[i].setPushed(false);
          }
          nodeQueue.add(firstVertex);
          vertex[firstVertex].setPushed(true);
  
          while(!nodeQueue.isEmpty())
          {
              V = nodeQueue.remove();
              vertex[V].visit();
              nodeCheck++;
              for(int column = 0; column &lt; numberOfVertices; column++)
              {
                  if(edge[V][column] == 1 &amp;&amp; vertex[column].getPushed())
                  {
                      nodeQueue.add(column);
                      vertex[column].setPushed(true);
                  }
              }
          }
      }
  
      private void Dijkstra(int firstVertex)
      {
          int v;
          LinkedList&lt;Integer&gt; nodeQueue = new LinkedList&lt;&gt;();
  
          int i = 0;
          while (i &lt; numberOfVertices)
          {
              if(vertex[i] != null)
                  vertex[i].setPushed(false);
              i++;
          }
          nodeQueue.add(firstVertex);
          vertex[firstVertex].setPushed(true);
  
          while(!nodeQueue.isEmpty())
          {
              v = nodeQueue.remove();
              vertex[v].visit();
              nodeCheck++;
              for(int column = 0; column &lt; numberOfVertices; column++)
              {
                  if(edge[v][column] == 1 &amp;&amp; vertex[column].getPushed())
                  {
                      nodeQueue.add(column);
                      vertex[column].setPushed(true);
                  }
              }
          }
      }
  
      private void insertVertex(int vertexNumber, Listing newListing)
      {
          if(vertexNumber &gt;= max)
          {
              return;
          }
          vertex[vertexNumber] = newListing.deepCopy();
          numberOfVertices++;
      }
  
      private void insertEdge(int fromVertex, int toVertex)
      {
          if(vertex[fromVertex] == null || vertex[toVertex] == null)
              return;
          edge[fromVertex][toVertex] = 1;
      }
  
      void showVertex(int vertexNumber)
      {
          System.out.print(vertex[vertexNumber]);
      }
  
      void showEdges(int vertexNumber)
      {
          for(int column = 0; column &lt; numberOfVertices; column++)
          {
              if(edge[vertexNumber][column] == 1)
              {
                  System.out.println(vertexNumber + "," + column);
              }
          }
          System.out.println();
      }
  
      void InitializeNodes(Graph G, int nodesNum)
      {
          Random random = new Random();
          for (int i = 0; i &lt; nodesNum; i++ )
          {
              Listing v = new Listing(random.nextInt(300000) + 1);
              G.insertVertex(i, v);
          }
  
          int vertexListNumber = G.vertex.length;
          List&lt;Integer&gt; list = new ArrayList&lt;&gt;();
          for (int i = 0; i &lt; nodesNum; i++ )
          {
              list.add(i);
          }
          Collections.shuffle(list);
          for (int i = 0; i &lt; vertexListNumber; i++ )
          {
              int randnum = random.nextInt(5);
              for (int j = 0; j &lt; randnum; j++ )
              {
                  int rand = random.nextInt(5);
                  G.insertEdge(i, list.get(rand));
              }
          }
  
      }
  
      int Search()
      {
          String search = JOptionPane.showInputDialog("Enter Node to search:");
          try
          {
              if(search != null)
              {
                  selectNum = Integer.parseInt(search);
              }
          }
          catch (NumberFormatException e)
          {
              selectNum = 0;
          }
          return selectNum;
      }
  
      private int SelectPane()
      {
          String paneSelect = JOptionPane.showInputDialog("Choose a search method:" +
                  "\n\t1: Use Depth-First Search" +
                  "\n\t2: Use Breadth-First Search" +
                  "\n\t3: Use Dijkstra's Search" +
                  "\n\t4: Close  Program");
          int selectNum = 0;
  
          try{
              if(paneSelect != null)
              {
                  selectNum = Integer.parseInt(paneSelect);
              }
          }
          catch (NumberFormatException ignored)
          {
          }
          return selectNum;
      }
  
      void algorithmChoice(Graph graph, int vertexStart)
      {
          int paneNum = 0;
          while (paneNum != 4)
          {
              paneNum = SelectPane();
              switch (paneNum)
              {
                  case 1:
                      graph.depthFirstSearch(vertexStart);
                      System.out.println("Nodes counted were: " + nodeCheck);
                      System.out.println("------------------------------------");
                      break;
                  case 2:
                      graph.breathFirstSearch(vertexStart);
                      System.out.println("Nodes counted were: " + nodeCheck);
                      System.out.println("------------------------------------");
                      break;
                  case 3:
                      graph.Dijkstra(vertexStart);
                      System.out.println("Nodes counted were: " + nodeCheck);
                      System.out.println("------------------------------------");
                      break;
                  case 4:
                      break;
                  default:
                      JOptionPane.showMessageDialog(null, "Enter 4 to quit.");
                      break;
              }
          }
      }
  
  
  }
  </code></pre>
  
  <p>Class Listing: </p>
  
  <pre><code>public class Listing
  {
      private int value;
      private boolean pushed;
  
      Listing(int v)
      {
          value = v;
      }
      public String toString()
      {
          return ("Vertex: " + value + "\n" );
      }
  
      Listing deepCopy()
      {
          return new Listing(value);
      }
      boolean getPushed()
      {
          return !pushed;
      }
      void setPushed(boolean value)
      {
          pushed = value;
      }
      void visit()
      {
          System.out.println(this);
      }
  }
  </code></pre>
  
  <p>Class Driver:</p>
  
  <pre><code>public class Driver
  {
      public static void main(String[] args)
      {
          int nodesNum = 30000; //Can go up to 30k nodes, otherwise causes memory leak.
          Graph graph = new Graph(nodesNum);
          graph.InitializeNodes(graph, nodesNum);
  
          for(int i = 0; i&lt;5; i++)
          {
              System.out.print("Node " + i + "\'s ");
              graph.showVertex(i);
              System.out.print("Its routes are:\n");
              graph.showEdges(i);
          }
  
          int select = graph.Search();
          graph.algorithmChoice(graph, select);
      }
  }
  </code></pre>
  
  <p>Thanks alot for your help!</p>