Найти все полные четырех вершинные Подграфы заданного графа

@Go0dwIND · Регистрация: 30.04.2014

Author24 — интернет-сервис помощи студентам

Доброе время суток ! Я первокурсник , первый раз пишу курсовую работу и так получилось что нет возможности попросить помощи у преподавателя так что решил обратиться с некоторыми вопросами сюда.
Задача : Дан Граф , Найти все полные четырех вершинные Подграфы.

Горе пополам оформил ввод , пытался оптимизировать но чет не получилось, костыль на костыле и решил пока оставить так и идти дальше, то есть к самому обходу и тут встал порос как будет лучше.
Дело в том что по определению полного графа степень вершины равна n -1. Т.к у меня 4 вершины понятно что степень равна 3. Сначала подумал с начало пройтись по графу и проверить на кол-во смежных вершин. тем самым если в какой либо меньше 3 то заходить в нее и смотреть смежные ей и в них удалять эту вершину. Потом думал сделать просто обход всего графа прыгая от смежной вершины к смежной пока не насчитаю 4 и закидывать их в масив потом проверять в каждой смежна ли она с тремя предыдущими. Проблема вся в том что мыслей много но боюсь сделать плохо так как зная препода , он мужик хороший , просто всегда говорит что штаны через голову возможно одеть но зачем и просит оптимизации! Заранее Благодарен тем кто откликнется

C

#include <stdio.h>
 
struct adjacency
{
    int vertex;
    adjacency *next;
};
 
struct list_graph
{
    adjacency *vertex_top;
    list_graph *next;
};
 
int is_empty(list_graph *graph)
{
    if (graph == NULL) return 1;
    return 0;
}
 
void max_min(int &elem_max, int &elem_min) 
{
    if (elem_max < elem_min)
    {
        int i;
        i = elem_max;
        elem_max = elem_min;
        elem_min = i;
    }
}
 
void create_graph(list_graph *graph)
{
    graph = new list_graph;
    graph->vertex_top = new adjacency;
}
 
list_graph *print_graph(list_graph *graph, FILE *input)
{
    list_graph *current_vertex;
    adjacency *current_adjacency;
    int elem_max = 0;
    int elem_min = 0;
    graph = new list_graph;
    graph->next = NULL;
    graph->vertex_top = new adjacency;
    graph->vertex_top->vertex = NULL;
    current_vertex = graph;
    while (fscanf_s(input, "%d%d", &elem_max, &elem_min) != EOF)
    {
        max_min(elem_max, elem_min);
        for (int i = 1; i <= elem_min; i++)
        {
            if (i == elem_min)
            {
                int k = 0;
                current_adjacency = current_vertex->vertex_top;
                while (k != 1)
                {
                    if (current_adjacency->vertex == NULL)
                    {
                        current_adjacency->vertex = elem_max;
                        current_adjacency->next = NULL;
                        current_vertex = graph;
                        k++;
                    }
 
                    else
                    {
                        if (current_adjacency->next == NULL)
                        {
                            current_adjacency->next = new adjacency;
                            current_adjacency->next->vertex = elem_max;
                            current_adjacency->next->next = NULL;
                            current_vertex = graph;
                            k++;
                        }
 
                        else
                        {
                            current_adjacency = current_adjacency->next;
                        }
                    }
                }
            }
 
            else
            {
                if (current_vertex->next == NULL)
                {
                    current_vertex->next = new list_graph;
                    current_vertex->next->vertex_top = new adjacency;
                    current_vertex->next->vertex_top->vertex = NULL;
                    current_vertex = current_vertex->next;
                    current_vertex->next = NULL;
                }
                else
                {
                    current_vertex = current_vertex->next;
                }
            }
        }
 
        for (int j = 1; j <= elem_max; j++)
        {
            if (j == elem_max)
            {
                int k = 0;
                current_adjacency = current_vertex->vertex_top;
                while (k != 1)
                {
                    if (current_adjacency->vertex == NULL)
                    {
                        current_adjacency->vertex = elem_min;
                        current_adjacency->next = NULL;
                        current_vertex = graph;
                        k++;
                    }
 
                    else
                    {
                        if (current_adjacency->next == NULL)
                        {
                            current_adjacency->next = new adjacency;
                            current_adjacency->next->vertex = elem_min;
                            current_adjacency->next->next = NULL;
                            current_vertex = graph;
                            k++;
                        }
 
                        else
                        {
                            current_adjacency = current_adjacency->next;
                        }
                    }
                }
            }
 
            else
            {
                if (current_vertex->next == NULL)
                {
                    current_vertex->next = new list_graph;
                    current_vertex->next->vertex_top = new adjacency;
                    current_vertex->next->vertex_top->vertex = NULL;
                    current_vertex = current_vertex->next;
                    current_vertex->next = NULL;
                }
                else
                {
                    current_vertex = current_vertex->next;
                }
            }
        }
 
    }
    return graph;
}

@Go0dwIND · 06.05.2014, 10:49 **[ТС]**

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

@Go0dwIND 0 / 0 / 0 Регистрация: 30.04.2014 Сообщений: 5
	06.05.2014, 10:49 [ТС]	2
	Убрал подпрограмму удаления смежных вершин , так как сказали что нельзя изменять граф! 0