Dlaczego mój w pocie czoła tworzony program nie zwraca żadnych wartości? Jego celem jest znalezienie w zadanym grafie cyklu hamiltona, jednak niezależnie od danych, output zawsze wydaje wartość "0". Błąd jest na pewno logiczny, jednak od wczoraj nie potrafię go dostrzec. Przedstawiam pliki programu:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace HamiltonCycle
{
class HamiltonCycle
{
public const int MAXV = 20;
public int n, m;
public List<int> q;
public List<int>[] L;
public List<string> output;
public bool[] visited;
public string buffer;
public int counter;
public HamiltonCycle()
{
this.L = new List<int>[MAXV + 1];
this.visited = new bool[MAXV + 1];
this.q = new List<int>();
this.output = new List<string>();
this.counter = 1;
}
public void DFSHamilton(int v)
{
//Add visited vertex to list
q.Add(v);
//If path have all vertex
if ( q.Capacity == n )
{
bool test = false;
//Looking for path
for ( List<int>.Enumerator i = L[v].GetEnumerator(); i.MoveNext(); )
{
//If exists edge from v to 1
if (i.Current == 1)
{
test = true;
break;
}
}
//Add to buffer number of founded path
if ( test )
{
this.buffer = this.counter.ToString() + ": ";
this.counter++;
}
//Add to buffer list of vertex from founded path
for ( List<int>.Enumerator i = q.GetEnumerator(); i.MoveNext(); )
{
this.buffer = this.buffer + i.Current + " -> ";
}
//Add to output list buffer content
this.output.Add(this.buffer);
this.buffer.Remove(0);
}
else
{
//In case, when path haven't all vertex
visited[v] = true;
L[v] = new List<int>();
//We visting not visited jet pathes
for (List<int>.Enumerator x = L[v].GetEnumerator(); x.MoveNext(); )
{
if( !visited[ x.Current ] ) { this.DFSHamilton( x.Current ); }
}
}
//Remove vertex from path
q.Remove(v);
}
public List<string> DFSHamiltonSearch()
{
q.Clear();
for (int j = 1; j <= this.n; j++ )
{
this.visited[j] = false;
}
this.DFSHamilton(1);
return this.output;
}
}
}
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace HamiltonCycle
{
public partial class Form1 : Form
{
private int v, w, y;
private int counter;
private int NumberVertex;
private int NumberEdge;
private List<int>[] connections;
private List<string> buffer;
private HamiltonCycle HCObj;
public Form1()
{
InitializeComponent();
}
private void Form1_Load(object sender, EventArgs e)
{
this.counter = 0;
this.HCObj = new HamiltonCycle();
this.connections = new List<int>[HamiltonCycle.MAXV];
}
private void txtNumberVertex_KeyPress(object sender, KeyPressEventArgs e)
{
int isNumber = 0;
e.Handled = !int.TryParse(e.KeyChar.ToString(), out isNumber);
}
private void txtNumberEdge_KeyPress(object sender, KeyPressEventArgs e)
{
int isNumber = 0;
e.Handled = !int.TryParse(e.KeyChar.ToString(), out isNumber);
}
private void btnClear_Click(object sender, EventArgs e)
{
txtNumberVertex.Text = null;
txtNumberEdge.Text = null;
}
private void btnStartTyping_Click(object sender, EventArgs e)
{
//If user doesn't enter any data
if (txtNumberVertex.Text == null || txtNumberEdge.Text == null)
{
MessageBox.Show("Nie wypełniłeś wszystkich pól!", "Niepoprawne dane:");
}
else
{
NumberVertex = Int32.Parse(txtNumberVertex.Text);
NumberEdge = Int32.Parse(txtNumberEdge.Text);
//If number of vertex or edges are less than zero
if (NumberVertex <= 0 || NumberEdge <= 0)
{
txtNumberVertex.Text = null;
txtNumberEdge.Text = null;
MessageBox.Show("Liczba wierzchołków i krawędzi nie może być ujemna!", "Niepoprawne dane:");
}
else
{
//Add to HCObj properties
this.HCObj.n = this.NumberVertex;
this.HCObj.m = this.NumberEdge;
int i;
//Make entries for listbox of vertex
for (i = 1; i <= NumberVertex; i++)
{
lstBoxVertexStart.Items.Add(i);
}
for (i = 1; i <= NumberVertex; i++ )
{
chkLstBoxVertex.Items.Add(i);
}
//Turn on connections add visibility
lstBoxVertexStart.Visible = true;
chkLstBoxVertex.Visible = true;
labelStartTyping.Visible = true;
btnAddConnection.Visible = true;
txtConnections.Visible = true;
}
}
}
private void btnAddConnection_Click(object sender, EventArgs e)
{
if((int)lstBoxVertexStart.SelectedItem == 0)
{
MessageBox.Show("Nie zaznaczyłeś początkowego wierzchołka!", "Niepoprawne dane");
}
else
{
this.v = (int)lstBoxVertexStart.SelectedItem;
foreach (object indexChecked in chkLstBoxVertex.CheckedIndices)
{
this.w = (int)indexChecked + 1;
//this.y = (int)indexChecked + 1;
txtConnections.Text = txtConnections.Text + this.v.ToString() + "-" + this.w.ToString() + ", ";
this.connections[this.v] = new List<int>();
this.connections[this.w] = new List<int>();
this.connections[this.v].Add(this.w);
this.connections[this.w].Add(this.v);
this.counter = this.counter + 1;
}
while (chkLstBoxVertex.CheckedIndices.Count > 0)
{
chkLstBoxVertex.SetItemChecked(chkLstBoxVertex.CheckedIndices[0], false);
}
lstBoxVertexStart.ClearSelected();
}
}
private void btnSearch_Click(object sender, EventArgs e)
{
if (this.counter != this.NumberEdge)
{
MessageBox.Show("Nie wprowadziłeś wystarczającej liczby krawędzi!", "Niepoprawne dane");
}
else
this.buffer = this.HCObj.DFSHamiltonSearch();
txtOutput.Text = this.buffer.Count.ToString();
for (int i = 0; i < this.buffer.Count; i++)
{
txtOutput.Text = txtOutput.Text + this.buffer[i];
}
}
}
}
}
Żeby nie było, program jest mojego autorstwa, nie jest tak, zerżnąłem go z zagranicznego serwisu i teraz nie potrafię go przerobić. Przy tworzeniu korzystałem jedynie z dostępnych w polskich serwisach algorytmów.