Good day. I had the following task: The graph is given by the adjacency matrix. It is necessary to find in it any cycle that passes through two vertices and two edges.

I tried to do this: I run a search in depth from one of the required vertices of the cycle, check them for adjacency first with the edges, and then with the second vertex. Every vertex found. However, I can not properly implement it.

Please tell me how to fix the following code (Edge is a structure for an 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); }

    1 answer 1

    Sorry, did not read your code (it’s a lot of it!). I would suggest the following algorithm:

    1. Find the path from the first given vertex to the second through the first given edge; if there is no such way, the task is impossible.
    2. Find the path from the first given vertex to the second through the second given edge; if there is no such way, the task is impossible.
    3. Invert the second path, connect with the first, it will be a cycle

    In order to find a path from the first given vertex to the second through some edge, use the following subroutine:

    1. Find some path from the first given vertex to the first vertex of the edge and some path from the second vertex of the edge to the second specified vertex; if there are paths, glue them into the result and exit
    2. Find some path from the first given vertex to the second vertex of the edge and some path from the first vertex of the edge to the second specified vertex; if there are paths, glue them into the result and exit
    3. Otherwise, there is no such way.

    To search for a path from one to another, I would use the search in width (and not in depth), but that's how you like it.