深度最初のトラバースと調整マトリックス

Question

深度最初のトラバーサルをしようとしています。私は私が近くにいるかどうか分かりません。今すぐ印刷しています1 3 4 5。印刷する必要があります1 2 4 7 3 5 6.助けやアドバイスをいただければ幸いです。ありがとう。 :)

クラス：

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); 
} 

}

Answer 1

あなたは深さ優先トラバーサルを見ている場合は、以下ではまず宣言）コードを使用すると、

1をしなければならない変更でありますあなたのノード配列はint[] node = {0, 1, 2, 3, 4, 5, 6}です。これは、配列インデックス開始（0）とノード開始番号（1）を避けるために行う必要があります。 SO、ここで今、私たちはあなたのノード1の新しい名前は、ノード2が1で、0である......とノード7が6

2であると仮定）の代わりにmyGraphsに

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

をしています： depthFirst（firstNode、7）;

for (i=1;i<=n;i++)の代わりにのdepthFirstを使用します。depthFirst関数でSystem.out.printlnを実行しているときに、0がノード1を表し、1がノード2を表します。以下は

私は修正あなたの完全に機能コードは次のとおりです。C＃で

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; 
        } 
       } 
      } 
}} 

Answer 2

作業/テストソリューション、誰かがそれを探している場合。

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); 
        } 
       } 
      } 
     } 
    } 
} 

繰り返しの表示順序を再帰と同じにするには、隣接するものを逆順にスタックしてスタックする必要があります。 Amitからこのロジックを取った答えhere