Форум программистов, компьютерный форум, киберфорум
Наши страницы
Qunero
Войти
Регистрация
Восстановить пароль
Оценить эту запись

Эйлеров цикл/цепь на C#

Запись от Qunero размещена 29.03.2019 в 16:04

Искал решение своей задачи по поиску цикла или цепи в графе. Написал программу на C#.
Входные данные: в папке с прогой должен быть файл input.txt вида:
3
0 1 1
1 0 1
1 1 0

Первая строка - кол-во вершин, далее - матрица смежности.
Выходные данные: файл output.txt вида:

Chain/Cycle
1 2 3 1

Chain - есть цепь, Cycle - есть цикл в графе. Вторая строка - путь.
Если нет ни того, ни другого, то тогда No.

Сама программа:
Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
 
namespace Эйлер.Индивидуалка
{
    class Program
    {
        static int Smezh(int[,] matrix, int a, int n)
        {
            int k = 0;
            for (int j = 0; j < n; j++)
            {
                if (matrix[a, j] == 1) k++;
            }
            return k;
        }
        static bool Stepeni_ostavshihsya_vershin(int[] v, int n)
        {
            int k = 0;
            for (int i = 0; i < n; i++)
            {
                if (v[i] > 0) k++;
            }
            if (k > 2) return false; else { return true; }
        }
 
        static void Main()
        {
            int nechet = 0; //показывает в графе кол-во нечетных вершин
            var stack = new Stack<int>();
            string[] Mass = File.ReadAllLines(@"input.txt", System.Text.Encoding.Default); //
            int n = Convert.ToInt32(Mass[0]);
            int[,] a = new int[n, n];
            for (int i = 0; i < Mass.Length; i++)
            {
 
                Console.WriteLine("{0,5}", Mass[i]);
 
            }
            int[,] matrix = new int[n, n];
            for (int p = 0; p < n; p++)
            {
                //удаляю пробелы и заножу символ как число в массив m
                int[] m = Mass[p + 1].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(s => int.Parse(s)).ToArray();
                for (int i = 0; i < m.Length; i++)
                {
                    matrix[p, i] = m[i]; //добавляю это число в двумерный массив
                }
            }
            Console.WriteLine("Матрица смежности:");
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    Console.Write("{0,5}", matrix[i, j]);
                }
                Console.WriteLine(" ");
            }
            int otvet_k = 0; //счетчик для добавления цепи
            var otvet = new Stack<int>();
            int[] v = new int[n]; //вершина-степень
            int[,] v_i = new int[n, n]; // вершина - другие вершины (проверка на смежность)
            int smezhnost = 0; // параметр для проверки на смежность вершин, т.е. если нарушена матрица, то =1 и вывод ошибки
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (matrix[i, j] == matrix[j, i]) //проверяю матрицу на адекватность
                    {
                        if (matrix[i, j] == 1)
                        {
                            v[i] += 1;
                        }
                    }
                    else
                    {
                        smezhnost = 1;
                    }
                }
                if (v[i] % 2 == 1) nechet++;
                if (v[i] == 0 || smezhnost == 1 || matrix[i, i] != 0) { Console.WriteLine("Граф несвязный. Или ошибка в матрице."); break; }
 
            }
            if (smezhnost != 1) Console.WriteLine($"Нечетных вершин - {nechet}");
            if (nechet > 2 || nechet == 1) Console.WriteLine("Нет ни цикла, ни цепи");
 
 
            int dlya_stacka = 0;
            if (nechet == 0) // пишем программу для нахождения цикла
            {
                //выберем стартовую вершину, например, будет 0.
                stack.Push(0);
                while (stack.Count > 0)
                {
                    if (v[dlya_stacka] == 0) { otvet.Push(stack.Pop()); } //когда пришли в вершину, где степень 0 - остается лишь вывести ответ
                    else
                    {//open
                        for (int j = 0; j < n; j++) //иначе будем проходить по смежным вершинам всегда
                        {
                            if (matrix[dlya_stacka, j] == 1 && !(v[j] == 1 && Smezh(matrix, dlya_stacka, n) > 1)) //Smezh - ищет кол-во смежных вершин
                            {
                                matrix[dlya_stacka, j] = 0; v[dlya_stacka] -= 1; v[j] -= 1; matrix[j, dlya_stacka] = 0; stack.Push(j); dlya_stacka = j;
                                break;
                            }
                        }//выше мы вычитаем степени у вершин ребра, убираем в матрице смежности "смежности".
 
                    }//close
 
                }
 
 
            }
            else
            {
                if (nechet == 2) // пишем для поиска цепи.
                {
                    int start = -1, end = -1;
                    //найдем вершину с нечетной степенью.
                    for (int i = 0; i < n; i++)
                    {
                        if (v[i] % 2 == 1)
                        {
                            if (start == -1) { start = i; }
                            else
                            {
                                if (end == -1) { end = i; }
                            }
                        }
                    }
                    //модифицируем алгоритм из поиска цикла
                    Console.WriteLine($"Старт - {start + 1}, konec - {end + 1}");
                    stack.Push(start);
                    while (stack.Count > 0)
                    {
                        if (v[dlya_stacka] == 0) { otvet.Push(stack.Pop()); } //когда пришли в вершину, где степень 0 - остается лишь вывести ответ
                        else
                        {//open
                            for (int j = 0; j < n; j++) //иначе будем проходить по смежным вершинам 
                            {
                                if (matrix[dlya_stacka, j] == 1 && !(v[j] == 1 && Smezh(matrix, dlya_stacka, n) > 1)) //Smezh - ищет кол-во смежных вершин
                                {
                                    matrix[dlya_stacka, j] = 0; v[dlya_stacka] -= 1; v[j] -= 1; matrix[j, dlya_stacka] = 0; stack.Push(j); dlya_stacka = j;
                                    break;
                                }
                            }//выше мы вычитаем степени у вершин ребра, убираем в матрице смежности "смежности".
 
                        }//close
 
                    }
 
 
                }
                
 
            }
            using (StreamWriter file = new StreamWriter(@"output.txt", false, System.Text.Encoding.Default))
            {
                if (nechet == 2)
                {
                    Console.WriteLine("Таким образом, у нас - цепь. Путь таков:");
                    file.WriteLine("Chain");
                    foreach (int number in otvet)
                    {
                        Console.Write(" ");
                        file.Write(" ");
                        Console.Write(number + 1); //вывод цикла.
                        file.Write(number + 1);
                    }
                }
                if (nechet == 0)
                {
                    Console.WriteLine("Таким образом, у нас - цикл. Путь таков:");
                    file.WriteLine("Cycle");
                    foreach (int number in otvet)
                    {
                        Console.Write(" ");
                        file.Write(" ");
                        Console.Write(number + 1); //вывод цикла.
                        file.Write(number + 1);
                    }
                }
                if (smezhnost == 1 || (nechet > 2 || nechet == 1))
                {
                    file.WriteLine("No.");
                }
            }
            Console.ReadKey();
        }
    }
}


Размещено в Без категории
Просмотров 216 Комментарии 1
Всего комментариев 1
Комментарии
  1. Старый комментарий
    По-моему, где-то в коде есть переменная, которая ни разу не использовалась.
    Я не претендую на суперкрутой алгоритм, код.
    Запись от Qunero размещена 29.03.2019 в 16:05 Qunero вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru