Biểu diễn đồ thị bằng danh sách kề

Để khắc phục khuyết điểm của list cạnh về việc đào bới tìm kiếm đỉnh kề, nhưng vẫn bảo đảm an toàn tổ chức dữ liệu về tối ưu tuyệt nhất Giao hàng chuyên chú tìm kiếm vào vật dụng thị mà Danh sách kề được Thành lập.

Bạn đang xem: Biểu diễn đồ thị bằng danh sách kề


1. Ý tưởng list kề

a. Ý tưởng

a.1 Tổ chức bằng mảng

Tổ chức tài liệu hình dáng list kề là bạn sẽ lưu các đỉnh kề của một đỉnh vào các đoạn vào mảng để tàng trữ. Nếu có N đỉnh thì sẽ sở hữu N đoạn để lưu. Và họ bắt buộc cất giữ chỉ số nhằm cai quản lí phạm vi những đỉnh kề của đỉnh nhưng mà đoạn kia quản lí.

Các các bạn coi hình ảnh bên dưới để làm rõ rộng ý tưởng này.

Gọi Head là chỉ số ngừng của đoạn quản lí đỉnh kề của i-1. Hay Head+1 là chỉ số ban đầu của đoạn quản lí đỉnh kề của i.

Bởi vậy, chỉ số của đoạn chứa các đỉnh kề của i là trường đoản cú Head+1 đến Head

a.2 Tổ chức bởi danh sách liên kết

Việc tổ chức triển khai bằng list link, bọn họ sẽ sở hữu được một mảng n ô, Mỗi ô đựng một pointer Node, pointer này có 2 đọc tin là chỉ số đỉnh kề và pointer next tiếp theo sau. Tham mê khảo hình dưới (mục thiết đặt bằng list liên kết) để nắm rõ rộng.

b. lấy ví dụ minh họa

Cho đồ dùng thị 1-1 có hướng, tất cả N đỉnh M canh. Dữ liệu các cạnh như sau:


1 21 32 42 32 53 53 64 55 6
1
2
3
4
5
6
7
8
9
1 2
1 3
2 4
2 3
2 5
3 5
3 6
4 5
5 6
*

ví dụ như minc họa tổ chức triển khai list kề bởi mảng một chiều


Thứ nhất bạn chỉ việc hiểu các đỉnh kề của đỉnh uAdj với v=Head+1……Head

Nhỏng hình minh họa bên trên sống đỉnh số 3, bản thân có sơn greed color ví dụ. Dựa vào bài toán khẳng định đỉnh kề bởi Head<> thì mình có được các đỉnh kề của 3 là Adj< Head<3>+1 mang lại Head<3+1>>

Nếu viết bởi c++ thì mình lấy những đỉnh kề của đỉnh u bằng phương pháp sau:


// Minc họa in các đỉnh kề của uvoid indinhke(int u) for (int v=Head+1; v
1
2
3
4
5
6
// Minc họa in những đỉnh kề của u
void indinhke(int u)

for (int v=Head+1; vHead; v++)
cout Adjendl;

c. Độ phức tạp

Độ phức tạp dữ liệu và thời hạn là O(m) cùng với m là số cạnh của vật thị.

2. Cài đặt danh sách kề

a. Tổ chức bởi mảng bởi pascal / C++

Nlỗi đều nội dung bài viết trước về tổ chức tài liệu mang đến định hướng vật dụng thị, mình vẫn gợi ý chúng ta gọi dữ liệu. Dòng đầu vẫn có 2 số N, với m.

Mô tả từng bước:

Ban đầu Head=0Đọc từng cạnh (u,v) cùng tăng Head=Head+1.Cộng dồn Head=Head+Head. i=2->n+1;Lưu ý thêm Head luôn m nếu như chính là đồ thị được bố trí theo hướng.Duyệt qua các cạnh, Adj> = v; Head=Head-1;

Code tổ chức triển khai dữ liệu trang bị thị bằng list kề trong c++


#define NMAX 100#define MMAX 1000//Knhị báo dữ liệu int x, y, Head, Adj;int n, m, u, v;// Đọc dữ liệucin >> n >> m;// Gán Head=0for (int i=0; i> x >> y; Head>++;for (int i=2; i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#define NMAX 100
#define MMAX 1000
//Khai báo dữ liệu
int x, y, Head, Adj;
int n, m, u, v;
// Đọc dữ liệu
cin >> n >> m;
// Gán Head=0
for (int i=0; in+1; i++)
Head=0;
for (int i=1; im; i++)

cin >> x >> y;
Head>++;

for (int i=2; in+1; i++)
Head=Head+Head;
for (int i=1; im; i++)

Head>--;

