Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <locale.h>
- #include <stdlib.h>
- // Константы для работы с графом
- #define MIN_N 2
- #define MAX_N 7
- #define FILENAME "input.txt"
- // Функция для ввода размера графа с клавиатуры
- void inputGraphSize(int* n) {
- printf_s("Введите количество вершин графа в диапазоне [%d; %d]: ", MIN_N, MAX_N);
- scanf_s("%d", n);
- }
- // Функция для проверки корректности размера графа
- int checkGraphSize(int n) {
- if (n < MIN_N || n > MAX_N) {
- printf_s("Ошибка: введенное значение n вне допустимого диапазона.\n");
- return 1; // Возврат с ошибкой
- }
- return 0; // Все в порядке
- }
- // Функция для создания матрицы смежности с клавиатуры
- void createAdjacencyMatrix(int n, int(*m1)[MAX_N]) {
- printf_s("Матрица смежности c размерностью %d x %d\n", n, n);
- for (int i = 0; i < n; i++) {
- for (int j = i; j < n; j++) {
- printf_s("m1[%d][%d] = ", i, j);
- scanf_s("%d", &m1[i][j]);
- m1[j][i] = m1[i][j];
- }
- }
- }
- // Функция для чтения матрицы смежности из файла
- void readAdjacencyMatrixFromFile(int n, int(*m1)[MAX_N]) {
- FILE* file;
- if (fopen_s(&file, FILENAME, "r") != 0) {
- printf_s("Ошибка открытия файла %s\n", FILENAME);
- exit(1);
- }
- for (int i = 0; i < n; i++) {
- for (int j = i; j < n; j++) {
- fscanf_s(file, "%d", &m1[i][j]);
- m1[j][i] = m1[i][j];
- }
- }
- fclose(file);
- }
- // Функция для вывода матрицы смежности на экран
- void printAdjacencyMatrix(int n, int(*m1)[MAX_N]) {
- printf_s("Вывод матрицы смежности m1\n");
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- printf_s("%d\t", m1[i][j]);
- }
- printf_s("\n");
- }
- }
- // Функция для подсчета количества рёбер в графе
- int countEdges(int n, int(*m1)[MAX_N]) {
- int k0 = 0;
- for (int i = 0; i < n - 1; i++) {
- for (int j = 0; j < n - 1; j++) {
- k0 += m1[i][j];
- }
- }
- return k0 / 2;
- }
- // Функция для подсчета связей каждой вершины
- void countVertexConnections(int n, int(*m1)[MAX_N], int* sum) {
- for (int j = 0; j < n - 1; j++) {
- sum[j] = 0;
- for (int i = 0; i < n - 1; i++) {
- sum[j] += m1[j][i];
- }
- }
- }
- // Функция для проверки связности графа
- int checkConnectivity(int n, int* sum) {
- int p = 0;
- for (int i = 0; i < n - 1; i++) {
- if (sum[i] == 0) {
- printf_s("Матрица несвязная\n");
- p++;
- }
- }
- return p;
- }
- // Функция для проверки, является ли граф деревом
- int isTree(int k, int n, int p) {
- return (k == n - 2 && p == 0);
- }
- // Главная функция программы
- int main() {
- setlocale(LC_ALL, "Russian");
- int n; // Переменная для хранения размера графа
- // Справка
- printf_s("\nАлгоритм работы программы:\n");
- printf_s("1. Пользователь выбирает источник данных: клавиатура или файл (input.txt).\n");
- printf_s("2. В зависимости от выбора, программа либо запрашивает ввод размера графа и матрицы смежности с клавиатуры,\n");
- printf_s(" либо считывает данные из файла input.txt.\n");
- printf_s("3. Программа выводит матрицу смежности.\n");
- printf_s("4. Программа выполняет проверку.\n");
- printf_s("5. Память, выделенная под матрицы, освобождается.\n");
- printf_s("\nАвтор: Павликова Екатерина, группа ПМИ-13\n");
- // Выбор источника данных (клавиатура или файл)
- printf_s("Выберите источник данных (1 - клавиатура, 2 - файл): ");
- int choice;
- scanf_s("%d", &choice);
- // Обработка выбора пользователя
- if (choice == 1) {
- // Ввод размера графа с клавиатуры
- inputGraphSize(&n);
- // Проверка корректности введенного размера графа
- if (checkGraphSize(n)) {
- return 1; // Возврат с ошибкой
- }
- }
- else if (choice == 2) {
- // Инициализация переменной n с использованием константного значения
- printf_s("Чтение данных из файла %s\n", FILENAME);
- FILE* file;
- if (fopen_s(&file, FILENAME, "r") != 0) {
- printf_s("Ошибка открытия файла %s\n", FILENAME);
- return 1; // Возврат с ошибкой
- }
- // Чтение размера графа из файла
- fscanf_s(file, "%d", &n);
- fclose(file);
- // Проверка корректности введенного размера графа
- if (checkGraphSize(n)) {
- return 1; // Возврат с ошибкой
- }
- }
- else {
- printf_s("Ошибка: неверный выбор источника данных.\n");
- return 1; // Возврат с ошибкой
- }
- // Выделение памяти под матрицу смежности
- int(*m1)[MAX_N] = malloc(MAX_N * sizeof(int[MAX_N]));
- // Проверка успешности выделения памяти
- if (m1 == NULL) {
- printf_s("Ошибка: не удалось выделить память для матрицы смежности.\n");
- return 1;
- }
- // Ввод или чтение матрицы смежности в зависимости от выбора пользователя
- if (choice == 1) {
- createAdjacencyMatrix(n, m1);
- }
- else if (choice == 2) {
- readAdjacencyMatrixFromFile(n, m1);
- }
- // Вывод матрицы смежности на экран
- printAdjacencyMatrix(n, m1);
- // Подсчет количества рёбер в графе
- int k = countEdges(n, m1);
- printf_s("В графе %d рёбер\n", k);
- // Массив для хранения связей каждой вершины
- int sum[MAX_N - 1];
- // Подсчет связей каждой вершины
- countVertexConnections(n, m1, sum);
- // Проверка связности графа
- int p = checkConnectivity(n, sum);
- // Проверка, является ли граф деревом
- if (isTree(k, n, p)) {
- printf_s("m1 является деревом\n\n");
- }
- else {
- printf_s("m1 не является деревом\n\n");
- }
- // Освобождение выделенной памяти
- free(m1);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement