CODEWITHSUNDEEP
javaalgorithmcode-analysiscode-complexity
Lucas Moura
Lucas Moura

Reputation: 38

Complexity of this simple algorithm

I did a algorithm to resolve a problem, but I don't know its complexity. The algorithm verifies if all of the vertex of a graph are "good". A "good" vertex is a vertex that can access all others vertexes of a graph following a path that started himself.

public static boolean verify(Graph graph)
{
    for(int i=0; i < graph.getVertex().size(); i++)
    {
        // List of vertexes visited 
        ArrayList<Character> accessibleVertex = new ArrayList<Character>();
        getChildren(graph.getVertex().get(i), graph.getVertex().get(i).getName(), accessibleVertex);    

        // If the count of vertex without father equals a count of the list of vertexes visited, his is a "good" vertex
        if((graph.getVertex().size()-1) == accessibleVertex.size())
            return true;
    }

    return false;
}

private static void getChildren(Vertex vertex, char fatherName, ArrayList<Character> accessibleVertex)
{
    // Ignore the 'father'
    if(vertex.getName() != fatherName)
        addIfUnique(vertex.getName(), accessibleVertex);

    for(int i=0; i < vertex.getEdges().size(); i++)
    {
        getChildren(vertex.getEdges().get(i).otherVertex(), fatherName, accessibleVertex);
    }
}

private static void addIfUnique(char name, ArrayList<Character> accessibleVertex)
{
    boolean uniqueVertex = true;

    for(int i=0; i < accessibleVertex.size(); i++)
    {
        if(accessibleVertex.get(i).equals(name))
            uniqueVertex = false;
    }

    if(uniqueVertex)
        accessibleVertex.add(name);
}

Graph tested

Thanks and sorry for my english.

Upvotes: 1

Views: 82

Answers (1)

Simone C.
Simone C.

Reputation: 369

I think the complexity is O(n^2), because you use a nested loop by calling:

getChildren(graph.getVertex().get(i), graph.getVertex().get(i).getName(), accessibleVertex);

Upvotes: 2

Related Questions