Добрый день. У меня возникла следующая задача: Задан граф матрицей смежности. Необходимо найти в нём любой цикл, который проходит через две вершины и два ребра.
Я пытался сделать так: запускаю поиск в глубину от одной из требуемых вершин цикла, проверяю их на смежность сперва с рёбрами, а затем со второй вершиной. Каждую найденную вершину. Однако у меня не получается правильно реализовать это.
Прошу подсказать, как можно исправить следующий код (Edge - структура для ребра):
public void FindCycle(int vFirst, int vSecond, Edge eFirst, Edge eSecond)
{
nRez[i++] = vFirst;
//смежно с началом 1 ребра
if (nMatr[vFirst, eFirst.Begin] == 1 && !Edge1 && !nRez.Contains(eFirst.Begin))
{
nRez[i++] = eFirst.Begin;
nRez[i++] = eFirst.End;
Edge1 = true;
FindCycle(eFirst.End, vSecond, eFirst, eSecond);
}
//смежн с концом 1 ребра
else if (nMatr[vFirst, eFirst.End] == 1 && !Edge1 && !nRez.Contains(eFirst.End))
{
nRez[i++] = eFirst.End;
Edge1 = true;
FindCycle(eFirst.End, vSecond, eFirst, eSecond);
}
//смежно с началом 2 ребра
else if (nMatr[vFirst, eSecond.Begin] == 1 && !Edge2 && !nRez.Contains(eSecond.Begin))
{
nRez[i++] = eSecond.Begin;
//nRez[i++] = eSecond.End;
Edge2 = true;
FindCycle(eSecond.End, vSecond, eFirst, eSecond);
}
//смежно с концом 2 ребра
else if (nMatr[vFirst, eSecond.End] == 1 && !Edge2 && !nRez.Contains(eSecond.End))
{
// nRez[i++] = eSecond.End;
Edge2 = true;
FindCycle(eSecond.End, vSecond, eFirst, eSecond);
}
//смежно со второй вершиной
else if (nMatr[vFirst, vSecond] == 1 && !Vertex2 && !nRez.Contains(vSecond))
{
// nRez[i++] = vSecond;
Vertex2 = true;
FindCycle(eFirst.End, vSecond, eFirst, eSecond);
}
//хотим замкнуть
else if (nMatr[vFirst, nRez[0]] == 1 && Edge1 && Edge2 && Vertex2)
{
GraphCycleFoundException e = new GraphCycleFoundException();
nRez[i++] = nRez[0];
throw e;
}
//нет ничего из вышеперечисленного: пускаем в ближайшую смежную, отличную от начальной
else
{
for (int j = 0; j < nDimension; j++)
if (!nRez.Contains(j) && nMatr[vFirst, j] == 1)
FindCycle(j, vSecond, eFirst, eSecond);
}