今天有個(gè)朋友問(wèn)到深度遍歷圖這樣的問(wèn)題，開(kāi)始都不知道如何下手，就問(wèn)了問(wèn)baidu 和 google，看到有人用C++寫的這樣的例子，順便就學(xué)習(xí)了一下，發(fā)現(xiàn)自己都忘得差不多了（包括：數(shù)據(jù)結(jié)構(gòu)），只能聯(lián)想到剛開(kāi)始學(xué)vs2003的時(shí)候，學(xué)習(xí)的第一個(gè)Hello Worl的例子，要?jiǎng)?chuàng)建一個(gè)控制臺(tái)應(yīng)用程序。
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("深度遍歷結(jié)果：");
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;//最大頂點(diǎn)數(shù)
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 //初始添加點(diǎn)數(shù)
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("頂點(diǎn){0}不存在", startV);
88 if (end == -1) Console.WriteLine("頂點(diǎn){0}不存在", endV);
89 //權(quán)值默認(rèn)為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 //深度優(yōu)先遍歷
108 public void dfs()
109 {
110 vertexList[0].wasVisited = true;
111 displayVertex(0);
112 thestack.Push(0);
113 //遍歷結(jié)點(diǎn)
114 while (thestack.Count!=0)
115 {
116 //從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖 （讀取棧里的第一個(gè)元素，但是不出棧）
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 //元素進(jìn)棧
126 thestack.Push(v);
127 }
128 }
129 //初始化所有的頂點(diǎn)狀態(tài)為未被訪問(wèn)
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 }
143
