4回答
首先，我想确保我的结构是正确的。据我所知，表示图的邻接表如下所示：
AdjList是一个ArrayList，其中每个元素都是一个对象。每个对象内部都包含一个ArrayList，用于表示连接的顶点。例如，在上图中，顶点1( AdjList中的第一个索引)连接到AdjList的索引2、4和5处的顶点。邻接列表的这种表示是否正确？(ps:我知道索引从0开始，为了简单起见，我在这里放了1)。
如果它是正确的，我应该使用哪种算法来查找两个顶点之间的最短路径？
浏览 1提问于2011-12-18得票数 1
回答已采纳
1回答
如果我们知道或不知道给定图中两个节点之间的路径长度，如何一次追踪它们之间的路径？(通过考虑邻接矩阵)
在邻接矩阵和广度优先搜索中，哪种方法更有效？
你能给出算法步骤吗。
提前谢谢你，卡玛拉。
浏览 0提问于2013-06-04得票数 0
2回答
是否可以使用邻接表对Floyd Warshall进行编码？我必须处理文本文件中的一百万个顶点，因此，邻接矩阵不是一个解决方案。有没有已经可用的实现？请帮帮忙。
浏览 3提问于2014-11-29得票数 3
我在一个文本文件中有一个蛋白质列表，格式如下：
ATF-1 MET4
ATF-1 NFE2L1
ATF-2 ATF-7
ATF-2 B-ATF
ARR1 ARR1
ARR1 CHOP
我想从文本文件中读取，并使用邻接表在Java或Perl中以无向图形式实现它们。我想要计算最小和最大边数，节点之间的最短和最长路径，以及其他类似的函数。
浏览 2提问于2011-12-24得票数 2
回答已采纳
1回答
存储树和图的数据？
、、、
在我试图解决的大多数树或图问题中，输入通常是node1->leafs或node1->相邻节点格式的整个树或图结构。
是否有任何常用的结构列表可以将此数据保存在内存中，这对以后的algorithm.For示例有帮助：
Say i have a list of graph nodes like:
1 3 8 2 4.....# 1 is connected to 3 8 2 4...nodes
2 5 1 3... # 2 is connected to 5 1 3...nodes
3 1 2... #likewise
. ...
8 ......
因此，如果我想使用随机收缩
浏览 2提问于2014-10-21得票数 0
1回答
大图算法的最佳实现方法
、、、、
我们知道，我们可以使用邻接表或邻接矩阵来处理图的算法。对于小图来说，这是非常简单和简单的。但是当图形很大时，例如社交网络图，什么数据结构才是实现传统算法如最短路径查找的最佳方法。由于内存要求很高，邻接矩阵或列表无法工作，对吗？社交网络引擎使用什么方法？
浏览 3提问于2014-04-01得票数 0
回答已采纳
1回答
我正准备创建一个迷宫解决方案。正如在这两个问题： && 中所指出的，他们解释了使用邻接表与邻接矩阵的区别。不幸的是，与这两种情况相比，我无法决定边缘列表的利弊，因为我在邻接矩阵和边缘列表上发现的很少。
通过迷宫相邻列表(我认为)的一个例子是：
insertVertex(V) : O(1)
insertEdge(Vertex, Vertex, E) : O(1)
removeVertex(Vertex) : O(deg(v))
removeEdge(Edge) : O(m)
vertices()
浏览 4提问于2014-08-30得票数 5
2回答
首先，我想澄清一下，我已经看到了这样的情况：
而这并不是重复，只是一个不幸的巧合，这个人错误地说是一个“瓶颈”。
瓶颈边缘是流网络中的边缘，在增加时，增加网络的最大流量。
所以这不一定是最小切，就像像o-1->o->o这样的图，我们没有瓶颈边，但我们有最小切。
(在那个例子中，o's是节点，边是-*->，其中*是整数。)
无论如何，所有瓶颈的查找显然可以在O(V+E)中完成(假设图是以邻接列表表示形式给出的)，我认为这样做的方法是创建两个大小为V的数组，我将调用传入和输出，然后遍历邻接列表中的每个元素两次，第一次通过进入每个节点的边的值增加INCOMINGi，第二次通
浏览 1提问于2018-05-04得票数 4
回答已采纳
4回答
如何找到所有最短的路径
、、、
我有一个图，我想找到两个节点之间的所有最短路径。我通过BFS找到了两个节点之间的最短路径。然而，它只是给了我一条最短的路径，如果有超过一条。
我怎样才能让他们都使用BFS呢？
我用著名的BFS伪码实现了我的代码。
此外，我有一个邻接列表向量，它保存所有节点的邻接顶点。
浏览 5提问于2013-11-28得票数 10
回答已采纳
1回答
邻接矩阵中的路径查找
、、、
给定一个邻接矩阵，你如何找到两个节点之间的最短路径，同时至少遍历每一点一次，并返回所需的移动次数？
示例
给定这个数组
int[][] points = { { 0, 1 },{ 0, 2 },{ 1, 2 },{ 1, 3 },{ 3, 4 } };
我做了一个类似这样的相邻矩阵..。
0 1 2 3 4
0 [0] [1] [1] [0] [0]
1 [1] [0] [1] [1] [0]
2 [1] [1] [0] [0] [0]
3 [0] [1] [0] [0] [1]
4 [0]
浏览 2提问于2013-04-07得票数 0
3回答
地图中的最短路径
、、、
我在mysql中使用标准化邻接表设计了一个加权图。现在我需要找到两个给定节点之间的最短路径。
我试着在php中使用Dijkstra，但我无法实现它(对我来说太难了)。我感觉到的另一个问题是，如果我使用Dijkstra，我将需要考虑所有节点，这在大型图中可能效率非常低。那么，有没有人有与上述问题相关的代码？如果有人至少能告诉我一个解决这个问题的方法，那就太好了。我已经被困在这里快一个星期了。请帮帮忙。
浏览 0提问于2009-12-09得票数 4
回答已采纳
我有一个任务是实现Dijkstra的算法。我们得到了将图作为邻接矩阵输入的框架代码，但被告知我们的解决方案必须在O(MlogN) {M边，N顶点}中运行。我知道PQ和list结构是如何实现这一点的，但我不知道如何在我的例子中避免O(N^2)解决方案。走出矩阵的唯一方法是遍历每一行和column...right？
浏览 2提问于2012-11-27得票数 2
回答已采纳
1回答
我有一个问题，我真的在努力解决。我有一组带有权重边的村庄，我需要创建一棵最小生成树来寻找最短路径，我已经根据权重找到了村庄的最短路径，我真的不知道该怎么做，我如何才能用邻接矩阵实现这一点？我将非常感谢您的帮助:)
-10个村(节点)
浏览 0提问于2013-12-12得票数 2
1回答
任务是：
找到两个城市之间的最短路径。城市与单向道路相连。城市以这样的方式存在于.txt文件中：
/至/距离//
例如：
伦敦格拉斯哥180
曼彻斯特利物浦80
约克剑桥415
约克曼彻斯特260
格拉斯哥，约克315
格拉斯哥，曼彻斯特315
给定一个源城市S和目标城市T，找出最短路径。计算距离并检索所选路径。
的问题是：完全不允许使用任何STL容器。无法使用容器，如std::list、std::vector、std：：偶数、std::set等。然而，我能够使用自己实现的动态数据结构。
我不知道应该实现哪些数据结构以及如何实现它们。此外，我是否应该使用优先级队列、堆或其他什么
浏览 1提问于2018-12-12得票数 1
回答已采纳
3回答
对于无向加权稀疏图，寻找所有对的最短路径长度的最佳算法是什么？具体地说，权重是节点之间的距离(因此是正数)。请注意，我只需要路径长度(即不需要路径本身)。我的图是稀疏的，所以它被存储为邻接表。
我找到了Dijkstra，Floyd-Warshall，Johnson等，但他们似乎都不是我想要的最优选择。在Dijkstra的情况下，您在所有顶点上运行单一源代码版本，Floyd-Warshall用于密集图，Johnson用于有向图。
我特别想在C++中找到一个实现。
浏览 36提问于2013-10-15得票数 2
5回答
我需要输出表示为邻接matrix.Could的给定图的围长，有人给我一些提示，我如何使用邻接矩阵或邻接表来获得图的围长？
示例：
graph one:
0 1 0 0
1 0 0 1
0 0 0 0
0 1 0 0
graph two:
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
The result:
Girth of graph 1: infinity
Girth of graph 2: 5
浏览 2提问于2012-10-15得票数 1
回答已采纳
1回答
在邻接列表中表示墙壁
、、、、
1111111111
1111110101
1100010101
1111011101
1001010001
1111010101
1100010101
1111011101
1001000001
1111111111
1=Wall
0=Path
你好，我想知道我是否需要在我的邻接列表中添加一个墙节点，如果我能够通过它的属性来确定一个节点是否是一个墙，因为在计算从一个源到一个目标的最短路径的代价时，不会考虑从我的知识墙，例如使用A*算法。
另外，假设我有一个节点对象列表，并且每个节点对象都包含一个相邻节点列表，那么是否需要存储相邻的墙壁节点？
浏览 4提问于2015-01-20得票数 1
回答已采纳
1回答
如果节点是直接连接的，就有n个节点，节点之间也有边。每个边没有重量和方向(如果节点a和b连接，它意味着双向连接，而不是单向连接)。
基于该图，我们可以绘制出二维数组A.An-1的邻接矩阵.因此，问题是如何返回最短路径。如果没有路径，应该返回空路径。而路径应该使用链接列表返回。
|A B C D E
A|0 1 0 1 0
B|1 0 1 0 0
C|0 1 0 1 0
D|1 0 1 0 1
E|0 0 0 1 0
因此，基于上面的矩阵，从C到E的最短路径是C，D，E，而从A到C的最短路径是A，B，C。
我们应该使用具有O(n^2)时间复杂度的伪码。我简单地猜BFS方法会很棒。
浏览 2提问于2019-09-08得票数 0
回答已采纳
我正在研究Dijkstra的算法，我真的需要找到所有可能的最短路径，而不仅仅是一条。我使用邻接矩阵，并应用了Dijkstra算法，我可以找到最短路径。但我需要以最小的成本找到所有的路径，我是说所有可能的解决方案，如果它们存在的话。
这是我的算法是如何工作的，对于一个单一的解决方案：
public void dijkstra( int graph[][] )
{
int d[] = new int[ graph.length ];
int dC[] = new int[ graph.length ];
int p[] = new int[ graph.length ];
浏览 1提问于2010-05-12得票数 16
我如何使用Dijkstra的算法，在没有成本的情况下，在Python中的邻接矩阵？它有1，如果在两个顶点之间有一条边，否则是0。我在互联网上找到的解释都是关于有成本的图表的。
浏览 8提问于2015-04-17得票数 0
回答已采纳
我读过几篇文章(如)，指出在运行图遍历算法时，由于无索引的邻接关系，图DB天生就比RDB快。然而，我很难理解它的理论理由。在我看来，如果你构建一个散列索引的邻接表，你应该达到同样的复杂性性能。
例如，使用包含两个表的RDB查找某人的朋友(给定个人id)：people和friendships
1)定位好友: O(m) -其中m是好友的数量。
2)对于每个好友Id，位于人员中: O(1)
总计: O(m)
在图DB中，这应该是相同的，不是吗？
浏览 2提问于2020-02-13得票数 1
假设下面的矩阵是一个具有3个节点的有向图邻接矩阵。
A=[.35 .076 .12;.0054 .83 .09; .31 .92 .019]
如何在matlab或ucinet中找到两个特定节点之间的最强路径？
我需要一些方法来告诉matlab找到两个节点之间的每条可能的路径，然后将每条路径中的边的权重相加，找到最大的加权路径，然后显示该路径。例如，如果我们考虑矩阵A，并希望找到从节点1到节点3的最强路径，我们有两条可能的路径:一条从节点1到节点3的直接路径，以及一条从节点1到节点2和节点2到节点3的路径。在第一条路径中，我们有A(1,3)=.12，对于第二条路径，我们有A(1,2)+ A(2,
浏览 1提问于2013-11-04得票数 1
2回答
我正在实现一个在一组房间中寻找最小跨越走廊的算法。目前我已经弄清楚了算法，我只是在尝试实现它。它的一部分涉及到寻找给定房间的所谓“特殊点”。矩形的“特殊点”是指与另一个矩形的最远点之间的距离最小的点。例如：
房间R1的特殊点将是v6或v7，因为两者到矩形中最远点的最小距离都是相同的，而不是R1。同样，矩形R8的特殊点是v13或v14，因为两者到矩形中最远点的最小距离都是相同的，而不是R8。目前，我已经在邻接表中表示了点，列表中的每个邻接点。此外，我将每个房间都放在邻接列表中，每个边界点都是值。我也有它所属的每一个房间的每一个点。
目前，我正在通过查看该点周围每个矩形中最远点的距离来计算特
浏览 0提问于2013-06-02得票数 4
回答已采纳
1回答
我试图理解DFS和BFS在图中的空间复杂性是什么。我理解，当使用邻接矩阵时，BFS的空间复杂度为O(v^2)，其中v是顶点数。
使用邻接表可以降低平均情况下的空间复杂度，即< v^2。但在最坏的情况下，它将是O(v^2)。即使包括队列，也会是O(n^2) (忽略较低的值)。
但是，DFS的场景是什么呢？即使我们使用邻接矩阵/列表。空间复杂性为O(v^2)。但这似乎是一个非常松散的界限，这也没有考虑堆栈框架。
关于复杂的问题，我说得对吗？如果不是，BFS/DFS的空间复杂性是什么？在计算DFS的空间复杂度时，我们是否考虑堆栈框架？
对于BFS和DFS对于图，空间复杂度的紧界是什么？
浏览 1提问于2019-03-19得票数 1
回答已采纳
1回答
所有对最短路径问题
、、、、
我已经写了这个程序，它使用邻接矩阵实现了一个有100个节点的图。我还使用了Floyd-Warshall算法来为所有100个节点找到所有对的最短路径。现在，我想将100 x 100矩阵压缩为10 x 10矩阵，该矩阵仅包含public static final int A = 100...public static final int W = 66指定的10个索引的所有对最短路径。我应该如何压缩数组？我已经开始构建一个名为arrayCondenser的新方法，但是有没有更简单的方法呢？
public class AdjacencyMatrix
{
public static
浏览 11提问于2017-03-06得票数 1
我正在尝试设计一个使用斐波那契堆的dijkstras实现。我试图理解的是，除了O(logn) (带有delete)中的最小距离之外，是否可以表示任何给定节点的邻居？或者这是否违反了斐波那契堆结构？否则，我将不得不构建一个邻居列表以及一个斐波那契堆。
浏览 3提问于2010-11-12得票数 0
回答已采纳
给定宽度W和高度H的网格，其中包含5种符号：
'S' means starting position
'E' means ending position
'C' means checkpoints
'.' means open position and player can pass through it
'#' means closed block that player cant pass through.
玩家的目标是从一开始就以最小的距离到达终点，但他需要通过网格中的所有检查点。
我们需要找到这个最小距离。
浏览 0提问于2014-08-19得票数 3
我需要知道什么是最理想的旅行路径，每个人同时(假设4个小时)。这些人同时从A市开始(*见表)。
我有三个mysql表，如下所示：
表
people:
id name
1 People A
2 People B
3 People C
city:
id name
1 City A
2 City B
3 City C
... ...
26 City Z
distance:
fromCity toCity distance (km) time (appox. travel in minutes)
1 2
浏览 2提问于2020-04-20得票数 0
1回答
我尝试实现BF算法的负周期检测。
我跟着的讲座来实现算法。我的解决办法如下：
def belman_ford(s, adj, cost):
arr_len = len(adj)
dist_arr = [MAX_VAL]*arr_len
prev_arr = [None]*arr_len
dist_arr[s] = 0
for u in range(arr_len):
for i, v in enumerate(adj[u]):
if dist_arr[v] == MAX_VAL:
浏览 0提问于2018-12-28得票数 1
回答已采纳
3回答
1 1 1 1 1 1
1 2 2 3 3 3
4 4 2 2 3 4
4 4 4 4 4 4
4 4 5 5 6 6
5 5 5 5 5 6
我需要识别一个特定的超像素的相邻像素，
例如：
2的第一个邻接是1、3、4
2的第二个邻接是5、6
2的第三个邻接是...
做这件事最快的方法是什么？
浏览 5提问于2015-07-21得票数 3
13回答
我有一个大的，连通的，稀疏图的邻接列表形式。我想找到两个尽可能相距较远的顶点，即和两个实现它的顶点。
我对这个问题很感兴趣，无论是无向的还是定向的，都适用于不同的应用。在有向情况下，我当然关心有向距离(从一个顶点到另一个顶点的最短有向路径)。
有比计算所有对最短路径更好的方法吗？
编辑:我所说的“尽可能远”，当然是指“最长的最短路径”，也就是从一个到另一个最短距离的所有对顶点上的最大。
浏览 31提问于2009-07-27得票数 52
2回答
用A*算法求几条最短路径
、、、
我正在制作一个路由应用程序，它使用A*算法来查找路由。我想提供的不只是一条路线，还有几条替代路线。例如，仅比最佳路由稍长一点的路由。
由于A* (和其他许多)只找到一条路线，我如何搜索这些替代路线？我应该使用其他算法吗？
浏览 0提问于2015-02-26得票数 1
3回答
基于C#的图形导航
、、、、
我有点困惑，想想出一个很好的算法来浏览下面的图表。
如果用户选择“表21”作为起点，我需要能够从该起始表获得任何其他表的路径。
示例:如果用户选择“表21”作为开始，然后从“表8”中添加值，则需要创建以下路径"Table 21 -> Table 12 -> Table 9 -> Table 6 -> Table 8<code>E 210</code>“，表之间的所有权重都是相同的。
我似乎忘记了处理有向图的技巧，也想不出一个好的算法。我不是在要求解决问题，而是朝正确的方向前进。
谢谢!
浏览 5提问于2009-05-01得票数 3
回答已采纳
我们知道，Dijkstra在给定的图中找到从单个源节点到任何其他节点的最短路径。我尝试修改原始Dijkstra，以找到源节点和目标节点之间的最短路径。只在Dijkstra找到目标节点时设置终止程序的终止条件似乎很容易。然而，代码中设置的“终止条件”似乎导致了次优最短路径而不是最优最短路径。 Dijkstra代码如下，
def dijkstra(adjList, source, sink):
#define variables
n = len(adjList) #intentionally 1 more than the number of vertices, keep the 0th e
浏览 0提问于2020-09-20得票数 0
回答已采纳
2回答
假设人口为500人，而每个人都确切地知道人口中还有4人。假设一个人感染了一种疾病，这种疾病保证会在一天内传染给其他4个人。
编写一个算法来确定每个人被感染需要多少天，给出一个输入邻接矩阵。
我想不出怎样才能正确地记录这些日子。我尝试了以下方法，但它只是给出了一个接近节点总数的数字(应该要低得多)：
import random
random.seed(20)
nodes = 500
num_connections = 4
# generate random graph
graph = []
for node_num in range(nodes):
myrow = [0 for nod
浏览 2提问于2021-09-14得票数 0
给定两个字谜S1和S2，我们要将S1字谜转换为S2字谜。我们需要找出最小数量的邻接掉期。
例如: S1:CAT和S2:ACT。这里，交换的最小数量仅为1.交换C到A以获得S2。
我们如何使用动态规划来实现它呢？有可能吗？
浏览 1提问于2013-11-05得票数 3
1回答
假设我们在一个无向循环加权图中有一条路径。假设我们有一个引擎可以在这样的图中找到从节点A到节点B的路径，有没有一种简单的方法/算法来计算出从A到B的给定路径是否比从A到B的任何其他不相交的路径至少好X%？我所说的不相交是指两条路径不能共享任何边。
浏览 1提问于2011-10-08得票数 1
回答已采纳
2回答
图遍历的BFS实现困难
、、、、
我有一个邻接矩阵，定义如下：
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0
1 0 0 0 1 0 1 0 0
0 0 0 1 0 1 0 0 0
0 0 1 0 1 0 0 0 1
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0
我绞尽脑汁地设计一个BFS算法来遍历给定的起始位置和结束位置的图形。
我最好的尝试确实产生了一系列的动作，但不是最短的。
boolean[] pass = new boolean[9]; //if a move has been
浏览 7提问于2015-07-07得票数 1
回答已采纳
1回答
EIGRP相邻表
、、
来自Cisco IP路由的Alex Zinin
📷
根据这个图，据我所知，邻接表从双模块also.As获得消息，邻接表只是因为不同邻居之间交换的Hello而被填充。邻接表和对偶模块之间的关系是什么？
浏览 0提问于2019-07-31得票数 3
回答已采纳
我正在研究一个问题，就是找到可以存储在一起的最多的并行表，给出一个并行表的列表。
我的方法是用一个邻接列表来表示这个图，做一个拓扑排序，然后对拓扑数组中的每个节点“放松”边缘，给出最长的路径。
下面是代码，但我认为这与问题无关。
typedef struct Edge {
int src; /* source node */
int dst; /* destination node */
struct Edge *next;
} Edge;
int maxend; //node in which the longest path ends
浏览 7提问于2021-07-16得票数 1
回答已采纳
我最近正在学习图形算法，在我的大学里，我们被教导说，Bellman的结果是一个从所有节点到所有其他节点的距离表(所有对最短路径)。然而，我不明白这个算法是如何实现的，我试图通过观看YouTube视频和查找维基百科中的定义来理解它……
现在问题来了：
我无法找到描述该算法的资源，其结果将是所有对最短路径表，但只能“从一个节点到所有其他节点”。
对Bellman算法进行调整以实现所有对最短路径表，还是我的大学讲师在这方面完全错了？(他解释了一些提供所有对最短路径的算法，他称之为Bellman，但我认为这不可能是Bellman)。
编辑:我绝对理解Bellman算法中的“从一个节点到所有其他节点的最
浏览 8提问于2017-07-16得票数 1
回答已采纳
因此，我正在尝试编写一个算法，用于计算在O(m + nlogn)时间内可以访问的顶点上的约束的最短路径。在这个问题中，我们给出了一个间接加权(非负)图G= (V，E)，一组顶点X⊂V，以及两个顶点s，t∈V\ X。这个图是用邻接表给出的，我们可以假设它需要O(1)时间来确定一个顶点是否在X中。我正在尝试编写一个算法，它可以计算G中s和t之间的最短路径，使得如果在O(m + nlogn)时间内存在这样的路径，则该路径最多包含从X到X的一个顶点。我知道这个算法需要一个改进的Dijkstra算法，但我不确定如何从这里开始。有谁能帮帮我吗？谢谢
浏览 1提问于2020-05-08得票数 0
1回答
赋权有向图的邻接矩阵
、、、
A)设A是具有n个顶点的赋权有向图G的邻接矩阵，其中A[i,j]是边i到j的权重。如果没有这样的边缘A[i ,i]=0。矩阵A^K= A*A*A*...A。如果我们使用+而不是*，并且使用min而不是+，则时隙A^k [i,j]不能用至多k边来描述路径i到j的权重。我想找出这个问题表现出什么东西？
B)设A是具有n点的赋权有向图(无圈多边) G的邻接矩阵，其中A[i,j]是边i到j的权重。如果没有这样的边缘A[i ,j]=infinity，并且对于每个i，我们都有A[i, i]=0。矩阵A^K= A*A*A*...A。老虎机A^k [i,j]展示什么东西？最小重量？或者...？
有什么想法吗？
浏览 3提问于2014-10-18得票数 0
4回答
std::list <int> q;
std::vector<bool> visited(cols + 1);
for(int i = 1; i <= cols; i++) visited[i] = false;
visited[x] = true;
if(!l[x].empty())
{
for(std::list<int>::iterator i = l[x].begin(); i != l[x].end(); i++)
{
q.push_back(x); q.push_back(* i);
}
wh
浏览 1提问于2013-06-19得票数 2
回答已采纳
1回答
网络中最可能的路径
、、、
我有一个邻接矩阵(作为熊猫数据)，每个单元格是从A到B的概率。
行是"from“，列是"to”。每一行的和为1.0。
我已经构建了一个网络图，现在概率是图的“权重”。
我试图找出最可能的路径，即权值的乘积是最低的，而不是和。我知道网络最短路径找到了最优路径i项的权重之和。如何从最优乘积的角度寻找最优路径？
编辑:输入是图G、节点“源”和节点“目标”，为了简单起见，这些输入实际上是由多条路径连接的。我想在G中找到它们之间最可能的路径
Thx
浏览 1提问于2020-04-07得票数 1
回答已采纳
3回答
全对最短路径，领带断裂
、、、
我正在创建一个程序，它将计算未加权图中所有节点的Betwenness中心性。要做到这一点，我必须找到ASSSP (所有单一源最短路径)。在创建程序时，我意识到最终我将有联系(从源到目的地的距离相同，但路径不同)。这使我想到了这个问题。我该如何解决这些关系？如果我使用随机的断线器，那么对于相同的输入，中间中心度的每个输出可能略有不同。让我做一个小小的示范性图：
A
/ \
B C
\ /
D
现在假设A节点是我们希望找到ASSSP的源。可见，有两条路径(A->B->D和A->C->D)，bot的长度相同，两者最短。现在我应该选择哪一个，在什么条件
浏览 2提问于2012-07-11得票数 2
回答已采纳
2回答
给定一个无向图，一个起始点和一个结束点。找出从源到汇点恰好涉及h跳的遍历次数(这样一个顶点可以被多次访问)。例如，如果图是一个三角形，则具有h跳的此类路径的数量由第h个给出。这可以扩展到完全连接的k节点图，产生递归(和闭合形式的解) 。
当图形是n边多边形时，接受的答案将漫游的数量表示为二项式的总和。
我假设对于任何给定的图，可能有一个有效的算法来找到这个数字？我们可以假设图是以邻接矩阵或邻接表或任何其他方便的符号提供的。
浏览 0提问于2020-06-08得票数 3
1回答
我只是好奇facebook、linkdin等大型应用程序如何建模它们的内部图形数据结构。考虑到用户规模的性质，使用邻接表示是否可行，或者这些技术巨头在图形表示中使用了其他一些花哨的数据结构。
编辑邻接表，而不是邻接列表矩阵
浏览 3提问于2014-05-21得票数 2
我目前正在研究Bellman算法，出现了一个疑问。据我所知，Bellman算法从它的来源创建最短路径，如果图中有一个负循环，它返回true，算法停止，另一方面，它用最短路径返回false。
我现在的问题是，该算法是避免了图中创建最短路径的正循环，还是没有考虑到它们(因而落入了它们的陷阱)？
提前感谢！
浏览 4提问于2022-01-12得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
