C++: Tạo danh sách kề trong C++ sử dụng biểu đồ có hướng


Đăng ký nhận thông báo về những video mới nhất

Bài viết này sẽ nói về việc tạo một danh sách kề cho một đồ thị có hướng, nó có dạng như sau:

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

Đây sẽ là một đồ thị có hướng với V0 (đỉnh 0) có Edge to V1 và V3, V1 có Edge to V2 và V2 có Edge to V4, dạng như thế này:

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

Để làm điều này, ta sẽ cần tạo một danh sách kề trong C++. Một danh sách kề về cơ bản là một các danh sách được liên kết. Xét ví dụ đoạn giả mã sau:

#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
}

Ta mong muốn có thể lặp qua danh sách kề ở trên để có thể áp dụng vào đồ thị. Ví dụ, để thực hiện một số thuật toán lý thuyết đồ thị (sắp xếp, đường dẫn ngắn nhất, v.v.) bằng cách sử dụng biểu diễn danh sách kề.

Bạn có thể sử dụng một vector trong nút, như một danh sách kề.

class node {
  int value;
  vector<node*> neighbors;
 };

Nếu biểu đồ được biết tại thời gian biên dịch, bạn có thể sử dụng mảng, nhưng khó hơn "một chút". Nếu bạn chỉ biết kích thước của biểu đồ (tại thời gian biên dịch), bạn có thể làm là như sau:

template<unsigned int N>
class graph {
  array<node, N> nodes;
 }

Để thêm một danh sách kề, bạn làm như sau:

nodes[i].neighbors.Push_back(nodes+j); //or &nodes[j]

Tất nhiên, bạn có thể thực hiện danh sách kề không con trỏ và làm việc "phía trên" một bảng. Bạn có vector<int> trong nút và bạn đưa cạnh kề vào. Với cả hai biểu diễn của biểu đồ, bạn có thể nhận ra tất cả các thuật toán sử dụng danh sách kề.

Và cuối cùng, ta có thể sử dụng một danh sách thay vì một vectơ, vì việc xóa sẽ có độ phức tạp O(1). Tuy nhiên, đối với hầu hết các thuật toán, thứ tự trong danh sách kề là không quan trọng. Vì vậy, bạn có thể xóa bất kỳ phần tử nào khỏi vectơ trong thời gian O(1) . Chỉ cần hoán vị nó với phần tử cuối cùng, khi đó pop_back là O(1):

if(i != number_of_last_element_in_list) //neighbors.size() - 1
 swap(neighbors[i], neighbor.back());
neighbors.pop_back();

Ví dụ cụ thể:

//creation of nodes, as previously
constexpr unsigned int N = 3;
array<node,N> nodes; //or array<node, 3> nodes;
//creating Edge (adding neighbors), in the constructor, or somewhere
nodes[0].neighbors = {&nodes[1]};
nodes[1].neighbors = {&nodes[0], &nodes[1]};
//adding runtime, i,j from user, eg. i = 2, j = 0
nodes[i].neighbors.Push_back(&nodes[j]); //nodes[2].neighbors = {&nodes[0]};

Từ 0 bạn có thể đi tới 1, từ 1 đến 0 và đến chính nó, từ 2 đến 0, đó là đồ thị có hướng. Nếu bạn muốn đồ thị vô hướng, bạn nên thêm vào cả hai nút địa chỉ neighbour. Bạn có thể sử dụng số thay vì con trỏ. vector<unsigned int> in class node và đẩy lùi số, không có địa chỉ.

Khi số lượng đỉnh có thể thay đổi, bạn có thể sử dụng vectơ của các nút (vector<node>) thay cho mảng và chỉ thay đổi kích thước, phần còn lại không thay đổi. Ví dụ:

vector<node> nodes(n); //you have n nodes
nodes.emplace_back(); //you added new node, or .resize(n+1)
//here is place to runtime graph generate
//as previously, i,j from user, but now you have 'vector<unsigned int>' in node
nodes[i].neighbors.Push_back(j);

Nhưng bạn không thể xóa một nút, điều này vi phạm việc đánh số! Nếu bạn muốn xóa một cái gì đó, bạn nên sử dụng danh sách (list<node*>) của con trỏ. Nếu không, bạn phải giữ các đỉnh không tồn tại. Ở đây, thứ tự là quan trọng!

