Изоморфные графы C++?

---

Мой инструктор сказал моему классу, что мы должны написать программу, которая проверяет, являются ли два графика изоморфными. Я не прошу код, просто хотел получить некоторые идеи по алгоритмам. Как именно я могу проверить, изоморфны ли два графика?

От чтения дальше Википедия два графа изоморфны, если они являются перестановками друг друга. Представьте себе график в виде связки бусин, Соединенных нитками. Если бы я мог перемещать бусины, не меняя количество бусин или нитей, или как они связаны, то новый" граф " был бы изоморфен старому.

Это то, что у меня есть до сих пор (я опустил код в большинстве функций):

struct Vertex
{
    char ID;
    std::vector<Vertex*> adjacents;
    void addAdjacent(Vertex *v);
    unsigned int numAdjacent() const { return this->adjacents.size(); }
};

class Graph
{
private:
    std::vector<Vertex*> vertices;
    std::vector< std::pair<Vertex*, Vertex*> > edges;
    //going to use this to sort the list of vertices
    static bool compareVertices(const Vertex *a, const Vertex *b)
    {
        return (a->numAdjacent() < b->numAdjacent());
    }
public:
    //mutators
    void addVertex(Vertex *v);
    void addVertex(char c);
    void addEdge(std::pair<Vertex*, Vertex*> p);
    void addEdge(Vertex* a, Vertex* b);
    void addEdge(char a, char b);
    void sortVertices()    { std::sort(vertices.begin(), vertices.end(), compareVertices); }
    //accessors
    unsigned int numVertices() const { return this->vertices.size(); }
    unsigned int numEdges() const { return this->edges.size(); }
    Vertex* getVertex(unsigned int i) { return vertices[i]; }
};


bool areIsomorphic(Graph &a, Graph &b)
{
    if (a.numVertices() != b.numVertices())
        return false;
    if (a.numEdges() != b.numEdges())
        return false;
    a.sortVertices();
    b.sortVertices();
    for (unsigned int i = 0; i < a.numVertices(); ++i)
    {
        if (a.getVertex(i)->numAdjacent() != b.getVertex(i)->numAdjacent())
            return false;
    }
    return true;
}

Что я уже пробовал:

Поэтому я проверил, что у них одинаковое количество вершин и ребер, и что есть такое же количество вершин, которые связаны с определенным количеством других вершин.

Что дальше? Я могу думать только о том, чтобы пройти через вершины одну за другой и проверить все их связи. Но я не совсем уверен, как это сделать.

Что делать, если я создам третий граф в функции, а затем назначу ему все ребра из графа B, но используя идентификаторы вершин в графе A (в зависимости от numAdjacent() вершины из графа A и вершины из графа B)?

---