标签: directed-graph

我来自阿根廷,但我认为每个参加数据结构课程的人都知道图表是什么.如果你这样做,你可能知道什么样的实现是"常见的"或"标准的".它可以通过List或数组实现.甚至维基百科都这么说.还有Mark Allen Weiss,Bruno Preiss和Luis Joyanes Aguilar.

事情是.没有人认为这不是一个好方法吗？最推荐的方法是通过List.但是考虑到顶点之间只有一条边,我不认为List是这样做的好界面.我的意思是,如果Vertex V1与Vertex V2连接,那么只有一个且只有一个边缘.

难道你不认为它会是一个Set而不是一个列表吗？

Class Vertex{
    private Set edges;
    private Object data;

    /** Methods**/
}

只是想知道一些意见,你怎么看？

谢谢!!

编辑: 此外,如果我们认为图形不能有重复的元素,HashSet将是一个很好的选择,以最小化插入中的顶点的查找.

我试图Node在有向图中实现一个表示节点的类,特别是有一组后继者和前辈.我希望Node.predecessors并且Node.predecessors表现得像集合,特别是我想迭代它们的元素,添加和删除元素,检查包含,并从迭代中设置它们.但是,node_1.sucessors.add(node_2)它之后应该是真的node_1 in node_2.pedecessors.

似乎有可能编写一个set实现这种魔法的新子类,但据我所知,这样一个类的实现会非常麻烦,因为它必须知道Node它所属的对象以及它是否是前身或者后继并且需要一些特殊的方法来添加等等,这样node_1.sucessors.add(node_2)就不会调用node_2.predecessors.add(node_1)因而导致无限循环.

(node for node in all_nodes if self in node.sucessors)应该可以动态生成两个属性中的一个属性,但是我需要跟踪属于图形的所有节点,如果我只有一个图形,但是使用一个,这很容易(将其添加到weakref.WeakSet类属性中__init__)如果我有多个不相交的图,那么所有节点的大集合会导致大量的计算工作,而我看不到如何修改前辈集.

有人有一个很好的解决方案吗？

所以我最近一直在研究 Dijkstra 的算法和有向图。但是，我似乎无法弄清楚这一点，这真的开始困扰我。

如果恰好有一个负权重边但没有负权重循环，则展示如何修改 Dijkstra 算法以解决单源最短路径问题。

到目前为止，我最初的想法是以某种方式拆分图形并分别执行算法，但这就是我想到的全部。

我实际上找到了我正在寻找的解释，但我似乎无法遵循他的解释

回答得好！我想指出的是，如果负边的数量有限，那么基于 Dijkstra 的算法可能会做得更好。例如，如果从u到v只有一个下降沿，你可以在S和V上运行Dijkstra算法，然后取最小值之间的每个顶点d[s]和d[s]+w(u, v)+d[v]，给人一种运行Dijkstra算法的复杂度的两倍

