1 //1 使用邻接表 时间复杂度: O(n+e) 2 //递归 3 public void DFS(int v) 4 { 5     System.out.print(this.vexs[v].data + " "); 6     this.visited[v] = true; 7          8     for(ArcNode p = this.vexs[v].firstarc; p != null; p = p.nextarc) 9         if(this.visited[p.adjvex] == false)10             this.DFS(p.adjvex);11 }12 13 //迭代(借助栈)14 public void DFS(int v)15 {16     System.out.print(this.vexs[v].data + " ");17     this.visited[v] = true;18     Stack stack = new Stack();19     stack.push(vexs[v]);20     21     for(int i = 0; i < this.vexs.length; i++)22         this.vexs[i].next = this.vexs[i].firstarc;23     24     while(!stack.isEmpty())25     {26         VexNode q = stack.getTop();27         ArcNode p;28         for(p = q.next; p != null && this.visited[p.adjvex] == true; p = p.nextarc);29         if(p != null)30         {31             System.out.print(this.vexs[p.adjvex].data + " ");32             this.visited[p.adjvex] = true;33             stack.push(this.vexs[p.adjvex]);34             q.next = p.nextarc;35         }36         else37             stack.pop();38     }39 }

 

1 //使用邻接矩阵 时间复杂度: O(n^2) 2 //递归 3 public void DFS(int v)   4 { 5     System.out.print(this.vexs[v] + " "); 6     this.visited[v] = true; 7      8     for(int i = 0; i < this.vexnum; i++) 9         if(this.adjacencyMatrix[v][i] == 1 && this.visited[i] == false)10             this.DFS(i);11 }12 13 //迭代(借助栈)14 public void DFS(int v)15 {16     System.out.print(this.vexs[v] + " ");17     this.visited[v] = true;18     Stack stack = new Stack();19     stack.push(v);20     21     while(!stack.isEmpty())22     {23         v = stack.getTop();24         int i;25         for(i = 0; i < this.vexnum; i++)26             if(this.adjacencyMatrix[v][i] == 1 && this.visited[i] == false)27             {28                 System.out.print(this.vexs[i] + " ");29                 this.visited[i] = true;30                 stack.push(i);31                 break;32             }33         if(i == this.vexnum)34             stack.pop();35     }36 }