По-моему у вас рекурсия организована не совсем верно. Дело в том, что
r передаётся по ссылке во все ветви поиска. И если одна из этих ветвей завершается успешно,
r обнуляется, тем самым сбрасывая конкурирующие пути. Кроме того и в цикле поиска
r так же должна всегда содержать тоже самое (т е путь до текущей вершины
v. Но в вашем коде это не так, потому что
r будет меняться внутри рекурсивного вызова.
Я не уверен, что всё остальное правильно, но я бы поменял:
dfs(a, ref visited, n, i, x, ref cnt, ref p, ref r);
на
dfs(a, ref visited, n, i, x, ref cnt, ref p, r.ToArray());
И соответственно ref убрал бы из определения dfs. Так при переходе по всем вершинам путям в цикле будет для каждого пути создана своя копия
r. Так же в этом случае не нужен
r.Remove(v + 1); и
r = new List();
Вообще передача большого количества аргументов по ссылке не очень хорошее решение с архитектурной точки зрения. Вам стоит подумать как организовать код так, что бы рекурсивная функция была "чистой" - т е её вызов с одними и теми же параметрами всегда приводил бы к одному результату. Умение писать в таком стиле сильно уменьшает вероятность ошибки.
Update:
По просьбе
Michail7 привожу свой вариант решения:
class Program
{
public struct Path {
public List<int> Vertexes { readonly get; private set; }
public Path(int vertex) {
this.Vertexes = new List<int>();
this.Vertexes.Add(vertex);
}
public Path(List<int> vertexes, int vertex) {
if (vertexes != null) {
this.Vertexes = new List<int>(vertexes);
}
else {
this.Vertexes = new List<int>();
}
this.Vertexes.Add(vertex);
}
public Path Add(int vertex) {
Path p = new Path(this.Vertexes, vertex);
return p;
}
public bool hasVertex(int vertex) {
return Vertexes.Contains(vertex);
}
public int LastVertex() {
return Vertexes.Last();
}
}
public static List<Path> RunDfs(in int[,] graph, int n, in Path currentPath, int targetVertex) {
int currentVertex = currentPath.LastVertex();
if (currentVertex == targetVertex) {
return new List<Path> { currentPath };
}
else {
List<Path> result = new List<Path>();
for (int i = 0; i < n; i++) {
if (graph[currentVertex,i] == 1 && ! currentPath.hasVertex(i) ) {
List<Path> newPaths = RunDfs(graph, n, currentPath.Add(i), targetVertex );
result.AddRange(newPaths);
}
}
return result;
}
}
static void Main(string[] args) {
int[,] graph = { {0,1,1,0},{0,0,0,1},{0,1,0,0}, {0,0,0,0}};
Path curPath = new Path().Add(0);
List<Path> paths = RunDfs(graph, 4, curPath, 3);
Console.WriteLine("Hello World!");
}
Его наверняка можно улучшить. И не факт, что он по скорости выиграет. Но. В нём сведено к миниму количество параметров и метод RunDfs является "чистым" в том понятии, что для одинакового входа он всегда выдаёт тот же выход и не имеет сайд-эффектов в виде записи в передаваемые структуры. Единственное, что я не стал оптимизировать - это передачу графа в виде двумерного массива. Очевидно для настоящих больших графов так оставлять нельзя, т к есть вероятность, что компиллятор всё же решит его копировать по значению, несмотря на то, что запись внутри RunDfs в него не происходит. (Это наверное можно проверить, делая бенчмарки по времени на графе достаточного размера и сравнив версию, где граф передаётся через ref) Но правильнее и проще для графа также ввести какую то структуру или даже класс, который будет передаваться по ссылке, но при этом не будет давать себя менять.