Về dòng nodes.emplace_back(); //adding node, nó an toàn với biểu đồ không có con trỏ. Nếu bạn muốn sử dụng con trỏ thì không nên thay đổi kích thước của biểu đồ. Bạn có thể vô tình thay đổi địa chỉ của một số nút, trong khi thêm đỉnh, khi vector sẽ được sao chép sang vị trí mới (ngoài không gian).

Một cách để đối phó với nó là sử dụng dự trữ, mặc dù bạn phải biết kích thước tối đa của biểu đồ! Nhưng trên thực tế tôi khuyến khích bạn không nên sử dụng vector để giữ các đỉnh, khi bạn đang sử dụng các con trỏ. Nếu bạn không biết triển khai, an toàn hơn có thể là quản lý bộ nhớ bản thân (con trỏ thông minh, ví dụ: shared_ptr hoặc new).

node* const graph = new node[size]; //<-- It is your graph.
//Here no address change accidentally.

Sử dụng vector làm danh sách kề luôn luôn tốt, vì không làm thay đổi địa chỉ của nút.

Đây có thể không phải là cách tiếp cận rất chung chung nhưng đó là cách tôi xử lý danh sách kề trong hầu hết các trường hợp. C++ có thư viện STL hỗ trợ cấu trúc dữ liệu cho danh sách được liên kết có tên là list.

Giả sử bạn có các nút N trong biểu đồ, tạo danh sách được liên kết cho mọi nút:

list graph[N];

Bây giờ graph[i] đại diện cho cạnh kề của nút i. Đối với mọi Edge i đến j, hãy làm như sau:

graph[i].Push_back(j);

Tôi đề nghị bạn thêm vào cấu trúc nút danh sách điều chỉnh [.__.] Và xác định cấu trúc biểu đồ là Danh sách các nút thay vì Danh sách danh sách điều chỉnh.

struct node {
    int vertex;
    node* next;
    adjList m_neighbors;
};
struct graph{
    //List of nodes
};
Tôi muốn giới thiệu cách tiếp cận tổng quát và đơn giản hơn về cách sử dụng vectơ và cặp: [.__.] #Icoide [.__.] :
typedef std::pair<int, int> ii; /* the first int is for the data, and the second is for the weight of the Edge - Mostly usable for Dijkstra */
typedef std::vector<ii> vii;
typedef std::vector <vii> WeightedAdjList; /* Usable for Dijkstra -for example */
typedef std::vector<vi> AdjList; /*use this one for DFS/BFS */

Hoặc kiểu bí danh (> = C++ 11):

using ii = std::pair<int,int>;
using vii = std::vector<ii>;
using vi = std::vector<int>;
using WeightedAdjList = std::vector<vii>;
using AdjList = std::vector<vi>;

Cách tiếp cận của tôi sẽ là sử dụng bản đồ băm để lưu trữ danh sách các nút trong biểu đồ:

class Graph {
private:
  unordered_map<uint64_t, Node> nodeList;
  ...
}

Bản đồ lấy ID nút làm khóa và chính nút đó là giá trị. Bằng cách này bạn có thể tìm kiếm một nút trong biểu đồ trong thời gian không đổi.

Nút chứa danh sách kề, trong trường hợp này là một vectơ. Nó cũng có thể là một danh sách được liên kết, mặc dù trong trường hợp sử dụng này sẽ không thấy sự khác biệt về hiệu quả. Có lẽ danh sách sẽ tốt hơn nếu bạn muốn giữ nó được sắp xếp theo cách nào đó.

class Node{
    uint64_t id;     // Node ID
    vector<uint64_t> adjList;  
...
}

Với phương pháp này, bạn phải đi qua danh sách kề và sau đó tìm kiếm bản đồ trên ID để lấy nút. 

Thay vào đó, bạn có thể có một vectơ con trỏ tới các nút lân cận. Điều đó sẽ cho bạn quyền truy cập trực tiếp vào các nút lân cận, nhưng sau đó bạn không thể sử dụng bản đồ để giữ tất cả các nút của mình trong biểu đồ và bạn sẽ mất khả năng tìm kiếm các mục dễ dàng trong biểu đồ của mình.

Như bạn có thể thấy, có rất nhiều quyết định đánh đổi bạn phải đưa ra khi thực hiện một biểu đồ, tất cả phụ thuộc vào thực tế sử dụng của bạn.


Nếu bạn có điều thắc mắc, bạn hãy comment cho V1Study để được giải đáp.
Bài viết này được chia sẻ bởi LongDT. Nếu bạn muốn chia sẻ bài viết, bạn hãy Đăng ký làm thành viên!
« Prev
Next »
Copied !!!