Я очень плохо знаком с графиками, пытаясь найти правильный способ создания графика для этого:
Учитывая набор городов и межгосударств, которые есть в этом городе, необходимо выяснить, пересекаются ли дороги других городов с одним из соответствующих городов, например, Бостоном, и степень разделения.
Например: если Бостон — это город, для которого необходимо определить степень смежности между штатами, 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 ??
}
}
}
}
Это можно решить с помощью поиска в ширину (BFS) в графе. Этот алгоритм возвращает вам дерево, корнем которого является город, с которого вы начинаете, и уникальный путь оттуда к любому другому узлу / городу — это путь с наименьшим количеством возможных прыжков.
Если вам нужна эта информация для всех ваших городов / узлов, запустите алгоритм один раз для каждого города.
Для объяснения BFS и его времени работы хорошим источником является, например, википедия.
BFS нужен граф в качестве входных данных, предпочтительно заданный списком смежности. Таким образом, данные данные сначала нуждаются в преобразовании: бегите по списку и для каждого города сохраняйте города, которые напрямую связаны с ним:
Boston: NewYork
NewYork: Boston, Seattle
Seattle: NewYork
Теперь вы поддерживаете три части информации: рабочая очередь Q
инициализируется с Бостоном (в вашем случае), список S
«уже подключенных» городов, инициализированных с Бостоном и массивом P
из «предшественников»: для каждого города будет указан предыдущий город на пути из Бостона. Для Бостона это указывает на ноль.
Запустить через очередь: выбрать первую запись c
в Q
, Беги через его прилегающую территорию и всякий раз, когда ты встречаешь не связанный город, добавляй его в S
установите его предшественник c
и добавить его в конец Q
,
Если из Бостона можно добраться до любого города, то вы получите дерево «предшественников». Чтобы определить расстояние города следуйте предшественникам от этого города до Бостона.
Других решений пока нет …