Biểu Diễn Đồ Thị Bằng Danh Sách Kề Và Danh Sách Kề, Biểu Diễn Đồ Thị Bằng Ma Trận Kề Và Danh Sách Kề

Để khắc chế lỗi của danh sách cạnh về việc đào bới tìm kiếm đỉnh kề, nhưng mà vẫn đảm bảo an toàn tổ chức dữ liệu tối ưu độc nhất vô nhị giao hàng chuẩn y search trong đồ vật thị cơ mà Danh sách kề được ra đời.

You watching: 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 dữ liệu hình dạng danh sách kề là các bạn sẽ lưu giữ các đỉnh kề của một đỉnh vào những đoạn vào mảng nhằm tàng trữ. Nếu bao gồm N đỉnh thì sẽ sở hữu N đoạn để lưu. Và họ nên lưu lại chỉ số nhằm quản ngại lí phạm vi những đỉnh kề của đỉnh mà lại đoạn đó cai quản lí.

Các chúng ta xem hình hình họa bên dưới nhằm nắm rõ hơn ý tưởng này.

hotline Head là chỉ số chấm dứt của đoạn quản lí đỉnh kề của i-1. Hay Head+1 là chỉ số bắt đầu của đoạn quản lí lí đỉnh kề của i.

Bởi vậy, chỉ số của đoạn cất các đỉnh kề của i là tự Head+1 mang đến Head

a.2 Tổ chức bằng list liên kết
Việc tổ chức triển khai bằng danh sách link, bọn họ sẽ có được một mảng n ô, Mỗi ô cất một pointer Node, pointer này có 2 báo cáo là chỉ số đỉnh kề và pointer next tiếp theo. Tđam mê khảo hình bên dưới (mục thiết lập bởi danh sách liên kết) để nắm rõ hơn.
b. lấy ví dụ như minh họa
Cho thứ thị đối chọi có hướng, có N đỉnh M canh. Dữ liệu những 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ư minch họa tổ chức danh sách kề bởi mảng một chiều

trước hết các bạn chỉ cần gọi những đỉnh kề của đỉnh u là Adj cùng với v=Head+1……Head
Như hình minc họa bên trên ngơi nghỉ đỉnh số 3, bản thân có đánh màu xanh ví dụ. Dựa vào bài toán xác minh đỉnh kề bởi Head<> thì bản thân đạt được các đỉnh kề của 3 là Adj< Head<3>+1 đến Head<3+1>>
Nếu viết bằng c++ thì bản thân đem các đỉnh kề của đỉnh u bằng phương pháp sau:

// Minh họa in những đỉnh kề của uvoid indinhke(int u) for (int v=Head+1; v
1
2
3
4
5
6
// Minh họa in các đỉ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 tài liệu với thời gian là O(m) với m là số cạnh của đồ thị.
2. Cài đặt list kề
a. Tổ chức bởi mảng bằng pascal / C++
Như hồ hết bài viết trước về tổ chức dữ liệu cho triết lý thứ thị, bản thân đã giải đáp chúng ta gọi dữ liệu. Dòng đầu đã bao gồm 2 số N, và m.
Mô tả từng bước:
Ban đầu Head=0Đọc từng cạnh (u,v) và tăng Head=Head+1.Cộng dồn Head=Head+Head. i=2->n+1;Lưu ý thêm Head luôn luôn m nếu sẽ là thiết bị thị được bố trí theo hướng.Duyệt qua những cạnh, Adj> = v; Head=Head-1;
Code tổ chức triển khai tài liệu đồ gia dụng thị bởi list kề vào c++

#define NMAX 100#define MMAX 1000//Knhì báo tài 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 thiết bị thị bằng 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;
// knhị 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 khổng lồ m do
begin
read(f,u,v);
inc(head>);
end;
for i:=2 khổng lồ n+1 do
head:=head+head;
for i:=1 to 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 lúc cùng dồn head, và tất nhiên MMAX yêu cầu tăng gấp hai.

See more: Bí Mật Về Cái Chết Của Đại Tướng Nguyễn Chí Thanh, Về Binh Thư Của Tướng Nguyễn Chí Thanh

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 có nhu cầu giữ thêm trọng số của cạnh, có thể chế tạo thêm một mảng có sứ mệnh y hệt như adj, nhỏng từ bây giờ chúng ta đang lưu lại trọng số của bọn chúng.
b. Tổ chức vụ sách liên kết

Tổ chức lưu trữ vật thị bởi list liên kết

struct Node int info; Node* pNext; Node() pNext=NULL; Node* List;int u,v,m,n;// Nhập số đỉnh và 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 và 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 links 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
// Minc 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 cùng hạn chế của danh sách kề
– Ưu điểm của danh sách kề là chi phí coi sóc và lưu trữ khá về tối ưu. Đặc biệt là danh sách kề vào mảng.
– Cài đặt bài toán thù bằng list kề tương đối dài hơn nữa đối với ma trận kề với danh sách cạnh.
– Đối cùng với từng bài xích toán thù rõ ràng, tùy thuộc vào dữ liệu bài toán cho, chúng ta hãy lựa chọn lựa cách tổ chức tài liệu tương xứng độc nhất, không nhất thiết thời điểm nào cũng tổ chức triển khai danh sách kề.
4. Bài tập ứng dụng
Bài tập về list kề nhìn toàn diện những chúng ta cũng có thể rước các bài bác tập bản thân nội dung nghỉ ngơi bài bác về DFS, BFS về thực chất nó là đồng nhất.
Trong khi rất có thể xem thêm danh sách kề lúc kết phù hợp với Pryên ổn heap: https://ehefs.org/cay-khung-nho-nhat-qbmst-spoj-kruskal-prim-heap/

Đồ thị Tổ chức dữ liệu vào lý thuyết trang bị thị. permalink.

See more: Nsưt Minh Phụng - Nghệ Sĩ Cải Lương Minh Phụng

Post navigation

Viết mã nguồn tự động hóa thông tin điểm UIT (Phần 2)
Cách đọc ghi file vào 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 ạ,dễ hiểu rộng sách giáo khoa siêng tin nhiều luôn luôn ạ !!! Cảm ơn ad !

Trả lời
Trả lời Hủy
E-Mail của bạn sẽ ko được hiển thị công khai. Các ngôi trường cần được khắc ghi *
Bình luận
Tên *
E-Mail *
Trang website
Lưu tên của mình, tin nhắn, cùng website vào trình để mắt tới này đến lần phản hồi kế tiếp của tớ.

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

Chuyên mục: Blog