Как реализовать взвешенный граф?

290
28 ноября 2017, 19:31

Граф задаётся списком смежности,читается из файла.В итоге граф = List<Node> Не знаю, как программно реализовать вес рёбер.Подскажите пожалуйста

class Node//вершина
    {
        public string name; //хранит название вершины
        //содержит названия вершин, к которым исходят дуги из данной вершины
        public List<string> neighbours = new List<string>();
        //считывание строки
        public Node(string parse)
        {
            char[] separators =
            {
                ':',
                ','
            };
            string[] parseResult = parse.Split(separators);
            name = parseResult[0];
            for (int i = 1; i < parseResult.Length; i++)
            {
                neighbours.Add(parseResult[i]);
            }
        }
        // выводит название вершины
        public void print()
        {
            if (neighbours.Count == 0)
            {
                Console.WriteLine("- Вершина " + name + " не имеет исходящих дуг.");
                return;
            }
            Console.WriteLine("-Вершина " + name + ":");
            Console.WriteLine("Исходящие дуги:");
            foreach (var i in neighbours)
            {
                Console.WriteLine("" + name + "-> " + i + "");
            }
        }
        /** добавляет в список вершин-"соседей"
         * вершину с заданным именем
         */
        public void addEdge(string newEdge)
        {
            neighbours.Add(newEdge);
        }
        /** удаляет из списка вершин-"соседей"
         * все вхождения deletedEdge
         */
        public void deleteEdge(string deletedEdge)
        {
            while (neighbours.Remove(deletedEdge)) ;
        }
        public void deleteEdge(int deletedEdge)
        {
            for (int i = 0; i < neighbours.Count; i++)
            {
                if (int.Parse(neighbours[i]) == deletedEdge)
                {
                    neighbours.RemoveAt(i);
                }
            }
        }
    }
Answer 1

Зависит от вида списка смежности, проще всего если для N вершин он представлен матрицей (двумерный массив) размером NxN, где в пересечении строка-столбец записан вес ребра, например:

_|1|2|3|4|
1|0|7|0|9|
2|7|0|5|0|
3|0|5|0|8|
4|0|0|8|0|

здесь описаны 3 ребра: (1-2) весом "7"; (2-3) весом "5"; (3-4) весом "8". "0" означает что ребро между вершинами отсутствует; веса могут быть дробными и отрицательными. Так можно описать взвешенный ориентированный граф, за исключением случая, когда может быть нулевой вес ребра -- придётся выдумать другой флаг отсутствия ребра, например при записи в текст.файле ставить не-числовой символ, а при написании программы (в 2-мерн.массиве чисел) использовать константу типа "NaN".

Это не список рёбер/вершин (существует только табл. смежности) -- дополнительных задач вам вроде бы не влечёт =)

READ ALSO
Получить данные из одной таблицы и записать в другую

Получить данные из одной таблицы и записать в другую

в базе данных SQLite есть таблица Выручка: №, ФИО, Дата, Сумма

233
BinaryReader (c#) в delphi 7

BinaryReader (c#) в delphi 7

В c# был удобный компонент BinaryReader, с ним можно было удобно записывать строки и числа (Write), а так же легко было считать (

232
Второй поток начинает свою работу, после завершения первого

Второй поток начинает свою работу, после завершения первого

Подскажите, как сделать что бы второй поток запускался после завершения первого потока?

194
Передача ссылки на самого себя в параметре команды

Передача ссылки на самого себя в параметре команды

Привет всемХотел бы узнать 2 момента по поводу MVVM + WPF

199