Code tổ chức triển khai dữ liệu đồ gia dụng thị bởi danh sách kề trong Pascal


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const nmax=100;
mmax=1000;
typedata=longint;
// khai bao du lieu
var
adj:array<0..mmax> of data;
head,u,v:array<0..mmax+1> of data;
//doc du lieu
procedure docfile;
var i,j:data;
begin
read(n,m);
fillchar(head,sizeof(head),0);
for i:=1 to m do
begin
read(f,u,v);
inc(head>);
end;
for i:=2 lớn n+1 do
head:=head+head;
for i:=1 to lớn m do
begin
dec(head>);
end;
end;

// Lúc nhập dữ liệuHead>++;Head>++;
1
2
3
// Lúc nhập dữ liệu
Head>++;
Head>++;

Sau khi cộng dồn head, và tất yếu MMAX cần tăng gấp hai.

Xem thêm: Game Of Thrones Season 7 Tập 2 Vietsub + Thuyết Minh Full Hd


for (int i=1; i
1
2
3
4
5
6
7
8
for (int i=1; im; i++)

Head>--;
Head>--;

Nếu bạn muốn lưu giữ thêm trọng số của cạnh, rất có thể chế tác thêm một mảng bao gồm phương châm giống hệt như adj, nlỗi hôm nay họ sẽ lưu trọng số của bọn chúng.

b. Tổ chức danh sách liên kết


*
Tổ chức tàng trữ vật dụng thị bởi danh sách liên kết


struct Node int info; Node* pNext; Node() pNext=NULL; Node* List;int u,v,m,n;// Nhập số đỉnh cùng số cạnhcin >> n >> m;for (int i=1; i> u >> v; Node *p = new Node(); p->info = v; if (List==NULL) List = p; else p->pNext = List; List = p; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct Node

int info;
Node* pNext;
Node()

pNext=NULL;


Node* List;
int u,v,m,n;
// Nhập số đỉnh cùng số cạnh
cin >> n >> m;
for (int i=1; im; i++)

cin >> u >> v;
Node *p = new Node();
p->info = v;
if (List==NULL)
List = p;
else

p->pNext = List;
List = p;


Duyệt đỉnh kề của u trong list link ra sao ?
// Minc họa in những đỉnh kề của uvoid indinhke(int u) Node *p = List; while (p!=NULL) cout info pNext;
1
2
3
4
5
6
7
8
9
10
// Minch họa in những đỉnh kề của u
void indinhke(int u)

Node *p = List;
while (p!=NULL)

cout p->info endl;
p=p->pNext;


3. Ưu điểm và giảm bớt của danh sách kề

– Ưu điểm của danh sách kề là ngân sách trông nom và lưu trữ hơi buổi tối ưu. Đặc biệt là danh sách kề trong mảng.

– Cài đặt bài toán thù bằng danh sách kề tương đối dài hơn nữa đối với ma trận kề cùng danh sách cạnh.

– Đối cùng với từng bài bác tân oán cụ thể, tùy từng dữ liệu bài xích tân oán đến, chúng ta hãy lựa chọn cách tổ chức tài liệu cân xứng tốt nhất, không duy nhất thiết dịp nào cũng tổ chức danh sách kề.

4. Bài tập ứng dụng

các bài luyện tập về list kề nhìn chung những bạn có thể rước những bài tập bản thân share ngơi nghỉ bài về DFS, BFS về thực chất nó là như nhau.

Bên cạnh đó có thể tìm hiểu thêm danh sách kề khi kết hợp với Prlặng heap: https://vblgroup.vn/cay-khung-nho-nhat-qbmst-spoj-kruskal-prim-heap/


Đồ thị Tổ chức tài liệu trong kim chỉ nan vật thị. permaliên kết.

Xem thêm: Phim Bước Nhảy Xì Tin Tập Cuối, Vtv Giải Trí

Post navigation


Viết mã mối cung cấp tự động thông tin điểm UIT (Phần 2)
Cách đọc ghi tệp tin trong c++

4 thoughts on “Bài 3: Danh sách kề C++ Lý thuyết thứ thị”


*
Vô Danh says:
17 Tháng Ba, 2018 at 21:56

Hay lắm ạ,dễ hiểu hơn sách giáo khoa chăm tin nhiều luôn ạ !!! Cảm ơn ad !


Trả lời

Trả lời Hủy

Email của các bạn sẽ không được hiển thị công khai minh bạch. Các trường buộc phải được khắc ghi *

Bình luận

Tên *

Thư điện tử *

Trang web

Lưu tên của mình, gmail, cùng trang web trong trình chăm chú này đến lần phản hồi tiếp đến của tôi.


Chulặng mục

Ngành công nghệ thông tin (45)Ngôn ngữ (23)Thuật tân oán (307)Cấu trúc tài liệu (26)Đồ thị (51)Webmaster (12)

Chuyên mục: Tổng hợp