标签: adjacency-list

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

我有一个边缘列表存储在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'

谢谢!

我正在做面试准备和审查图表实现.我一直看到的最重要的是邻接列表和邻接矩阵.当我们考虑基本操作的运行时,为什么我从未看到使用散列的数据结构？

例如,在Java中,通常会使用邻接列表ArrayList<LinkedList<Node>>,但为什么人们不使用HashMap<Node, HashSet<Node>>？

设n =节点数,m =边数.

在这两种实现方式,去掉了节点U包括通过所有的收藏和取出诉搜索.在邻接表,这是为O(n ^ 2),但在"邻接集",这是为O(n).同样,删除边缘涉及从v列表中删除节点u,从u列表中删除节点v.在邻接列表中,那是O(n),而在邻接集中,它是O(1).其他操作,例如查找节点后继,查找两个节点之间是否存在路径等,对于这两种实现都是相同的.空间复杂度也都是O(n + m).

我能想到的邻接集的唯一缺点是添加节点/边是分摊O(1),而在邻接列表中这样做是真正的O(1).

也许我没有看到任何东西,或者我在计算运行时忘了考虑事情,所以请告诉我.

我想用C#创建这个马尔可夫链.我需要知道除了邻接列表之外是否还有其他结构可以在这种情况下更好地工作.另外,我如何使用现有的.Net集合类型来实现它.

我承认这是我的功课.任务声明说我必须编写一个程序,找到一个图形的拓扑顺序,它将由标准输入输入.然后我需要提交它在教授的服务器上评分.

现在不是算法问题.这更像是一个技术问题.在我的计算机中,我使用.NET编译器(csc),而教授的评分机使用某种形式的单声道.

它运作良好,直到平地机说我得到30/100.我的一个朋友建议我使用评分者的"手动输入系统",所以在这里,我让它为邻接列表创建了100000个数组的列表.

几秒钟后,评分者报告说我的程序崩溃了.

Stacktrace:

at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) …

各位大家好:)今天我在图论和数据结构方面提炼技巧.我决定用C++做一个小项目,因为我在C++工作已经有一段时间了.

我想为有向图制作一个邻接列表.换句话说,看起来像:

0-->1-->3
1-->2
2-->4
3-->
4-->

这将是有向图,其中V0(顶点0)具有到V1和V3的边缘,V1具有到V2的边缘,V2具有到V4的边缘,如下所示:

V0----->V1---->V2---->V4
 |
 |
 v
 V3 

我知道为了做到这一点,我需要在C++中创建一个邻接列表. 邻接列表基本上是链表的数组.好的,让我们看一些伪C++代码:

#include <stdio>
#include <iostream>
using namespace std;

struct graph{
//The graph is essentially an array of the adjList struct.  
node* List[];

};

struct adjList{
//A simple linked list which can contain an int at each node in the list.

};

struct node {
int vertex;
node* next;
};

int main() {
//insert cool graph theory sorting algorithm here
}

如你所知,这个伪代码目前还远远不够.这就是我想要的一些帮助 - C++中的指针和结构从来都不是我的强项.首先,这会处理顶点指向的顶点 - …

我对tags表有以下架构:

CREATE TABLE tags (
    id integer NOT NULL,
    name character varying(255) NOT NULL,
    parent_id integer
);

我需要构建一个查询来返回以下结构(为了便于阅读,这里表示为yaml):

- name: Ciencia
  parent_id: 
  id: 7
  children:
  - name: Química
    parent_id: 7
    id: 9
    children: []
  - name: Biología
    parent_id: 7
    id: 8
    children:
    - name: Botánica
      parent_id: 8
      id: 19
      children: []
    - name: Etología
      parent_id: 8
      id: 18
      children: []

