C# 连接路径的分离度

Question

我对图表很陌生，正在尝试找出为此创建图表的正确方法：

给定城市拥有的一组城市和州际公路，需要找出其他城市道路是否与相应城市之一相交，例如波士顿和分离度。

例如：如果波士顿是需要计算州际连接度的城市，则 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 ??
            }           
        }
    }
}

Answer 1

这可以通过图中的广度优先搜索 (BFS) 来解决。该算法返回一棵树，其根是您开始的城市，从那里到任何其他 node/city 的唯一路径是跳数最少的那条路径。

如果您的所有 cities/nodes 都需要此信息，那么运行每个城市的算法一次。

对于 BFS 及其运行宁时间的解释，一个很好的来源是例如维基百科。

BFS 需要一个图作为输入，最好由邻接表给出。因此，给定数据首先需要进行转换：运行遍历列表，并为每个城市存储与其直接相连的城市：

Boston: NewYork NewYork: Boston, Seattle Seattle: NewYork

现在您维护三个信息：使用波士顿初始化的工作队列 Q（在您的例子中）、S 个 "already connected" 个城市的列表 "already connected" 使用波士顿初始化和一个数组P of "predecessors"：对于每个城市，这将包含从波士顿出发的路径上的前一个城市。对于波士顿，这指向零。

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

如果实际上可以从波士顿到达每个城市，那么您将以 "predecessors" 的树结束。判断一个城市的距离，跟随前辈从这个城市到波士顿的距离。

C# 连接路径的分离度

C# Degree of separation for connected paths

c#

c++

algorithm

graph

breadth-first-search