Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.74/34: Рейтинг темы: голосов - 34, средняя оценка - 4.74
0 / 0 / 0
Регистрация: 25.10.2017
Сообщений: 10
1

Из списка смежности в матрицу смежности. Выполнить обход графа глубину

26.02.2018, 16:38. Показов 6998. Ответов 1
Метки нет (Все метки)

Помогите пожалуйста с программой:
Дан список смежности. Преобразовать в матрицу смежности. Выполнить обход графа в глубину.
Заранее спасибо.
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.02.2018, 16:38
Ответы с готовыми решениями:

Вывести матрицу смежности и список смежности графа
Всем привет!! Уважаемые форумчане, помогите плиз с заданием! Я написала код в Си по которому...

Преобразование списка смежности в матрицу смежности
Помогите пожалуйста, нужно разработать алгоритм преобразования списка смежности в матрицу...

Матрица смежности графа - поиск в глубину
Здравствуйте дорогие форумчане. У меня тут небольшая ошибка. Никак не могу понять что к чему....

Список смежности и обход графа в ширину
нужно создать список смежности и пройти граф в ширину. как с помощью struct{}; создать список...

1
134 / 130 / 107
Регистрация: 17.03.2009
Сообщений: 364
28.02.2018, 17:02 2
Вот программа, она работает. На всякий рефакторинг времени не было.

Теоретический материал доступен здесь:
http://shpargalum.ru/shpora-go... ubinu.html


Код:

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace ConsoleApplication1
{
 
 
    public class Program
    {
 
        /// <summary>
        /// Преобразует списко смежности в матрицу смежности
        /// </summary>
        /// <param name="list"></param>
        /// <returns></returns>
        public static int[,] AjancenyListToMatr(int[][]list)
        {
            var length = 0;
            foreach(var item in list) {
                length++;
            };
            var result = new int[length, length];
            var i = -1;
            foreach (var row in list)
            {
                i++;
                foreach (var j in row)
                {
                    result[i, j] = result[j, i] = 1;
 
                }
            };
 
 
            return result;
        }
 
 
        /// <summary>
        /// Осуществляет поиск в глубину
        /// </summary>
        /// <param name="index"></param>
        /// <param name="_matr"></param>
        /// <returns></returns>
        public static HashSet<int> SearchInDepth(int index, int[,] _matr)
        {
            var list = new HashSet<int>();
            list.Add(index);
            for (int j = 0; j < _matr.GetLength(1); j++)
            {
                if (_matr[index, j] == 1)
                {
                    _matr[index, j] = _matr[j, index] = 0;
                    list.UnionWith(SearchInDepth(j, _matr));
 
                }
            }
            return list;
        }
 
        public static void Main(string[] args)
        {
            //Задаем граф в виде списка смежности
            int[][] adjacencyList = new int[][]
            {
               new int[] {1, 1, 1, 1},
               new int[] {0, 4},
               new int[] {0, 3},
               new int[] {0, 2},
               new int[] {0, 1}
            };
 
            
            //Печать списка смежности
            PrintAdjacencyList(adjacencyList);
            
            //Преобразуем список смежности в матрицу смежности
            var matr = AjancenyListToMatr(adjacencyList);
 
            PrintMatr(matr); //Печать матрицы смежности 
 
            //Осуществляем поиск в глубину
            var result = SearchInDepth(1, matr);
 
           
            
            //Печать списка прохождения вершин
            PrintSearchInDepthResult(result);
 
            Console.ReadKey();
        }
 
        private static void PrintAdjacencyList(int[][] adjacencyList)
        {
            var i = 0;
            foreach (var row in adjacencyList)
            {
                Console.Write(i + " ");
                foreach (var j in row)
                {
                    Console.Write(j + " ");
                }
                Console.WriteLine();
                i++;
            };
        }
 
        private static void PrintSearchInDepthResult(HashSet<int> result)
        {
            Console.WriteLine();
            Console.WriteLine();
            Console.WriteLine(String.Join(" ", result));
        }
 
        private static void PrintMatr(int[,] matr)
        {
            for (var i = 0; i < matr.GetLength(0); i++)
            {
                Console.WriteLine();
                for (var j = 0; j < matr.GetLength(1); j++)
                {
                    Console.Write(matr[i, j] + " ");
                }
            }
 
        }
    }
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.02.2018, 17:02

Поиск в глубину. DFC (для списка смежности)
Напишите пожалуйста код на паскале - Поиск в глубину используя списки смежности (да,да не матрица...

Матрица смежности некоторого графа. Сделать обход в длину и вывести результат обхода по возрастанию
Задание: дана матрица смежности некоторого графа. Сделать обход в длину и вывести результат обхода...

Сгенерировать матрицу смежности полного графа
1. Сгенерировать матрицу смежности полного графа (количество вершин n = 3) и найти минимальный...

Составить матрицу смежности для графа


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru