对于C++中的图形问题,什么是更好的,邻接列表或邻接矩阵？各有哪些优缺点？

请注意,图表表示为邻接列表.

我听说有两种方法可以在图表中找到一个循环:

1. 保留一个布尔值数组,以跟踪您之前是否访问过某个节点.如果你的新节点用完了(没有点击你已经存在的节点),那么只需回溯并尝试不同的分支.

2. 来自Cormen的CLRS或Skiena的那个:对于无向图中的深度优先搜索,有两种类型的边,树和背.当且仅当存在后沿时,该图具有循环.

有人可以解释一下图的后边缘是什么,以及上述两种方法之间的差异是什么.

谢谢.

更新: 这是在两种情况下检测周期的代码.Graph是一个简单的类,为了简单起见,将所有图形节点表示为唯一编号,每个节点都有其相邻的相邻节点(g.getAdjacentNodes(int)):

public class Graph {

  private int[][] nodes; // all nodes; e.g. int[][] nodes = {{1,2,3}, {3,2,1,5,6}...};

  public int[] getAdjacentNodes(int v) {
    return nodes[v];
  }

  // number of vertices in a graph
  public int vSize() {
    return nodes.length;
  }

}

用于检测无向图中的循环的Java代码:

    public class DFSCycle {

    private boolean marked[];
    private int s;
    private Graph g;
    private boolean hasCycle;

    // s - starting node
    public DFSCycle(Graph g, int s) {
        this.g = g;
        this.s = …

在我的MySQL模式中,我有category(id, parentid, name)表

在MSSQL中,我有CTE查询(从下到上为所提供的类别ID构建一个类别树:

with CTE (id, pid, name) 
as
(
    select id, parentid as pid,name
    from category
    where id = 197
      union all
        select CTE.pid as id , category.parentid as pid, category.name
        from CTE 
          inner join category 
            on category.id = CTE.pid
 )
 select * from CTE 

如何将该查询"转换"为MySQL？

我花了最后几个小时试图在线找到这个问题的解决方案.我已经找到了很多关于如何从嵌套集转换为邻接的例子......但很少有相反的方法.我发现的示例要么不起作用,要么使用MySQL程序.不幸的是,我无法使用此项目的程序.我需要一个纯PHP解决方案.

我有一个使用下面的邻接模型的表:

id          parent_id         category
1           0                 Books
2           0                 CD's
3           0                 Magazines
4           1                 Books/Hardcover
5           1                 Books/Large Format
6           3                 Magazines/Vintage

我想将它转换为下面的嵌套集:

id    left    right          category
0     1       14             Root Node
1     2       7              Books
4     3       4              Books/Hardcover
5     5       6              Books/Large Format
2     8       9              CD's
3     10      13             Magazines
6     11      12             Magazines/Vintage

这是我需要的图像:

我有一个函数,基于此论坛帖子的伪代码(http://www.sitepoint.com/forums/showthread.php?t=320444),但它不起作用.我得到多个具有相同左侧值的行.这不应该发生.

<?php

/**

--
-- Table structure for table `adjacent_table`
--

CREATE TABLE IF NOT EXISTS `adjacent_table` ( …

在CLRS消费税22.1-8(我自学,不在任何大学)

假设每个数组条目Adj [u]不是链表,而是包含顶点v的哈希表,其中(u,v)∈E.如果所有边缘查找都具有相同的可能性,那么确定是否是边缘在图中？这个方案有什么缺点？为每个边缘列表建议一个替代数据结构来解决这些问题.与哈希表相比,您的替代方案是否有缺点？

因此,如果我用哈希表替换每个链表,则存在以下问题:

1. 确定边是否在图中的预期时间是多少？
2. 有什么缺点？
3. 为每个边缘列表建议一个替代数据结构来解决这些问题
4. 与哈希表相比,您的替代方案是否有缺点？

我有以下部分答案:

1. 我认为预期的时间是O(1),因为我只是去Hashtable t = Adj [u],然后返回t.get(v);
2. 我认为缺点是Hashtable会占用更多的空间然后链表.

对于其他两个问题,我无法得到线索.

任何人都可以给我一个线索？

我正在进行一项任务,其中一个问题要求导出一个算法,以检查有向图G =(V,E)是否是单独连接的(对于所有不同的顶点u,最多有一条从u到v的简单路径, v的v

当然你可以蛮力检查它,这就是我现在正在做的事情,但我想知道是否有更有效的方法.有人能指出我正确的方向吗？

我试图从具有父ID的平面数组生成分层树对象.

// `parent` represents an ID and not the nesting level.
var flat = [
    { id: 1, name: "Business", parent: 0 },
    { id: 2, name: "Management", parent: 1 },
    { id: 3, name: "Leadership", parent: 2 },
    { id: 4, name: "Finance", parent: 1 },
    { id: 5, name: "Fiction", parent: 0 },
    { id: 6, name: "Accounting", parent: 1 },
    { id: 7, name: "Project Management", parent: 2  }
];

最终的树对象应如下所示:

{ 
    id: 1, 
    name: "Business", 
    children: …

有一段时间我一直在努力解决如何最好地处理SQL中的层次结构.由于邻接列表的限制和MPTT /嵌套集的复杂性而感到沮丧,我开始考虑简单地存储密钥路径,作为一个简单的node_key/node_key/...字符串.我决定编译这三种技术的优点和缺点:

创建/删除/移动节点所需的呼叫数:

• 邻接= 1
• MPTT = 3
• Path = 1(用包含该路径的所有节点上的新节点路径替换旧节点路径)

获取树所需的调用次数:

• 邻接= [子级数]
• MPTT = 1
• 路径= 1

获取节点/祖先路径所需的调用次数:

• 邻接= [超级数]
• MPTT = 1
• 路径= 0

获取子节点数所需的调用次数:

• 邻接= [子级数]
• MPTT = 0(可以从右/左值计算)
• 路径= 1

获取节点深度所需的调用次数:

• 邻接= [超级数]
• MPTT = 1
• 路径= 0

需要DB字段:

• 邻接= 1(父)
• MPTT = 3(父,右,左)
• 路径= 1(路径)

结论

除了一个用例之外,存储的路径技术使用与每个用例中的其他技术相同或更少的调用.通过这种分析,存储路径是明显的赢家.更不用说,它实现起来要简单得多,人类可读等等.

所以问题是,不应该将存储路径视为比MPTT更强大的技术吗？为什么存储路径不是更常用的技术,为什么不在给定实例中使用它们而不是MPTT？

另外,如果您认为此分析不完整,请告诉我们.

更新:

这里至少有两件事MPTT可以开箱即用,存储的路径解决方案不会:

1. 允许计算每个节点的子节点数,而无需任何其他查询(如上所述).
2. 在给定级别的节点上强加订单.其他解决方案是无序的.

你好,我理解邻接列表和矩阵的概念,但我很困惑如何在Python中实现它们:

实现以下两个示例的算法实现但不知道从一开始的输入,因为他们在他们的示例中对其进行硬编码:

对于邻接列表:

    a, b, c, d, e, f, g, h = range(8) 
    N = [ 
     {b:2, c:1, d:3, e:9, f:4},    # a 
     {c:4, e:3},                   # b 
     {d:8},                        # c 
     {e:7},                        # d 
     {f:5},                        # e 
     {c:2, g:2, h:2},              # f 
     {f:1, h:6},                   # g 
     {f:9, g:8}                    # h 
   ] 

对于邻接矩阵:

    a, b, c, d, e, f, g, h = range(8) 
    _ = float('inf') 
    #     a b c d e f g h
    W = [[0,2,1,3,9,4,_,_], # a 
        [_,0,4,_,3,_,_,_], # …

我的问题很简单:我需要从边列表中创建一个邻接列表/矩阵.

我有一个边缘列表存储在csv文档中,其中column1 = node1和column2 = node2,我想将其转换为加权邻接列表或加权邻接矩阵.

更确切地说,这是数据的样子 - 数字只是节点ID:

node1,node2
551,548
510,512
548,553
505,504
510,512
552,543
512,510
512,510
551,548
548,543
543,547
543,548
548,543
548,542

有关如何实现从此转换为加权邻接列表/矩阵的任何提示？这就是我以前决定这样做的方法,但没有成功(由Dai Shizuka提供):

dat=read.csv(file.choose(),header=TRUE) # choose an edgelist in .csv file format
el=as.matrix(dat) # coerces the data into a two-column matrix format that igraph likes
el[,1]=as.character(el[,1])
el[,2]=as.character(el[,2])
g=graph.edgelist(el,directed=FALSE) # turns the edgelist into a 'graph object'

谢谢!