C#深度优先遍历结构算法

 N久都没做过关于C#的WinForm程序了，一直都是在研究asp.net的程序。

     今天有个朋友问到深度遍历图这样的问题，开始都不知道如何下手，就问了问baidu 和 google，看到有人用C++写的这样的例子，顺便就学习了一下，发现自己都忘得差不多了（包括：数据结构），只能联想到刚开始学vs2003的时候，学习的第一个Hello Worl的例子，要创建一个控制台应用程序。

     接着就打开VS2005，新建——>项目——>控制台应用程序

代码如下：

1. using System; 
2.  using System.Collections.Generic; 
3.  using System.Text; 
4.  using System.Collections; 
5.   
6.  namespace ConsoleApplication2 
7.  { 
8.      class Program 
9.      { 
10.          static void Main(string args) 
11.          { 
12.              Graph graph = new Graph(); 
13.              graph.addVertex('A'); 
14.              graph.addVertex('B'); 
15.              graph.addVertex('C'); 
16.              graph.addVertex('D'); 
17.              graph.addVertex('E'); 
18.              graph.addVertex('F'); 
19.              graph.addVertex('G'); 
20.              graph.addVertex('H'); 
21.              graph.addEdge('A', 'B'); 
22.              graph.addEdge('B', 'D'); 
23.              graph.addEdge('B', 'E'); 
24.              graph.addEdge('E', 'H'); 
25.              graph.addEdge('D', 'H'); 
26.              graph.addEdge('A', 'C'); 
27.              graph.addEdge('C', 'F'); 
28.              graph.addEdge('F', 'G'); 
29.              graph.addEdge('C', 'G'); 
30.              Console.Write("深度遍历结果："); 
31.              graph.dfs(); 
32.              Console.WriteLine(); 
33.          } 
34.      } 
35.   
36.      class Vertex 
37.      { 
38.          public Vertex(char label) 
39.          { 
40.              _label = label; 
41.              wasVisited = false; 
42.          } 
43.   
44.   
45.          public char _label; 
46.          public bool wasVisited; 
47.      } 
48.   
49.      class Graph 
50.      { 
51.          private static int flag = 1; 
52.          private int max_vertexs = 20;//最大顶点数 
53.          private Vertex vertexList; 
54.          private int[,] adjMat; 
55.          private int countVertexs; 
56.          private Stack thestack; 
57.          public Graph() 
58.          { 
59.              vertexList = new Vertex[max_vertexs]; 
60.              adjMat = new int[max_vertexs, max_vertexs]; 
61.              countVertexs = 0; 
62.              for (int j = 0; j < max_vertexs; j++) 
63.                  for (int k = 0; k < max_vertexs; k++) 
64.                      adjMat[j, k] = 0; 
65.              thestack = new Stack(max_vertexs); 
66.          } 
67.          //初始添加点数 
68.          public void addVertex(char label) 
69.          { 
70.              vertexList[countVertexs++] = new Vertex(label); 
71.          } 
72.   
73.          public void addEdge(int start, int end) 
74.          { 
75.              adjMat[start, end] = 1; 
76.              adjMat[end, start] = 1; 
77.          } 
78.   
79.          public void addEdge(char startV, char endV) 
80.          { 
81.              int start = -1, end = -1; 
82.              for (int i = 0; i < countVertexs; i++) 
83.              { 
84.                  if (startV == vertexList[i]._label) start = i; 
85.                  if (endV == vertexList[i]._label) end = i; 
86.              } 
87.              if (start == -1) Console.WriteLine("顶点{0}不存在", startV); 
88.              if (end == -1) Console.WriteLine("顶点{0}不存在", endV); 
89.              //权值默认为1  
90.              adjMat[start, end] = 1; 
91.              adjMat[end, start] = 1; 
92.          } 
93.   
94.          //显示字符 
95.          public void displayVertex(int v) 
96.          { 
97.              if (flag == 1) 
98.              { 
99.                  Console.Write(vertexList[v]._label); 
100.              } 
101.              else 
102.              { 
103.                  Console.Write("," + vertexList[v]._label); 
104.              } 
105.              flag++; 
106.          } 
107.          //深度优先遍历 
108.          public void dfs() 
109.          { 
110.              vertexList[0].wasVisited = true; 
111.              displayVertex(0); 
112.              thestack.Push(0); 
113.              //遍历结点 
114.              while (thestack.Count!=0) 
115.              { 
116.                  //从第v个顶点出发递归地深度优先遍历图  （读取栈里的第一个元素，但是不出栈） 
117.                  int v = getAdjUnvisitedVertex(Int32.Parse((thestack.Peek().ToString()))); 
118.                  if (v == -1) 
119.                      //元素出栈 
120.                      thestack.Pop(); 
121.                  else 
122.                  { 
123.                      vertexList[v].wasVisited = true; 
124.                      displayVertex(v); 
125.                      //元素进栈 
126.                      thestack.Push(v); 
127.                  } 
128.              } 
129.              //初始化所有的顶点状态为未被访问 
130.              for (int j = 0; j < countVertexs; j++) 
131.                  vertexList[j].wasVisited = false; 
132.          } 
133.   
134.          public int getAdjUnvisitedVertex(int v) 
135.          { 
136.              for (int j = 0; j < countVertexs; j++) 
137.                  if (adjMat[v, j] == 1 && vertexList[j].wasVisited == false) 
138.                      return j; 
139.              return -1; 
140.          } 
141.      } 
142.  } 

  结果如图：