Adjacency list (original) (raw)
In der Graphentheorie sind Adjazenzlisten (oder auch Nachbarschaftslisten) eine Möglichkeit, Graphen zu repräsentieren. Dabei wird für jeden Knoten eine Liste, die Adjazenzliste, aller seiner Nachbarn (in ungerichteten Graphen) bzw. Nachfolger (in gerichteten Graphen) angegeben. Oft basieren Datenstrukturen für Graphen auf Adjazenzlisten. Im einfachsten Fall wird in einem Array für jeden Knoten eine einfach verkettete Liste aller Nachbarn gespeichert.
| Property | Value |
|---|---|
| dbo:abstract | In der Graphentheorie sind Adjazenzlisten (oder auch Nachbarschaftslisten) eine Möglichkeit, Graphen zu repräsentieren. Dabei wird für jeden Knoten eine Liste, die Adjazenzliste, aller seiner Nachbarn (in ungerichteten Graphen) bzw. Nachfolger (in gerichteten Graphen) angegeben. Oft basieren Datenstrukturen für Graphen auf Adjazenzlisten. Im einfachsten Fall wird in einem Array für jeden Knoten eine einfach verkettete Liste aller Nachbarn gespeichert. (de) In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs. (en) En algorithmique, une liste d'adjacence est une structure de données utilisée pour représenter un graphe. Cette représentation est particulièrement adaptée aux graphes creux (c'est-à-dire peu denses), contrairement à la matrice d'adjacence adaptée aux graphes denses. (fr) En teoría de grafos, una lista de adyacencia es una representación de todas las aristas o arcos de un grafo mediante una lista. Si el grafo es no dirigido, cada entrada es un conjunto o multiconjunto de dos vértices conteniendo los dos extremos de la arista correspondiente. Si el grafo es dirigido, cada entrada es una tupla de dos nodos, uno denotando el nodo fuente y el otro denotando el nodo destino del arco correspondiente. Típicamente, las listas de adyacentes no son ordenadas. (es) 隣接リスト（英: adjacency list）は、グラフ理論でのグラフにある頂点または辺を全てリスト（一覧）で表現したものである。 一般に隣接リストでは順序は不定である。 (ja) 인접 리스트(adjacency list)는 그래프 이론에서 그래프를 표현하기 위한 방법 중 하나이다. 그래프의 한 꼭짓점에서 연결되어 있는 꼭짓점들을 하나의 연결 리스트로 표현하는 방법이다. 인접 행렬에 비하여 변이 희소한 그래프에 효율적이다. (ko) In algebra computazionale, le liste di adiacenza sono una modalità di rappresentazione in memoria di grafi. È probabilmente la rappresentazione più immediata a cui è possibile pensare e la più semplice da implementare, anche se in generale non la più efficiente in termini di spazio occupato. Un semplice grafo; accanto ad ogni vertice è riportata la sua lista di adiacenze. L'idea della rappresentazione è semplicemente che ad ogni vertice viene associata una lista contenente tutti e soli i vertici tali che esista l'arco da a . Supponendo di memorizzare tutte le coppie del tipo (n, L), dove L è la lista di adiacenza del vertice n-esimo, si ottiene una descrizione univoca del grafo. In alternativa, se si stabilisce di ordinare le liste di adiacenza, non è necessario memorizzare esplicitamente anche gli indici n dei vertici. (it) Список смежности — один из способов представления графа в виде коллекции списков вершин. Каждой вершине графа соответствует список, состоящий из «соседей» этой вершины. (ru) Em teoria dos grafos, uma lista de adjacência, estrutura de adjacência ou dicionário é a representação de todas arestas ou arcos de um grafo em uma lista. Se o grafo é não direcionado, cada entrada é um conjunto (ou multiconjunto) de dois nós contendo as duas extremidades da aresta correspondente; se ele for dirigido, cada entrada é uma tupla de dois nós, um indicando o nó de origem e o outro denotando o nó destino do arco correspondente. Normalmente, as listas de adjacência são desordenadas. (pt) 在图论和计算机科学中，邻接表（英语：adjacency list）是表示了图中与每一个顶点相邻的边集的集合，这里的集合指的是无序集。 如果是无向图，那么每条边由两个结点组成，分别代表边的两个端点；如果是有向图，那么每条边是一个，分别代表边的始点和终点。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Simple_cycle_graph.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.boost.org/libs/graph http://www.ics.uci.edu/~eppstein/161/960201.html http://opendatastructures.org/versions/edition-0.1e/ods-java/12_2_AdjacencyLists_Graph_a.html |
| dbo:wikiPageID | 392431 (xsd:integer) |
| dbo:wikiPageLength | 9124 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1102846197 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Pat_Morin dbr:Degree_(graph_theory) dbr:Matrix_(mathematics) dbr:Graph_(discrete_mathematics) dbr:Computer_science dbr:Locality_of_reference dbr:Adjacency_matrix dbr:Graph_(abstract_data_type) dbr:Graph_theory dbr:Guido_van_Rossum dbr:Hash_table dbr:Array_data_structure dbc:Graph_data_structures dbr:Vertex_(graph_theory) dbr:Boost_Graph_Library dbr:Singly_linked_list dbr:Object_oriented dbr:Binary_search dbr:Sequential_search dbr:Sparse_graph dbr:File:Simple_cycle_graph.svg |
| dbp:wikiPageUsesTemplate | dbt:Cite_web dbt:Commons_category dbt:Math dbt:Reflist dbt:Short_description dbt:Abs dbt:Graph_representations |
| dct:subject | dbc:Graph_data_structures |
| gold:hypernym | dbr:Collection |
| rdf:type | yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:PsychologicalFeature100023100 yago:WikicatGraphDataStructures dbo:Book yago:Structure105726345 |
| rdfs:comment | In der Graphentheorie sind Adjazenzlisten (oder auch Nachbarschaftslisten) eine Möglichkeit, Graphen zu repräsentieren. Dabei wird für jeden Knoten eine Liste, die Adjazenzliste, aller seiner Nachbarn (in ungerichteten Graphen) bzw. Nachfolger (in gerichteten Graphen) angegeben. Oft basieren Datenstrukturen für Graphen auf Adjazenzlisten. Im einfachsten Fall wird in einem Array für jeden Knoten eine einfach verkettete Liste aller Nachbarn gespeichert. (de) In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs. (en) En algorithmique, une liste d'adjacence est une structure de données utilisée pour représenter un graphe. Cette représentation est particulièrement adaptée aux graphes creux (c'est-à-dire peu denses), contrairement à la matrice d'adjacence adaptée aux graphes denses. (fr) En teoría de grafos, una lista de adyacencia es una representación de todas las aristas o arcos de un grafo mediante una lista. Si el grafo es no dirigido, cada entrada es un conjunto o multiconjunto de dos vértices conteniendo los dos extremos de la arista correspondiente. Si el grafo es dirigido, cada entrada es una tupla de dos nodos, uno denotando el nodo fuente y el otro denotando el nodo destino del arco correspondiente. Típicamente, las listas de adyacentes no son ordenadas. (es) 隣接リスト（英: adjacency list）は、グラフ理論でのグラフにある頂点または辺を全てリスト（一覧）で表現したものである。 一般に隣接リストでは順序は不定である。 (ja) 인접 리스트(adjacency list)는 그래프 이론에서 그래프를 표현하기 위한 방법 중 하나이다. 그래프의 한 꼭짓점에서 연결되어 있는 꼭짓점들을 하나의 연결 리스트로 표현하는 방법이다. 인접 행렬에 비하여 변이 희소한 그래프에 효율적이다. (ko) Список смежности — один из способов представления графа в виде коллекции списков вершин. Каждой вершине графа соответствует список, состоящий из «соседей» этой вершины. (ru) Em teoria dos grafos, uma lista de adjacência, estrutura de adjacência ou dicionário é a representação de todas arestas ou arcos de um grafo em uma lista. Se o grafo é não direcionado, cada entrada é um conjunto (ou multiconjunto) de dois nós contendo as duas extremidades da aresta correspondente; se ele for dirigido, cada entrada é uma tupla de dois nós, um indicando o nó de origem e o outro denotando o nó destino do arco correspondente. Normalmente, as listas de adjacência são desordenadas. (pt) 在图论和计算机科学中，邻接表（英语：adjacency list）是表示了图中与每一个顶点相邻的边集的集合，这里的集合指的是无序集。 如果是无向图，那么每条边由两个结点组成，分别代表边的两个端点；如果是有向图，那么每条边是一个，分别代表边的始点和终点。 (zh) In algebra computazionale, le liste di adiacenza sono una modalità di rappresentazione in memoria di grafi. È probabilmente la rappresentazione più immediata a cui è possibile pensare e la più semplice da implementare, anche se in generale non la più efficiente in termini di spazio occupato. Un semplice grafo; accanto ad ogni vertice è riportata la sua lista di adiacenze. L'idea della rappresentazione è semplicemente che ad ogni vertice viene associata una lista contenente tutti e soli i vertici tali che esista l'arco da a . (it) |
| rdfs:label | Adjazenzliste (de) Adjacency list (en) Lista de adyacencia (es) Lista di adiacenza (it) Liste d'adjacence (fr) 인접 리스트 (ko) 隣接リスト (ja) Lista de adjacência (pt) Список смежности (ru) 邻接表 (zh) |
| owl:sameAs | freebase:Adjacency list yago-res:Adjacency list wikidata:Adjacency list dbpedia-de:Adjacency list dbpedia-es:Adjacency list dbpedia-fa:Adjacency list dbpedia-fr:Adjacency list dbpedia-it:Adjacency list dbpedia-ja:Adjacency list dbpedia-ko:Adjacency list dbpedia-pt:Adjacency list dbpedia-ro:Adjacency list dbpedia-ru:Adjacency list dbpedia-sr:Adjacency list dbpedia-th:Adjacency list dbpedia-vi:Adjacency list dbpedia-zh:Adjacency list https://global.dbpedia.org/id/2Undf |
| prov:wasDerivedFrom | wikipedia-en:Adjacency_list?oldid=1102846197&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Simple_cycle_graph.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Adjacency_list |
| is dbo:wikiPageRedirects of | dbr:Adjacency_List dbr:Incidence_list dbr:Adjacency-list_representation dbr:Adjacency_List_Model dbr:Adjacency_list_model dbr:Adjacency_lists dbr:Adjacency_table |
| is dbo:wikiPageWikiLink of | dbr:Prim's_algorithm dbr:Quantum_complexity_theory dbr:List_of_data_structures dbr:List_of_graph_theory_topics dbr:Cycle_(graph_theory) dbr:Neighbourhood_(graph_theory) dbr:Object_graph dbr:Glossary_of_graph_theory dbr:NEST_(software) dbr:Combinatorial_species dbr:Component_(graph_theory) dbr:Computational_complexity_theory dbr:Priority_queue dbr:Trivial_Graph_Format dbr:Tree_(data_structure) dbr:Karger's_algorithm dbr:Adjacency_matrix dbr:Breadth-first_search dbr:Graph_(abstract_data_type) dbr:Graph_theory dbr:Adjacency_List dbr:State-transition_table dbr:Edge_list dbr:Hierarchical_database_model dbr:Dijkstra's_algorithm dbr:Boolean_satisfiability_algorithm_heuristics dbr:Sparse_matrix dbr:Implicit_graph dbr:Kosaraju's_algorithm dbr:Incidence_list dbr:Nested_set_model dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Streaming_algorithm dbr:Sparse_network dbr:Task_allocation_and_partitioning_in_social_insects dbr:Adjacency-list_representation dbr:Adjacency_List_Model dbr:Adjacency_list_model dbr:Adjacency_lists dbr:Adjacency_table |
| is foaf:primaryTopic of | wikipedia-en:Adjacency_list |
