跳到主要内容

邻接列表

提示
  1. 定义和结构：邻接表是一种用于表示图的数据结构，其中数组的每个索引表示一个顶点，每个元素是一个链表，代表与该顶点相连的其他顶点。
  2. 优点：邻接表在存储上非常高效，特别是对于边数较少的稀疏图，因为它只存储边的值，还便于快速查找与某个顶点相邻的所有顶点。
  3. 缺点：与邻接矩阵相比，邻接表在查找特定边上可能不够快，因为它需要遍历链表来找到相邻的节点。

邻接表将图表示为一个链表数组。数组的索引代表一个顶点，数组中的每个元素代表与该顶点形成边的其他顶点。

例如，我们有一个如下所示的图。

一个图

我们可以将这个图表示为计算机上的链表，如下所示。

图的邻接表表示

在这里，0、1、2、3是顶点，每个顶点都与其所有相邻顶点形成一个链表。例如，顶点1有两个相邻顶点0和2。因此，图中1与0和2相连。

邻接表的优点​

  • 邻接表在存储方面非常高效，因为我们只需要存储边的值。对于具有数百万个顶点和边的稀疏图，这可以节省大量空间。
  • 它还有助于轻松查找与某个顶点相邻的所有顶点。

邻接表的缺点​

  • 查找邻接表不如邻接矩阵快，因为必须首先探索所有连接的节点以找到它们。

邻接表结构​

最简单的邻接表需要一个节点数据结构来存储一个顶点，以及一个图数据结构来组织这些节点。

我们保持与图的基本定义接近 - 顶点和边的集合 {V, E}。为了简单起见，我们使用未标记的图，而不是带标签的图，即顶点由它们的索引0,1,2,3等来标识。

让我们深入了解这里使用的数据结构。

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

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

不要让 struct node** adjLists 使你感到不知所措。

我们所说的是我们要存储指向 struct node* 的指针。这是因为我们不知道图会有多少个顶点，所以无法在编译时创建一个链表数组。

C++ 中的邻接表​

它与相同的结构，但通过使用C++的内置列表STL数据结构，我们使结构更加清晰。我们还能够抽象实现的细节。

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

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

Java 中的邻接表​

我们使用Java集合来存储链表数组。

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

LinkedList的类型由你想在其中存储的数据决定。对于带标签的图，你可以存储字典而不是整数。

Python 中的邻接表​

Python之所以受欢迎，有一个原因。一个简单的顶点和其边的字典就足以表示一个图。你可以使顶点本身变得复杂。

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'])}

Python、Java 和 C/C++ 中的邻接表代码​

Python Java C C++

# Python 中的邻接表表示

class AdjNode:
    def __init__(self, value):
        self.vertex = value
        self.next = None


class Graph:
    def __init__(self, num):
        self.V = num
        self.graph = [None] * self.V

    # 添加边
    def add_edge(self, s, d):
        node = AdjNode(d)
        node.next = self.graph[s]
        self.graph[s] = node

        node = AdjNode(s)
        node.next = self.graph[d]
        self.graph[d] = node

    # 打印图
    def print_agraph(self):
        for i in range(self.V):
            print("顶点 " + str(i) + ":", end="")
            temp = self.graph[i]
            while temp:
                print(" -> {}".format(temp.vertex), end="")
                temp = temp.next
            print(" \n")


if __name__ == "__main__":
    V = 5

    # 创建图和边
    graph = Graph(V)
    graph.add_edge(0, 1)
    graph.add_edge(0, 2)
    graph.add_edge(0, 3)
    graph.add_edge(1, 2)

    graph.print_agraph()
// Adjascency List representation in Java

import java.util.*;

class Graph {

  // Add edge
  static void addEdge(ArrayList<ArrayList<Integer>> am, int s, int d) {
    am.get(s).add(d);
    am.get(d).add(s);
  }

  public static void main(String[] args) {

    // Create the graph
    int V = 5;
    ArrayList<ArrayList<Integer>> am = new ArrayList<ArrayList<Integer>>(V);

    for (int i = 0; i < V; i++)
      am.add(new ArrayList<Integer>());

    // Add edges
    addEdge(am, 0, 1);
    addEdge(am, 0, 2);
    addEdge(am, 0, 3);
    addEdge(am, 1, 2);

    printGraph(am);
  }

  // Print the graph
  static void printGraph(ArrayList<ArrayList<Integer>> am) {
    for (int i = 0; i < am.size(); i++) {
      System.out.println("\nVertex " + i + ":");
      for (int j = 0; j < am.get(i).size(); j++) {
        System.out.print(" -> " + am.get(i).get(j));
      }
      System.out.println();
    }
  }
}
// Adjascency List representation in C

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

struct node {
  int vertex;
  struct node* next;
};
struct node* createNode(int);

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

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

// Create a graph
struct Graph* createAGraph(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;
}

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

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

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

int main() {
  struct Graph* graph = createAGraph(4);
  addEdge(graph, 0, 1);
  addEdge(graph, 0, 2);
  addEdge(graph, 0, 3);
  addEdge(graph, 1, 2);

  printGraph(graph);

  return 0;
}
// Adjascency List representation in C++

#include <bits/stdc++.h>
using namespace std;

// 添加边
void addEdge(vector<int> adj[], int s, int d) {
  adj[s].push_back(d);
  adj[d].push_back(s);
}

// 打印图
void printGraph(vector<int> adj[], int V) {
  for (int d = 0; d < V; ++d) {
    cout << "\n 顶点 "
       << d << ":";
    for (auto x : adj[d])
      cout << "-> " << x;
    printf("\n");
  }
}

int main() {
  int V = 5;

  // 创建图
  vector<int> adj[V];

  // 添加边
  addEdge(adj, 0, 1);
  addEdge(adj, 0, 2);
  addEdge(adj, 0, 3);
  addEdge(adj, 1, 2);
  printGraph(adj, V);
}

邻接表的应用​

  • 对于边数较少的图来说，使用邻接表会更快。
最后于 更新