Nachbarschaftsliste

Tree, Дерево, Алгоритм

Adjazenzliste stellt ein Diagramm als ein Array aus verknüpften Listen dar.

Der Array-Index stellt einen Scheitelpunkt und jedes Element in seiner verknüpften Liste dar und stellt auch andere Scheitelpunkte dar, die mit dem Scheitelpunkt eine Kante bilden.

Stellt eine Nachbarschaftsliste dar

Der Graph und seine äquivalente Adjazenzlistendarstellung sind unten gezeigt.

Die Adjazenzliste ist speichereffizient, da wir nur Werte für Kanten speichern müssen. Für einen spärlichen Graphen mit Millionen von Scheitelpunkten und Kanten kann dies bedeuten, dass viel Platz gespart wird.

Die Struktur der Adjazenzliste

Die einfachste Adjazenzliste erfordert eine Knotendatenstruktur zum Speichern des Scheitelpunkts und eine Graphendatenstruktur zum Organisieren der Knoten.

Wir nähern uns der grundlegenden Definition eines Graphen – der Sammlung von Ecken und Kanten {V, E}. Der Einfachheit halber verwenden wir einen unbeschrifteten Graphen, keinen beschrifteten, das heißt, die Eckpunkte werden durch ihre Indizes 0,1,2,3 identifiziert.

Werfen wir einen Blick auf die folgende Datenstruktur.

struct node
{
    int vertex;
    struct node* next;
};
struct Graph
{
    int numVertices;
    struct node** adjLists;
};

Lassen Sie sich nicht von struct node* adjLists überwältigen.
Wir müssen den struct node -Zeiger speichern. Da wir nicht wissen, wie viele Scheitelpunkte der Graph enthalten wird, können wir zur Kompilierzeit kein Array verknüpfter Listen erstellen.

Nachbarschaftsliste C++

Es ist die gleiche Struktur, aber mit der in C++ eingebauten Liste von STL-Datenstrukturen machen wir die Struktur etwas sauberer. Wir können auch Implementierungsdetails abstrahieren.

class Graph
{
    int numVertices;
    list<int> *adjLists;

public:
    Graph(int V);
    void addEdge(int src, int dest);
};

Java-Nachbarschaftsliste

Wir verwenden Java-Sammlungen, um ein Array von verknüpften Listen zu speichern.

class Graph
{
    private int numVertices;
    private LinkedList<integer> adjLists[];
}

Der LinkedList-Typ bestimmt, welche Art von Daten Sie darin speichern möchten. Für ein beschriftetes Diagramm können Sie anstelle eines ganzzahligen Werts ein Wörterbuch speichern.

Python-Nachbarschaftsliste

Es gibt einen Grund, warum Python so viel "Liebe" bekommt. Ein einfaches Wörterbuch von Ecken und Kanten ist eine ausreichende Darstellung eines Graphen. Sie können das Oberteil so komplex gestalten, wie Sie möchten.

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

C Adjazenzlistencode

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int vertex;
    struct node* next;
};
struct node* createNode(int);
struct Graph
{
    int numVertices;
    struct node** adjLists;
};
struct Graph* createGraph(int vertices);
void addEdge(struct Graph* graph, int src, int dest);
void printGraph(struct Graph* graph);
int main()
{
    struct Graph* graph = createGraph(6);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 4);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 4);
    addEdge(graph, 4, 6);
    addEdge(graph, 5, 1);
    addEdge(graph, 5, 6);

    printGraph(graph);

    return 0;
}


struct node* createNode(int v)
{
    struct node* newNode = malloc(sizeof(struct node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

struct Graph* createGraph(int vertices)
{
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    graph->adjLists = malloc(vertices * sizeof(struct node*));

    int i;
    for (i = 0; i < vertices; i++)
        graph->adjLists[i] = NULL;

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest)
{
    // Add edge from src to dest
    struct node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // Add edge from dest to src
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

void printGraph(struct Graph* graph)
{
    int v;
    for (v = 0; v < graph->numVertices; v++)
    {
        struct node* temp = graph->adjLists[v];
        printf("\n Adjacency list of vertex %d\n ", v);
        while (temp)
        {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

C++ Adjazenzlistencode

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

class Graph
{
    int numVertices;
    list *adjLists;

public:
    Graph(int V);
    void addEdge(int src, int dest);
};

Graph::Graph(int vertices)
{
    numVertices = vertices;
    adjLists = new list[vertices];
}

void Graph::addEdge(int src, int dest)
{
    adjLists[src].push_front(dest);
}


int main()
{
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 3);

    return 0;
}

Code der Java-Nachbarschaftsliste

import java.io.*;
import java.util.*;
class Graph
{
    private int numVertices;
    private LinkedList<Integer> adjLists[];

    Graph(int vertices)
    {
        numVertices = vertices;
        adjLists = new LinkedList[vertices];

        for (int i = 0; i < vertices; i++)
            adjLists[i] = new LinkedList();
    }

    void addEdge(int src, int dest)
    {
        adjLists[src].add(dest);
    }

    public static void main(String args[])
    {
        Graph g = new Graph(4);

         g.addEdge(0, 1);
         g.addEdge(0, 2);
         g.addEdge(1, 2);
         g.addEdge(2, 3);
    }
}