tree - 带值边的树形数据结构

Question

我有一个图表 - 例如 - 公共汽车站和它们之间的距离。

图：AB5、BC4、CD8、DC8、DE6、AD5、CE2、EB3、AE7

AB5：停止A到停止B，距离为5等。

你能推荐一个可以支持这个图的数据结构或对象设计吗？

我对此的看法：

一个节点——在这种情况下是一个公共汽车站——可以有一条或多条路线。Route 具有 SourceNode 和 DestinationNode 的值 - 距离。该节点有一个地图目的地名称 -> 路线。

然后可以锻炼 ABC 的距离，即 9。

Answer 1

有几种数据结构可以表示图： Wikilink

如果您选择邻接矩阵，您将有一个 *n 矩阵，其中每个槽代表 2 个顶点之间的距离。我更喜欢这种表示，当你知道顶点的数量时（最好不要太多，这样你的矩阵就不会占用太多空间）。如果需要，很容易找到 2 个顶点之间的距离以及更新距离。但是，如果您不确定顶点的数量，或者该数量将来可能会增加，那么其他表示将是更好的选择。

这是一些代码片段：

    static void Main(string[] args)
        {
            int length = 7; //number of vertices
            int [,] Matrix = new int[length-1,length-1];
            //instantiate Matrix with 0's
            for(int i = 0; i < length; i++)
            {
                for(int j = 0; j < length; j++)
                {
                    Matrix[i,j] = 0;
                }
            }
            // Import your distances:
            Matrix[0, 1] = 5; // AB5
            Matrix[1, 2] = 4; //BC4 and so on..

        }

希望您对如何继续有所了解。如果您有很多数据要输入，您可能希望从某个文件中读取它并在 Matrix 中迭代地填充数据。