public int dijkstra(){
    boolean[] visited = new boolean[gSize];

    int src = 1;
    int dest = 1;
    int[] distance = new int[5];
    int[] part = new int[5];
    int min;
    int nextNode = 0;

    for(int i = 0; i < 5; i++)
    {
        visited[i] = false;
        part[i] = 0;

        for(int j = 0; j < 5; j++)
            if(arr[i][j] == -1)
                arr[i][j] = 999; //gives it a high value to ignore
    }

    distance = arr[src];
    distance[src] = 0;

    visited[src] = true;

    for(int i …

我发现了一个简单的算法来找到一个图所有循环这里。我也需要打印出周期，这个算法可以吗？请在下面找到代码。

我得到正确的周期数！

node1, node2 是整数。访问的是一本字典

def dfs(self,node1, node2):
    if self.visited[node2]:
        if(node1 == node2):
            self.count += 1
            print node2
        return

    self.visited[node2] = True

    for x in self.adj_lst[node2-1]:
        self.dfs(node1, x)

    self.visited[node2] = False

def allCycles(self):
    self.count = 0
    for x in self.VList:
        self.dfs(x.num, x.num)
        self.visited[x.num] = True

    print "Number of cycles: "+str(self.count)

首先，我想澄清一下，我对图论和解析有向图的正确算法的经验很少，并且我在这里进行了搜索，但没有找到我想要的东西。希望你们能帮助我:)

我有一个大型有向图（大约 3000 个节点），其中有几个由连接节点组成的子图，并且子图彼此不连接。这是我这里拥有的数据的一个具有代表性的小图表：

我正在编写一个 Perl 脚本来查找从每个源节点到接收器节点的所有可能路径，并将它们存储在数组的数组中。因此，对于该图，可能的路径是：

1,2,3,4,5,6
1,2,3,4,5,7
1,8,9,10
11,12,13
11,14
15,16,17

我在脚本中完成此搜索的方法是在以下步骤中使用Graph模块：

1. 查找图中所有源节点并将它们存储在数组中
2. 找到图中所有的sink节点并将它们存储在一个数组中
3. 使用 Floyd-Warshall 算法查找所有对的短路径
4. 如果源节点和汇节点之间存在路径，则搜索 APSP Floyd-Warshall 图对象。如果存在路径，则将其存储在数组的数组中。如果没有路径，则什么也不做。

这是我的脚本中执行此操作的部分：

#Getting all source nodes in the graph:
my @source_nodes = $dot_graph->source_vertices();
my @sink_nodes = $dot_graph->sink_vertices();

# Getting all possible paths between from source to sink nodes in the graph:
print "Calculating all possible overlaps in graph\n";
my $all_possible_paths = $dot_graph->APSP_Floyd_Warshall();
print "Done\n"; 

# print "Extending overlapping contigs\n"; 
my @all_paths;
foreach my $source (@source_nodes) {
    foreach …

我有一个有向图的nxn邻接矩阵.我想搜索以查看是否有任何列总和为n.问题是我必须在O(n)时间内完成这项工作.有没有办法用O(n)时间来处理这个问题或者是不可能的(不需要代码)？

供参考,以下是我要解决的问题:

问题:

在学校的乐队选举期间,每个人对总统有一些偏好,并且一个人的偏好一直包括他/她自己."完美"的总统是每个人都喜欢的人,除了他/她自己不喜欢任何人.我们想要知道的是这样一个人是否存在.

• 定义与所述一组候选作为顶点和从顶点的有向边的有向图一到顶点b当且仅当b是在该组的偏好的一个.
• 有n个人
• 我们想要一种在O(n)时间内执行的算法
• 我们以nxn邻接矩阵的形式给出了上述图形

我想如果每个人都投票给"完美的总统",那么他/她将有n个传入节点,因此总结列应该给我们n.如果有更好的方法来解决这个问题而不是我正在做的事情,那么任何提示都会受到赞赏,以指导我朝着正确的方向前进.

我试图将有向（无环）图拆分为方向连接的路径，依赖于连接性：

当我测试弱连接和强连接子图时，我得到的是：

Weak connectivity :
['16', '17'], ['3', '41', '39', '42']
Strong connectivity :
['17'], ['16'], ['39'], ['41'], ['3'], ['42']

我理解弱连接结果，但不是强连接结果，因为我期望 3 个子图：[16, 17]、[42, 39] 和 [3, 41, 39]。

我在这里错过了什么，为什么那些单节点列表？如何得到预期的结果？

这是代码：

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()
G.add_edges_from([('16', '17'), ('3', '41'), ('41', '39'), ('42', '39')])

print("Weak connectivity : ")
for subgraph in (G.subgraph(c).copy() for c in nx.weakly_connected_components(G)) :
    print(subgraph.nodes)
print("Strong connectivity : ")
for subgraph in (G.subgraph(c).copy() for c in nx.strongly_connected_components(G)) :
    print(subgraph.nodes) …

正如标题所说..在java中存储连接图的最有效方法是什么？

例如,假设我有多个位置以各种方式相互连接,我必须遍历图表以查看它是否已连接..任何帮助/评论都会有所帮助,谢谢!

我有一个数据文件,其中包含表示河流流量关系的配对值列表.

该文件具有此结构

Node       Downstream Node
A          B
B          C
C          D
E          C

etc

我需要做的是读取此文件,然后对于任何给定节点,我需要打印所有的UPSTREAM节点.

在上面的例子中,如果我输入C,我会得到E,B,A.

我在Linux机器上使用perl,我写这篇文章的人也是.谢谢.