Depth-First-Traversal und Adj Matrix

Ich versuche zu tun, eine Tiefe ersten Durchlauf. Ich habe keine Ahnung, ob ich auch in der Nähe. Jetzt heißt es drucken 1 3 4 5. Es sollte drucken 1 2 4 7 3 5 6. Jede Hilfe oder Beratung wird geschätzt. Danke. 🙂

Klasse:

 public class myGraphs {
     Stack<Integer> st;
     int vFirst;

     int[][] adjMatrix;
     int[] isVisited = new int[7];


     public myGraphs(int[][] Matrix) {
         this.adjMatrix = Matrix;
         st = new Stack<Integer>();
         int i;
         int[] node = {1, 2, 3, 4, 5, 6, 7};
         int firstNode = node[0];

         for (i = 1; i < node.length - 1; i++) {
             depthFirst(firstNode, node[i]);
         }
    }

    public void depthFirst(int vFirst, int n) {
        int v, i;

        st.push(vFirst);

        while (!st.isEmpty()) {
            v = st.pop();
            if (isVisited[v]==0) {
                System.out.print("\n"+v);
                isVisited[v]=1;
            }

            for ( i=1;i<=n;i++) {
                if ((adjMatrix[v][i] == 1) && (isVisited[i] == 0)) {
                    st.push(v);
                    isVisited[i]=1;
                    System.out.print(" " + i);
                    v = i;
                }
            }
        }
    }

    //
    public static void main(String[] args) {     
        //1  2  3  4  5  6  7
        int[][] adjMatrix = { {0, 1, 1, 0, 0, 0, 0},
                              {1, 0, 0, 1, 1, 1, 0},
                              {1, 0, 0, 0, 0, 0, 1},
                              {0, 1, 0, 0, 0, 0, 1},
                              {0, 1, 0, 0, 0, 0, 1},
                              {0, 1, 0, 0, 0, 0 ,0},
                              {0, 0, 1, 1, 1, 0, 0}  };

       new myGraphs(adjMatrix);
     }
}

Eine Tiefe-zuerst-Suche für was?
Seine Tiefe suchen für ein Diagramm.
Aber was sind Sie auf der Suche nach?
Sie sind gonna haben, um zu definieren, "Tiefe" hier. Durch meine Lektüre, die ich erwarten würde [1 2 4 7 3 5 6], seit 7 kann gehen, 3 und 5.
Der OP wollte sagen, Tiefe erste traversal.

InformationsquelleAutor TMan | 2011-11-11

graph java

Wenn Sie sind auf der Suche Depth-First-Traversal dann folgende code-änderungen, die Sie vornehmen sollten,

1) Zunächst deklarieren Sie Ihre Knoten-array als int[] node = {0, 1, 2, 3, 4, 5, 6}. Dies sollte getan werden, um zu vermeiden, array-index beginnen (also 0 ) und den Knoten start-Nummer (die 1). SO, hier nun gehen wir davon aus, dass die neuen Namen der Knoten 1 ist 0, die Knoten 2 ist 1......und Knoten 7 ist 6.

2) Statt das zu tun,

for (i = 1; i < node.length-1; i++){
     depthFirst(firstNode, node[i]);
 }

in myGraphs tun :
depthFirst(firstNode, 7);

3)In depthFirst statt for ( i=1;i<=n;i++) verwenden for ( i=0;i<n;i++) dabei System.aus.println Funktion depthFirst hinzufügen, um die Zahl als 0 steht für Knoten 1, 1 repräsentiert den Knoten 2 und so weiter.

Unten ist Ihre voll funktionsfähige code, den ich verändert :

import java.util.Stack;


public class DFS {

    Stack<Integer> st;
      int vFirst;

      int[][] adjMatrix;
      int[] isVisited = new int[7];

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[][] adjMatrix = { {0, 1, 1, 0, 0, 0, 0},
                {1, 0, 0, 1, 1, 1, 0},
                {1, 0, 0, 0, 0, 0, 1},
                {0, 1, 0, 0, 0, 0, 1},
                {0, 1, 0, 0, 0, 0, 1},
                {0, 1, 0, 0, 0, 0 ,0},
                {0, 0, 1, 1, 1, 0, 0}  };


