Chuyển danh sách kề sang ma trận kề C++

Việc biểu diễn đồ thị vô hướng được suy ra từ biểu diễn đồ thị có hướng bằng cách coi một cạnh (i; j) trong đồ thị vô hướng là hai cung (i; j) và (j; i) trong đồ thị có hướng. Sau đây trình bày cách biểu diễn đồ thị có hướng G(V,E) trong đó V là tập đỉnh gồm N đỉnh (đánh số từ 0 đến N-1), E là tập cung gồm M cung e(i;j).

1. Biểu diễn đồ thị bằng ma trận kề: Dùng mảng hai chiều A[N][N]: A[i][j] =1 khi và chỉ khi có cung e(i;j) nối từ đỉnh i tới đỉnh j; A[i][j] =0 khi và chỉ khi không có cung nối từ đỉnh i tới đỉnh j;
2. Biểu diễn đồ thị bằng danh sách cạnh: Dùng mảng một chiều e[M] gồm M phần tử, mỗi phần tử là một bản cấu trúc có hai trường chính là x và y: e[k].x=i và e[k].y=j khi và chỉ khi đồ thị có cung thứ k là cung (i;j) với 0≤k<
3. Biểu diễn đồ thị bằng danh sách kề:      Cách cài đặt phổ biến là Forward Star dùng hai mảng adj[M] và head[N]. Mảng adj[M] có các phần tử là số hiệu các đỉnh, mảng này gồm N đoạn, đoạn thứ u lưu số hiệu các đỉnh kề với đỉnh u (cung đi ra từ u), phần tử đầu tiên của đoạn thứ u là phần tử có chỉ số head[u]+1 của mảng adj, phần tử cuối cùng của đoạn thứ u là phần tử có chỉ số head[u+1] của mảng adj. Ngoài ra trong một số trường hợp còn cài đặt danh sách kề bằng Reverse Star : Với mỗi đỉnh v lưu trữ một đoạn trong mảng adj[M] chứa số hiệu các đỉnh nối tới v (cung đi vào v), mà head[v]+1 là chỉ số của phần tử đầu tiên của đoạn này.
4. Biểu diễn đồ thị bằng danh sách liên thuộc: Dùng hai mảng link[maxM] và head[maxN]. Mỗi đỉnh cho tương ứng một danh sách các cung liên thuộc đi ra từ đỉnh đó. Head[i] là chỉ số cung đầu tiên trong danh sách các cung liên thuộc đi ra từ đỉnh i; nếu từ đỉnh i không có cung nào đi ra thì gán head[i]=0. Còn link[j] là chỉ số cung kế tiếp cung có chỉ số j; link[j]=0 là thể hiện cung có chỉ số j là cung cuối cùng trong các cung liên thuộc đi ra từ đỉnh

Danh sách kề được sử dụng thuận lợi trong nhiều bài toán, do đó cần biết cách chuyển đổi giữa danh sách kề với ma trận kề hoặc danh sách cạnh.

Chuyển đổi từ ma trận kề sang danh sách kề:

   int pos = -1;

   for (int i=0; i