Thực hiện biểu đồ biểu đồ danh sách kề

Question

Tôi vừa mới bắt đầu với lý thuyết đồ thị. Tôi không thể tìm ra cách để mã danh sách kề nhau bằng cách sử dụng danh sách liên kết. ví dụ: nếu tôi có biểu đồ này (không được hướng dẫn):

A--------B 
|  /|\ 
| /| \ 
| /| \ 
| / | \ 
| / | \ 
|/ |  \ 
|/ |  \ 
C  E-------D 

Làm cách nào để mã? Tôi biết làm thế nào để làm điều đó bằng cách sử dụng ma trận kề, nhưng làm thế nào để mã nó bằng cách sử dụng danh sách kề và danh sách liên kết (c + +)?

Answer 1

Danh sách kề chỉ là một vectơ/mảng của danh sách. Mỗi phần tử trong biểu đồ là một phần tử trong mảng và mọi cạnh được thêm vào danh sách kề kề của nó. Vì vậy nó trông giống như sau:

A -> {B, C}

B -> {A, C, D, E}

C -> {A, B}

D -> {B, E}

E -> {B, D}

Vì vậy, chúng ta bắt đầu với một cái gì đó giống như std::vector<std::list<vertex>>. Tuy nhiên, chúng ta có thể làm tốt hơn điều này, bởi vì các đỉnh là duy nhất, do đó chúng ta có thể sử dụng map. Hơn nữa, một đỉnh chỉ có thể xuất hiện trong danh sách cạnh một lần, vì vậy chúng tôi sửa đổi nó thành std::map<vertex, std::set<vertex>>.

Vì vậy, để bắt đầu, một cái gì đó như:

struct vertex 
{ 
    // 
}; 

class undirected_graph 
{ 
private: 
    std::map<vertex, std::set<vertex>> graph_container; 
public: 
    void add_vertex(const vertex& v) { //add a vertex to the map } 
    void add_edge(const vertex& v, const vertex& u) { //look up vertex in map and add to the vertex adjacency list } 
    //Other methods 
    //... 
}; 

Answer 2

Danh sách kề chỉ là một tập hợp các đối tượng đại diện cho các cạnh của biểu đồ.

struct edge { 
    node *nodes[2]; 

    edge(node *a, node *b) { 
     if (a < b) { // define canonical order of edges for undirected graph 
      nodes[0] = a; 
      nodes[1] = b; 
     } else { 
      nodes[0] = b; 
      nodes[1] = a; 
     } 
    } 
}; 

Danh sách được liên kết không có vẻ đặc biệt thiết thực; thông thường bạn sẽ xác định thứ tự các cạnh và đặt chúng trong một số std::set hoặc std::map.

bool operator< (edge const &lhs, edge const &rhs) { 
    if (lhs.nodes[0] < rhs.nodes[0]) return true; 
    if (rhs.nodes[0] < lhs.nodes[0]) return false; 
    return lhs.nodes[1] < rhs.nodes[1]; 
} 

typedef std::set<edge> graph; 

Có nhiều cách để thực hiện việc này, thật khó để đề xuất thêm bất cứ điều gì mà không biết bạn định làm gì với biểu đồ.