Самая интересная информация только у нас!
Графы.Матрица смежности и списки смежности - Форум
Меню сайта

Форма входа

Поиск

Наш опрос
Оцените мой сайт
Всего ответов: 30

Статистика

Приветствую Вас, Гость · RSS 18.02.2018, 10:14

[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
Страница 1 из 11
Модератор форума: DenzeL 
Форум » Мир IT технологий » Языки прграммирования » Графы.Матрица смежности и списки смежности (C++)
Графы.Матрица смежности и списки смежности
ХиМиКДата: Четверг, 25.11.2010, 13:26 | Сообщение # 1
Злобный циник
Группа: Администратор
Сообщений: 339
Статус:
Представить неориентированный граф (без петель) в виде матрицы смежности и вывести его на экран в виде списка смежности
Код насыщен комментариями

Code
#include <stdio.h>
#include <conio.h>
#include <locale.h>
int main ()
{
     setlocale(LC_ALL, "russian");

     int numtop = 0,    //    Количество вершин графа
         top1 = 0,     // Для ввода вершин
         top2 = 0;    // Для ввода вершин

     printf ("Введите количество вершин графа >: ");
     scanf ("%d", &numtop);

     //    Создание двумерного массива - матрицы смежности
     int **AdjacencyMatrix = new int*[numtop];
     for (int i = 0 ; i < numtop ; i++)  
         AdjacencyMatrix[i] = new int[numtop];

     //    Заполнение матрицы смежности нулями
     for (int i=0; i<numtop; i++)
     {
         for (int j=0; j<numtop; j++)
             AdjacencyMatrix[i][j]=0;    
     }

     //    Ввод списка ребер
     /*     
     Как вводить ребра: На запрос вводим пару чисел (через пробел),     которые обозначают вершины соединенные ребром.  
     Например пара чисел "2 6" означает что вершина 2 соединена с вершиной 6  
     (и наоборот, т.к. программа написана для неориентированного графа)
     Заметьте, нумерация вершин начинается с нуля. Т.е. если у вас граф с тремя вершинами, то его вершины - 0, 1 и 2.
     Программа будет бесконечно запрашивать от вас ребра.
     Что бы прекратить ввод, на очередной запрос надо ввести хотя бы одну несуществующую вершину.
     Например если ваш граф содержит три вершины, то любой вариант ввода следующих пар чисел:
     0 5
     7 2
     8 95
     сообщит программе о том, что вы больше не хотите вводить ребра. Этот последний ввод не будет учтен.
      
     После того как программа получит от вас пару чисел, она будет считать их координатами массива в которые нужно записать единицы
     Причем первое число сначала будет считаться координатой строки, а затем координатой столбца. Так же для второго числа, только наоборот.
     Это нужно для создания симметричной матрицы, т.к. граф неориентированный
     */
     printf ("Введите список ребер: \n");
     printf ("Для прекращения ввода на очередной запрос введите несуществующие вершины \n");
     while (1)
     {
         printf (">: ");
         scanf ("%d%d", &top1, &top2);
         if (top1<numtop && top2<numtop)
         {
             AdjacencyMatrix[top1][top2]=1;
             AdjacencyMatrix[top2][top1]=1;
         }
         else  
             break;
     }

     //    Вывод на экран матрицы смежности  
     printf ("\nМатрица смежности:\n");
     for (int i=0; i<numtop; i++)  
     {
         for (int j=0; j<numtop; j++)
             printf ("%2d", AdjacencyMatrix[i][j]);
         printf ("\n");
     }
      
     //    Вывод списка смежности
     /*
     Программа фиксирует строку, выводит её номер в качестве вершины и ищет все вхождения единиц в этой строке.  
     Как находит единицу, выводит на экран номер столбца в котором содержится единица в данной строке, и так до конца строки.  
     Затем фиксируется вторая строка и все повторяется по новой.
     */
     printf ("Список смежности:\n");
     for (int i=0; i<numtop; i++)  
     {     
         printf ("Вершина %d: ",i);
          
         for (int j=0; j<numtop; j++)
         {
             if (AdjacencyMatrix[i][j]==1) printf (" %d,",j);
         }
         printf ("\n ");
     }
      
     getch ();
     return 0;
}
 
ШкололоДата: Пятница, 10.12.2010, 15:12 | Сообщение # 2
Новичок
Группа: Пользователь
Сообщений: 2
Статус:
Ололололо а че не подписали аффтара а? Не порядок! Этот код, равно как и комменты к нему написал я, прошу засвидетельствовать, и сохранить в анале истории

Шучу конечно, весь свой код я распространяю бесплатно, ибо он все равно никому не нужен biggrin

Сообщение отредактировал Школоло - Пятница, 10.12.2010, 15:20
 
ХиМиКДата: Суббота, 11.12.2010, 19:44 | Сообщение # 3
Злобный циник
Группа: Администратор
Сообщений: 339
Статус:
Quote (Школоло)
лолололо а че не подписали аффтара а? Не порядок! Этот код, равно как и комменты к нему написал я, прошу засвидетельствовать, и сохранить в анале истории

Шучу конечно, весь свой код я распространяю бесплатно, ибо он все равно никому не нужен biggrin

Ну код я нарезал у своего одногруппника, так что насчет авторства - не докажешь)

 
ШкололоДата: Воскресенье, 12.12.2010, 17:06 | Сообщение # 4
Новичок
Группа: Пользователь
Сообщений: 2
Статус:
Докажу, так как я и есть этот одногруппник, сижу обычно на первой парте 1 ряда от окна, стараюсь записывать лекции на диктофон, недавно получил повестку из военкомата... Никого не напоминает? biggrin

Сообщение отредактировал Школоло - Воскресенье, 12.12.2010, 17:08
 
ХиМиКДата: Среда, 22.12.2010, 19:04 | Сообщение # 5
Злобный циник
Группа: Администратор
Сообщений: 339
Статус:
Школоло, ты на меня еще в суд подай за распространение кода smile
 
Форум » Мир IT технологий » Языки прграммирования » Графы.Матрица смежности и списки смежности (C++)
Страница 1 из 11
Поиск:


Copyright MyCorp © 2018