经过一些试验和错误,并在SO中寻找类似的问题,我想出了这个问题:

    WITH RECURSIVE tagtree AS (
      SELECT tags.name, tags.parent_id, tags.id, json '[]' children
      FROM tags
      WHERE NOT EXISTS (SELECT 1 …

我有一个表使用Adjacency List模型存储分层信息.(使用自引用键 - 下面的示例.此表可能看起来很熟悉):

category_id name                 parent
----------- -------------------- -----------
1           ELECTRONICS          NULL
2           TELEVISIONS          1
3           TUBE                 2
4           LCD                  2
5           PLASMA               2
6           PORTABLE ELECTRONICS 1
7           MP3 PLAYERS          6
8           FLASH                7
9           CD PLAYERS           6
10          2 WAY RADIOS         6

将上述数据"压扁"成这样的东西的最佳方法是什么？

category_id lvl1        lvl2        lvl3        lvl4
----------- ----------- ----------- ----------- -----------
1           1           NULL        NULL        NULL
2           1           2           NULL        NULL
6           1           6           NULL        NULL
3           1           2           3           NULL
4           1 …

我有一张桌子,其中包含世界上所有地理位置的位置及其关系.

以下是显示层次结构的示例.您将看到数据实际存储为全部三个

• 枚举路径
• 邻接清单
• 嵌套集

数据显然也从未改变过.下面是英格兰布莱顿位置的直接祖先的例子,其中有一个13911的寂寞.

表:( geoplanet_places有560万行) 大图:http://tinyurl.com/68q4ndx

然后,我有一个名为的表entities.此表存储我想要映射到地理位置的项目.我存储了一些基本信息,但最重要的是我存储了woeid哪个是外键geoplanet_places.

最终该entities表将包含数千个实体.我想要一种能够返回包含实体的所有节点的完整树的方法.

我计划创建一些东西,以便根据实体的地理位置过滤和搜索实体,并能够发现在该特定节点上可以找到多少个实体.

所以如果我的表中只有一个实体entities,我可能会有这样的东西

`地球(1)

英国(1)

英格兰(1)

东萨塞克斯郡(1)

布莱顿 - 霍夫市(1)

布莱顿(1)`

让我们说我有另一个位于德文郡的实体,那么它会显示如下:

地球(2)

联合王国(2)

英格兰(2)

德文(1)

东萨塞克斯(1)......等

(计数)将说明每个地理位置"内部"有多少实体不需要是活的.我可以忍受每小时生成我的对象并缓存它.

目标是,能够创建一个界面,可能开始只显示有实体的国家.

所以喜欢

Argentina (1021),Chile (291),...,United States (32,103),United Kingdom (12,338)

然后,用户将点击某个位置,例如United Kindom,然后将获得作为英国后代的所有直接子节点,并且其中包含实体.

如果United Kindgdom中有32个县,但最终只有23个当你向下钻取时存储了实体,那么我不想显示其他9.它只是位置.

本网站恰如其分地表明,我希望实现的功能: http://www.homeaway.com/vacation-rentals/europe/r5

您如何建议我管理这样的数据结构？

我正在使用的东西.

• PHP
• MySQL的
• Solr的

我计划尽可能快地完成钻孔.我想创建一个无缝的AJAX界面进行搜索.

我也有兴趣知道你建议索引哪些列.

我试图用C++实现一个图形.我使用包含两个变量的结构来表示图中的节点 -
a)一个整数,用于包含有关节点的一些信息.
b)包含与其连接的其他顶点的索引的列表.
以下是代码.

// Graphs using adjacency list

#include <iostream>
#include <list>
#include <cstdlib>
using namespace std;

// structure to represent a vertex(node) in a graph
typedef struct vertex{
    int info;
    list<int> adj;   // adjacency list of edges contains the indexes to vertex
} *vPtr;             

int main(){
    vPtr node = (vPtr)malloc(sizeof(struct vertex));
    node->info = 34;            // some arbitrary value
    (node->adj).push_back(2);   // trying to insert a value in the list
    return 0;
}

代码正在编译正常,但是当我推回列表中的元素时,我遇到了运行时错误.我的结构有什么问题吗？
我正在使用代码块和GNU GCC,C++ 98编译器来编译我的代码.

我正在处理分层数据，如树结构。我想知道将它们存储在数据库中的最佳方式是什么。

我从 MySQL 中的邻接表开始。但随着数据的增加，性能似乎会下降。我有大约 20,000 行存储在具有父子关系的 MySQL 表中，并且将来还会增加。获取数据需要很长时间，因为我必须根据树的深度编写许多自连接。

所以我正在寻找存储此类数据的最佳方法。在一次地方，我发现嵌套集比邻接列表更好。然后我被建议考虑 NoSQL，如果这能解决我的问题。所以我现在很困惑是继续使用 SQL 还是进入 No SQL，或者是否有其他最好的方法来处理此类数据。

那么有人可以建议我什么是最好的方法吗？