深度優先遍歷和調整矩陣

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）。所以在這裏，現在我們假設你的節點1的新名稱爲0，節點2爲1 ......和節點7是6

2）代替myGraphs做

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

做： depthFirst（firstNode，7）;

3）深入第一，而不是for (i=1;i<=n;i++)使用for (i=0;i<n;i++)在函數depthFirst中執行System.out.println時，將數字加1，因爲0代表節點1，1代表節點2等等。

下面是你的全功能的代碼，我修改：

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

一個工作/在C＃中測試的解決方案，如果有人找它。

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