Why is there a problem with calculating the diameter of a graph?

Question

C++ / C#

There is a graph:

struct list {
    int data;
    int firstPeak;
    int secondPeak;
    list* next = 0;
};

struct graph {
    int data;
    list* List = new list;
};

Links are defined by a list of adjacent edges.

Here's how they are added:

void addEdgeRec(list*& List, int firstPeak, int secondPeak, int data) {
    if (List->next == 0) {
        List->data = data;
        List->firstPeak = firstPeak;
        List->secondPeak = secondPeak;
        List->next = new list;
        return;
    }
    addEdgeRec(List->next, firstPeak, secondPeak, data);
}

graph* addEdge(graph graph[], int firstPeak, int secondPeak, int data) {
    addEdgeRec(graph[firstPeak - 1].List, graph[firstPeak-1].data, graph[secondPeak-1].data, data);
    addEdgeRec(graph[secondPeak - 1].List, graph[secondPeak-1].data, graph[firstPeak - 1].data, data);
    return graph;
}

We need functions for calculating the diameter, those that I made according to my idea for some reason do not work as they should. Functions:

int findLength(list* List, int a, int counter = 0) {
    if (List->secondPeak == a) {
        return counter;
    }
    if (List->next == 0) {
        return counter;
    }
    return findLength(List->next, a, counter + 1);
}

int findMax(list * List, int size) {
    int* arr = new int[size];
    for (int a = 0; a < size; a++) {
        if (a == List->firstPeak) {
            arr[a] = 0;
            continue;
        }
        if (a == List->secondPeak) {
            arr[a] = 1;
            continue;
        }
        arr[a] = findLength(List, a);
    }
    int max = arr[0];
    for (int a = 1; a < size; a++) {
        if (arr[a] > max) {
            max = arr[a];
        }
    }
    return max;
}

int findDiameter(graph Graph[], int size) {
    int* arr = new int[size];
    for (int a = 0; a < size; a++) {
        arr[a] = findMax(Graph[a].List, size);
    }
    int max = arr[0];
    for (int a = 1; a < size; a++) {
        if (arr[a] > max) {
            max = arr[a];
        }
    }
    return max;
}

Input example (vertex 1, vertex 2, data):

1 2 0
2 3 0
3 4 0

The graph diameter is 3, and the program outputs 2.

Answer 1

First, your structure is very strange. In general, it is not clear what kind of peaks you have there, why when adding an edge, data is involved in the vertices.
Instead of your own lists, you store the edges in a vector. In terms of performance, it will be even faster due to locality. And adding a bunch of elements to the vector once works for linear complexity. But if you need your own implementation, then you always add to the beginning of the list. Because recursively finding the end of the list and adding there is a quadratic algorithm out of the blue.
Describe your algorithm in words, what should the findLength function do? Search for the position of a given element in a list?
It looks like you have a weighted graph, and the only way you can in such a graph is to find the shortest paths from each vertex to each. This is where the algorithm fits in.Floyd . Or, if your graph is discharged - Dijkstra .