Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 110 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова .
// структура графа в виде списка (массива) ребер
struct Graph3
{
int n; // количество вершин графа
int m; // количество ребер графа
Edge * edges; // массив элементов типа Edge
};
// граф в виде списков смежности
// структура одного элемента списка,
// хранящего номер смежной вершины
struct ElementList
{
int number; // номер вершины
ElementList* next;// адрес следующего элемента списка
};
// структура графа в виде списков смежности
struct Graph4
{
int n; // количество вершин графа
int m; // количество ребер графа
ElementList** nodes; // массив, содержащий списки
// смежных вершин
};
Далее приводится описание процесса решения некоторых задач с при-
менением пользовательских функций.
Задача 1. Дан граф в виде списка ребер. Преобразовать граф в матрицу
смежности.
Сначала выделяем память под матрицу смежности. Первоначально запол-
няем все ее элементы нулями. Проходя по всем ребрам из массива, заполняем
элементы матрицы единицами, исходя из номеров начальной и конечной вер-
шин ребра.
// определение функции преобразования представления графа
// из массива дуг в матрицу смежности
void Preobr32(Graph3& g1, Graph2& g2)
{
int i,j;
g2.n=g1.n; g2.m=g1.m;
// выделение памяти под матрицу смежности
110
А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                   .
    // структура графа в виде списка (массива) ребер
    struct Graph3
    {
          int n;        // количество вершин графа
          int m;        // количество ребер графа
          Edge * edges; // массив элементов типа Edge
    };

    // граф в виде списков смежности

    // структура одного элемента списка,
    // хранящего номер смежной вершины
    struct ElementList
    {
          int number;       // номер вершины
          ElementList* next;// адрес следующего элемента списка
    };

    // структура графа в виде списков смежности
    struct Graph4
    {
          int n;               // количество вершин графа
          int m;               // количество ребер графа
          ElementList** nodes; // массив, содержащий списки
                               // смежных вершин
    };


    Далее приводится описание процесса решения некоторых задач с при-
менением пользовательских функций.
    Задача 1. Дан граф в виде списка ребер. Преобразовать граф в матрицу
смежности.
    Сначала выделяем память под матрицу смежности. Первоначально запол-
няем все ее элементы нулями. Проходя по всем ребрам из массива, заполняем
элементы матрицы единицами, исходя из номеров начальной и конечной вер-
шин ребра.
    // определение функции преобразования представления графа
    // из массива дуг в матрицу смежности
    void Preobr32(Graph3& g1, Graph2& g2)
    {
          int i,j;
          g2.n=g1.n; g2.m=g1.m;
          // выделение памяти под матрицу смежности


                                           110

Страницы