C#连接路径的分离度 [英] C# Degree of separation for connected paths

问题描述

我对图非常陌生，试图找出正确的方法来为此创建图:

I am very new to graphs, trying to figure out the right way to create a graph for this:

考虑到该市拥有的一组城市和州际公路，需要找出其他城市道路是否与相应城市中的一条相交，例如波士顿和分隔程度.

Given a set of Cities and Interstates that City have, need to find out if other Cities roads intersects with one of the respective City say Boston and the degree of separation.

例如:如果波士顿是需要计算联系州际度的城市，则0是波士顿的分离度.如果纽约可以直接连接到波士顿，则分离度为1，如果纽约通过不同的城市道路连接到波士顿，则分离度为2，依此类推

E.g : If Boston is the City for which the connecting interstates degree needs to be figured, 0 is the degree of separation for Boston. If new York can connect directly to Boston the degree of separation is 1, If new York connects to Boston through a different city road , the degree of separation is 2 and so on

例如输入:

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的方式.

I have transformed the input data into a Dictionary<string,List<string>> that has connecting cities. Trying to figure out how construct a Graph or a way i can use Dictionary<string,List<string>> to do 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)来解决.该算法为您提供了一棵树，其根是您开始的城市，并且从那里到任何其他节点/城市的唯一路径是跳数最少的树.

This can be solved with a breadth first search (BFS) in the graph. This algorithm gives you back a tree whose root is the city you start with and the unique path from there to any other node/city is the one with the fewest possible hops.

如果您需要所有城市/节点的此信息，请为每个城市运行一次算法.

If you need this information for all your cities/nodes then run the algorithm once for each city.

有关BFS及其运行时间的说明，例如维基百科.

For an explanation of BFS and its running time a good source is e.g. wikipedia.

BFS需要一个图作为输入，最好由邻接表给定.因此，给定的数据首先需要进行转换:在列表上运行，并为每个城市存储与之直接相连的城市:

BFS needs a graph as input, preferably given by an adjacency list. The given data thus needs a transformation first: Run over the list and for each city store the cities that are connected directly to it:

波士顿:纽约纽约:波士顿，西雅图西雅图:纽约

现在，您维护三项信息:以波士顿(在您的情况下)初始化的工作队列 Q ，以波士顿初始化的已连接"城市列表 S 以及先行者"的数组 P :对于每个城市，它将包含从波士顿出发的路径上的先前城市.对于波士顿来说，这等于零.

Now you maintain three pieces of information: A working queue Q initialized with Boston (in your case), a list S of "already connected" cities initialized with Boston and an array P of "predecessors": For each city this will contain the previous city on the path from Boston. For Boston this points to nil.

在队列中运行:在 Q 中选择第一个条目 c ，在其邻接处运行，每当遇到未连接的城市时，将其添加到 S ，将其前身设置为 c 并将其添加到 Q 的末尾.

Run over the queue: Pick the first entry c in Q, Run over its adjaceny and whenever you encounter an unconnected city add it to S, set its predecessor to c and add it to the end of Q.

如果实际上可以从波士顿到达每个城市，那么您将以一棵前辈"树结束.要确定一个城市的距离，请遵循从该城市到波士顿的前辈.

If every city can actually be reached from Boston then you end with a tree of "predecessors". To determine the distance of a city follow the predecessors from this city to Boston.

这篇关于C#连接路径的分离度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！