Представить неориентированный граф (без петель) в виде матрицы смежности и вывести его на экран в виде списка смежности
Код насыщен комментариями
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;
}