Обход графа в глубину - C#
Формулировка задачи:
string [,]graph = new string[10,11];
graph[0, 0] = "a";
graph[0, 1] = "0"; //а
graph[0, 2] = "b";//b
graph[0, 3] = "c";//c
graph[0, 4] = "0";//d
graph[0, 5] = "0";//f
graph[0, 6] = "0";//g
graph[0, 7] = "0";//h
graph[0, 8] = "0";//r
graph[0, 9] = "0";//o
graph[0, 10] = "0";//p
graph[1, 0] = "b";
graph[1, 1] = "a"; //а
graph[1, 2] = "0";//b
graph[1, 3] = "c";//c
graph[1, 4] = "d";//d
graph[1, 5] = "f";//f
graph[1, 6] = "0";//g
graph[1, 7] = "0";//h
graph[1, 8] = "0";//r
graph[1, 9] = "0";//o
graph[1, 10] = "0";//p
graph[2, 0] = "c";
graph[2, 1] = "a"; //а
graph[2, 2] = "b";//b
graph[2, 3] = "0";//c
graph[2, 4] = "0";//d
graph[2, 5] = "f";//f
graph[2, 6] = "0";//g
graph[2, 7] = "0";//h
graph[2, 8] = "0";//r
graph[2, 9] = "0";//o
graph[2, 10] = "0";//p
graph[3, 0] = "d";
graph[3, 1] = "0"; //а
graph[3, 2] = "b";//b
graph[3, 3] = "0";//c
graph[3, 4] = "0";//d
graph[3, 5] = "f";//f
graph[3, 6] = "g";//g
graph[3, 7] = "0";//h
graph[3, 8] = "0";//r
graph[3, 9] = "0";//o
graph[3, 10] = "0";//p
graph[4, 0] = "f";
graph[4, 1] = "0"; //а
graph[4, 2] = "b";//b
graph[4, 3] = "c";//c
graph[4, 4] = "d";//d
graph[4, 5] = "0";//f
graph[4, 6] = "0";//g
graph[4, 7] = "0";//h
graph[4, 8] = "0";//r
graph[4, 9] = "0";//o
graph[4, 10] = "0";//p
graph[5, 0] = "g";
graph[5, 1] = "0"; //а
graph[5, 2] = "0";//b
graph[5, 3] = "0";//c
graph[5, 4] = "d";//d
graph[5, 5] = "0";//f
graph[5, 6] = "0";//g
graph[5, 7] = "h";//h
graph[5, 8] = "r";//r
graph[5, 9] = "0";//o
graph[5, 10] = "0";//p
graph[6, 0] = "h";
graph[6, 1] = "0"; //а
graph[6, 2] = "0";//b
graph[6, 3] = "0";//c
graph[6, 4] = "0";//d
graph[6, 5] = "0";//f
graph[6, 6] = "g";//g
graph[6, 7] = "0";//h
graph[6, 8] = "r";//r
graph[6, 9] = "0";//o
graph[6, 10] = "0";//p
graph[7, 0] = "r";
graph[7, 1] = "0"; //а
graph[7, 2] = "0";//b
graph[7, 3] = "0";//c
graph[7, 4] = "0";//d
graph[7, 5] = "0";//f
graph[7, 6] = "g";//g
graph[7, 7] = "h";//h
graph[7, 8] = "0";//r
graph[7, 9] = "o";//o
graph[7, 10] = "p";//p
graph[8, 0] = "o";
graph[8, 1] = "0"; //а
graph[8, 2] = "0";//b
graph[8, 3] = "0";//c
graph[8, 4] = "0";//d
graph[8, 5] = "0";//f
graph[8, 6] = "0";//g
graph[8, 7] = "0";//h
graph[8, 8] = "r";//r
graph[8, 9] = "0";//o
graph[8, 10] = "p";//p
graph[9, 0] = "p";
graph[9, 1] = "0"; //а
graph[9, 2] = "0";//b
graph[9, 3] = "0";//c
graph[9, 4] = "0";//d
graph[9, 5] = "0";//f
graph[9, 6] = "0";//g
graph[9, 7] = "0";//h
graph[9, 8] = "r";//r
graph[9, 9] = "o";//o
graph[9, 10] = "0";//p
int n = 0;
string zabor = "";
string verh = "";
string bfs_num = "";
string vmist = "";
string start = "";
textBox3.Text = "Внршина BFS-номер Черга";
start = Convert.ToString(textBox1.Text);
for (int i = 0; i <= 9; i++)
{
if (graph[i, 0] == start)
{
n++; //номер DFS
verh = graph[i, 0]; //зберігаємо імя початкової вершини
bfs_num = Convert.ToString(n); //dfs для виведення
vmist += graph[i, 0]; // стек
buf_i = i; //до якого елементу відноситься
zabor += verh;// в стрічку добавляєм нову заборонену вершину
}
}
textBox3.Text += Environment.NewLine + " " + verh + " " + bfs_num + " " + vmist;
while (vmist != "")
{
for (int i = buf_i, j = 1; j < 9; j++)
{
if (graph[i, j] != "0")
{
if (zabor.Contains(graph[i, j]) == false)
{
n++;
verh = graph[i, j];
bfs_num = Convert.ToString(n);
vmist += graph[i, j];
textBox3.Text += Environment.NewLine + " " + verh + " " + bfs_num + " " + vmist;
buf_i = j;
zabor += verh;
}
else
{
vmist = vmist.Substring(0,vmist.Length - 1);
buf_i = j;
/* int len = vmist.Length;
start =Convert.ToString(vmist[len]);
for (int k = 0; k <= 9; k++)
{
if (graph[k, 0] == start)
{
buf_i = i; //до якого елементу відноситься
}
}
*/
textBox3.Text += Environment.NewLine + " " + "-" + " " + "-"+ " " + vmist;
}
}
}
}
получилось в шир а не в глуб
Решение задачи: «Обход графа в глубину»
textual
Листинг программы
for (int i = 0; i <= 9; i++)
{
if (graph[i, 0] == start)
{
n++; //номер DFS
verh = graph[i, 0]; //зберігаємо імя початкової вершини
bfs_num = Convert.ToString(n); //dfs для виведення
vmist += graph[i, 0]; // стек
buf_i = i; //до якого елементу відноситься
zabor += verh;// в стрічку добавляєм нову заборонену вершину
}
}
textBox3.Text += Environment.NewLine + " " + verh + " " + bfs_num + " " + vmist;
DFS_visit(buf_i);