C # Степень разделения для подключенных путей

Я очень плохо знаком с графиками, пытаясь найти правильный способ создания графика для этого:

Учитывая набор городов и межгосударств, которые есть в этом городе, необходимо выяснить, пересекаются ли дороги других городов с одним из соответствующих городов, например, Бостоном, и степень разделения.

Например: если Бостон — это город, для которого необходимо определить степень смежности между штатами, 0 — это степень разделения для Бостона. Если Нью-Йорк может напрямую соединиться с Бостоном, степень разделения равна 1, Если Нью-Йорк соединяется с Бостоном через другую городскую дорогу, степень разделения равна 2 и т. Д.

Например, вход:

Boston,I-94;I-90
NewYork,I-80;I-94
Seattle,I-80;I-5

Например, выход:

0, Boston
1, NewYork
2, Seattle

Я преобразовал входные данные в Dictionary<string,List<string>> это соединяет города. Попытка выяснить, как построить график или как я могу использовать Dictionary<string,List<string>> делать BFS.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Collections;

namespace DegreesOfSeperation
{
public class Program
{
public static void Main(string[] args)
{
/* Enter your code here. Read input from STDIN. Print output to STDOUT */

//use dictionary to store the values for creating the graph
Dictionary<string, List<string>> vertices = new Dictionary<string, List<string>>();

string str = null;
//skip the lines with # and decrement the counter to avoid index out of bounds error
while ((str = Console.ReadLine()) != null && str != "")
{
String[] strArr = str.Split(',');
string cityKey = strArr[0];

//use dictionary to store the values for creating the graph
vertices.Add(cityKey , new List<string>());
vertices[cityKey ].AddRange(strArr[1].Split(';'));
}

if (vertices.Count > 0)
{
//create a new dictionary to insert the final vertices with neighbors
Dictionary<string, List<string>> vertices1 = new Dictionary<string, List<string>>();

foreach (var item in vertices)
{
var currentValues = item.Value.ToList();
var matchingKeys = (vertices.Where(vertex => vertex.Value.Any(value => currentValues.Contains(value))).Select(pair => pair.Key)).Where(keys => keys != item.Key);

//add values to the dictionary with the new matching vertices/nodes
vertices1[item.Key] = matchingKeys.ToList();
}

//Now Vertices1 has the transformed values as below
//Boston: NewYork
//NewYork: Boston, Seattle
//Seattle: NewYork
//How to form the Graph and do the Breadth-First-Search here ??
}
}
}
}

-2

Решение

Это можно решить с помощью поиска в ширину (BFS) в графе. Этот алгоритм возвращает вам дерево, корнем которого является город, с которого вы начинаете, и уникальный путь оттуда к любому другому узлу / городу — это путь с наименьшим количеством возможных прыжков.

Если вам нужна эта информация для всех ваших городов / узлов, запустите алгоритм один раз для каждого города.

Для объяснения BFS и его времени работы хорошим источником является, например, википедия.


BFS нужен граф в качестве входных данных, предпочтительно заданный списком смежности. Таким образом, данные данные сначала нуждаются в преобразовании: бегите по списку и для каждого города сохраняйте города, которые напрямую связаны с ним:

Boston: NewYork
NewYork: Boston, Seattle
Seattle: NewYork

Теперь вы поддерживаете три части информации: рабочая очередь Q инициализируется с Бостоном (в вашем случае), список S «уже подключенных» городов, инициализированных с Бостоном и массивом P из «предшественников»: для каждого города будет указан предыдущий город на пути из Бостона. Для Бостона это указывает на ноль.

Запустить через очередь: выбрать первую запись c в Q, Беги через его прилегающую территорию и всякий раз, когда ты встречаешь не связанный город, добавляй его в Sустановите его предшественник c и добавить его в конец Q,

Если из Бостона можно добраться до любого города, то вы получите дерево «предшественников». Чтобы определить расстояние города следуйте предшественникам от этого города до Бостона.

1

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector