|
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 else
37 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 } 转载于:https://www.cnblogs.com/Huayra/p/10816415.html
|