算法和数据结构的实现

Question

我已经成功地实现了几种算法和数据结构。然而，我不确定我将如何实现一个图形算法，因为我需要表示一个图形。我正在尝试实现cormen et算法导论中的算法和数据结构。阿尔。但是，许多算法将图形作为输入，或者将树结构作为输入，您也不能将其作为文本提供。我不知道如何实现dijkstra，贝尔曼-福特，弗洛伊德-沃希尔，kruskal等。我能将任何图表示为矩阵吗，即使它是一个加权或有向图？因为我认为我可以对矩阵使用多维数组。我认为0或1可以指示是否存在边，但我不太确定如何使用矩阵来表示任何图。如果算法将其作为输入，那么二叉树又如何呢？

提前谢谢。

Answer 1

这是一个非常开放的问题。答案取决于您想要执行的操作类型。

表示简单图的一种方法是N x N数组，其中每个元素表示一条边。显然，您只需要一个三角形，可以忽略另一半，也可以复制信息以使查找更容易。

对于具有大量顶点的稀疏图，您可以将边表示为具有两个链接的节点，以便它可以位于两个列表中。每个顶点都将具有链接在一起的边列表的头部。