Tag: 向图

如何在C中创建有向图的邻接列表？

编辑：没有人回答，但我认为这与我如何存储我的列表有关。 现在我将每个顶点存储在一个名为G的节点数组中。但是我认为我需要使它成为一个二维数组，以便我不会覆盖其他节点中的数据。 （这很令人困惑） 正如标题所说，我正在尝试创建有向图。 我遇到了一个问题，每当我尝试将一个Node添加到顶点的邻接列表时，它就会改变前一个顶点的列表。 例如，我有一个带有这些边的简单有向图。 （父母，孩子） （2,1） （3,2） （3,4） （5,1） 当我尝试将顶点4添加到顶点3的邻接列表时，我最终改变了顶点2指向的顶点。 我需要它从3 – > 2 – > 4而不改变顶点2.我不知道如何做到这一点。 这是我的代码 Node* create_graph(Edge* E, int numbVertices, size_t size){ int i, j=0; Node* G = (Node*)malloc(sizeof(Node) * numbVertices); G[0].vertex = 0; G[0].next = NULL; for(i=1;i<numbVertices;i++){ G[i].e = 0; G[i].vertex = i; G[i].next = NULL; for(j=0;j<size;j++){ if((E[j].p) == […]

具有有限数量变化的“双图”中的最短路径

假设我们在一组顶点上有两个有向和正加权图（第一个图表示例如铁路，第二个表示公交车道;顶点是公交车站或铁路车站或两者）。 我们需要找到从A到B的最短路径，但我们不能将传输类型改为N次以上。 我试图修改Dijkstra的算法，但它只在一些“不那么平均和复杂”的图形上工作，我想我需要尝试不同的东西。 如何最好地表示“双图”以及如何管理遍历图表的有限数量的更改？ 是否有可能在这一个中适应Dijkstra的算法？ 任何想法和线索都会有所帮助。 编辑：我忘记了一件事（我认为这很重要）：N = 0,1,2，…; 我们可以得出我们喜欢的任何图形表示，当然每两个节点之间可以存在最多4条边（1个公交车道和1个铁路在一个方向上，1个公交车道和1个铁路在第二个方向）。