      new DFS(adjMatrix);

    }

    public DFS(int[][] Matrix) {

         this.adjMatrix = Matrix;
         st = new Stack<Integer>();
         int i;
         int[] node = {0, 1, 2, 3, 4, 5, 6};
         int firstNode = node[0];
         depthFirst(firstNode, 7);



          }

          public void depthFirst(int vFirst,int n)
          {
          int v,i;

          st.push(vFirst);

          while(!st.isEmpty())
          {
              v = st.pop();
              if(isVisited[v]==0)
              {
                  System.out.print("\n"+(v+1));
                  isVisited[v]=1;
              }
              for ( i=0;i<n;i++)
              {
                  if((adjMatrix[v][i] == 1) && (isVisited[i] == 0))
                  {
                      st.push(v);
                      isVisited[i]=1;
                      System.out.print(" " + (i+1));
                      v = i;
                  }
              }
          }
}}

es funktionierte tatsächlich, wenn ich gerade geändert int[] Knoten 0-6. Neben firstnode ich wirklich brauchen noch nicht einmal den int [] - Knoten. Vielen Dank für die Hilfe.
Saurabh, ich habe gerade deinen code getestet und es ist Druck 1,2,4,7,5,6,3 statt 1, 2, 4, 7, 3, 5, 6. Können Sie bitte testen und bestätigen?

InformationsquelleAutor Saurabh

Eine funktionierende/getestete Lösung in C#, wenn jemand auf der Suche nach es.

using System;
using System.Collections.Generic;

namespace GraphAdjMatrixDemo
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //0  1  2  3  4  5  6
            int[,] matrix = {     {0, 1, 1, 0, 0, 0, 0},
                                  {1, 0, 0, 1, 1, 1, 0},
                                  {1, 0, 0, 0, 0, 0, 1},
                                  {0, 1, 0, 0, 0, 0, 1},
                                  {0, 1, 0, 0, 0, 0, 1},
                                  {0, 1, 0, 0, 0, 0 ,0},
                                  {0, 0, 1, 1, 1, 0, 0}  };

            bool[] visitMatrix = new bool[matrix.GetLength(0)];
            Program ghDemo = new Program();

            for (int lpRCnt = 0; lpRCnt < matrix.GetLength(0); lpRCnt++)
            {
                for (int lpCCnt = 0; lpCCnt < matrix.GetLength(1); lpCCnt++)
                {
                    Console.Write(string.Format(" {0}  ", matrix[lpRCnt, lpCCnt]));
                }
                Console.WriteLine();
            }

            Console.Write("\nDFS Recursive : ");
            ghDemo.DftRecursive(matrix, visitMatrix, 0);
            Console.Write("\nDFS Iterative : ");
            ghDemo.DftIterative(matrix, 0);

            Console.Read();
        }

        //====================================================================================================================================

        public void DftRecursive(int[,] srcMatrix, bool[] visitMatrix, int vertex)
        {
            visitMatrix[vertex] = true;
            Console.Write(vertex + 1 + "  ");

            for (int neighbour = 0; neighbour < srcMatrix.GetLength(0); neighbour++)
            {
                if (visitMatrix[neighbour] == false && srcMatrix[vertex, neighbour] == 1)
                {
                    DftRecursive(srcMatrix, visitMatrix, neighbour);
                }
            }
        }

        public void DftIterative(int[,] srcMatrix, int srcVertex)
        {
            bool[] visited = new bool[srcMatrix.GetLength(0)];

            Stack<int> vertexStack = new Stack<int>();
            vertexStack.Push(srcVertex);

            while (vertexStack.Count > 0)
            {
                int vertex = vertexStack.Pop();

                if (visited[vertex] == true)
                    continue;

                Console.Write(vertex + 1 + "  ");
                visited[vertex] = true;

                for (int neighbour = 0; neighbour < srcMatrix.GetLength(0); neighbour++) 
                //for (int neighbour = srcMatrix.GetLength(0) - 1; neighbour >= 0; neighbour--)//To make same as recursive
                {
                    if (srcMatrix[vertex, neighbour] == 1 && visited[neighbour] == false)
                    {
                        vertexStack.Push(neighbour);
                    }
                }
            }
        }
    }
}

Zu machen display, um iterative gleiche wie die Rekursion, die wir brauchen, um push-Nachbarn in der umgekehrten Reihenfolge zu stapeln. Nahm diese Logik von Amit Antwort hier

InformationsquelleAutor Sai

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.