Chương trình C ++ để biểu diễn đồ thị bằng danh sách được liên kết

Ma trận tỷ lệ của đồ thị là một dạng biểu diễn khác của đồ thị để lưu vào bộ nhớ. Ma trận này không phải là ma trận vuông. Bậc của ma trận tỷ lệ là V x E. Trong đó V là số đỉnh và E là số cạnh trong đồ thị.

Trong mỗi hàng của ma trận này, chúng ta đang đặt các đỉnh, và trong mỗi cột, các cạnh được đặt. Trong biểu diễn này cho một cạnh e {u, v}, nó sẽ được đánh dấu bằng 1 cho vị trí u và v của cột e.

Độ phức tạp của biểu diễn Ma trận kề

• Biểu diễn ma trận tỷ lệ chiếm O (V x E) lượng không gian trong khi nó được tính toán. Đối với đồ thị hoàn chỉnh, số cạnh sẽ là V (V-1) / 2. Vì vậy, ma trận tỷ lệ chiếm không gian lớn hơn trong bộ nhớ.

Đầu vào:

Đầu ra:

Thuật toán

add_edge (adj_list, u, v)

Đầu vào - Chữ u và v của cạnh {u, v} và danh sách kề

Đầu ra - Danh sách gần kề của biểu đồ G

Begin
   Append v into the list at index u
   Append u into the list at index v
End

Mã mẫu

#include<iostream>
#include<list>
#include<iterator>
using namespace std;
void displayAdjList(list<int> adj_list[], int v) {
   for(int i = 0; i<v; i++) {
      cout << i << "--->";
      list<int> :: iterator it;
      for(it = adj_list[i].begin(); it != adj_list[i].end(); ++it) {
         cout << *it << " ";
      }
      cout << endl;
   }
}
void add_edge(list<int> adj_list[], int u, int v) {    //add v into the list u, and u into list v
   adj_list[u].push_back(v);
   adj_list[v].push_back(u);
}
main(int argc, char* argv[]) {
   int v = 6; //there are 6 vertices in the graph
   //create an array of lists whose size is 6
   list<int> adj_list[v];
   add_edge(adj_list, 0, 4);
   add_edge(adj_list, 0, 3);
   add_edge(adj_list, 1, 2);
   add_edge(adj_list, 1, 4);
   add_edge(adj_list, 1, 5);
   add_edge(adj_list, 2, 3);
   add_edge(adj_list, 2, 5);
   add_edge(adj_list, 5, 3);
   add_edge(adj_list, 5, 4);
   displayAdjList(adj_list, v);
}

Đầu ra

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