时间戳

首页 > 解决方案 > 我可以在图表的边缘插入数据吗？

c - 我可以在图表的边缘插入数据吗？

问题描述

我可以将数据放在相邻列表图的边缘吗？

我的要求有以下几行：

(A) 所需信息：A-1。100 个城市，每个城市的游览时间 A-2。300 地点之间的交通 w/ 价格

(B) 显示直接访问的城市图表（100 个站点，其中 300 条直接路径）

(C) 图由有距离的边组成

从（B）开始，我认为城市是顶点，路线（交通）是边。

（A. 需要的信息）说运输应该有自己的价格，（C）说边缘有距离。

这就是为什么我对将数据置于边缘的方式感到好奇。我以为edge只是一个抽象概念，实际上是通过将另一个节点的地址给节点来实现的。

喜欢：

struct AdjListNode* newNode = newAdjListNode(dest); 
newNode->next = graph->array[src].head; 
graph->array[src].head = newNode;

如何用数据实现边缘？谢谢你。

标签： c

解决方案

是的，您可以将数据与图形边缘相关联，这与您表示图形的方式无关。想想你将如何解决最短路径问题；您显然需要知道图中两个节点之间的距离，并且此信息是连接它们的边的属性，而不是单个节点。

在您的示例中，您可以：

// create reciprocal links between nodes 'src' and 'dst',
// containing the 'distance' information
void graph_link_two_cities(struct Graph* graph, int src, int dst, int distance)
{
    {
        struct Edge* head = graph->array[src].head; 
        struct Edge* node = { .id = dst, .distance = length, .next = head });
        graph->edges[src].head = node;
    }

    {
        struct Edge* head = graph->array[dst].head; 
        struct Edge* node = { .id = src, .distance = length, .next = head });
        graph->edges[dst].head = node;
    }
}

使用邻接矩阵，您只需将 和 之间的距离src存储dst到matrix[src][dst].

推荐阅读