Để 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.
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ảngTổ 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
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
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
cout Adj
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=HeadCode 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
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
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
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
for i:=1 to m do
begin
dec(head
end;
end;
// Lúc nhập dữ liệuHead
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.
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
struct Node int info; Node* pNext; Node() pNext=NULL; Node* List
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.
Xem thêm: 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ị”
17 Tháng Ba, 2018 at 21:56
Hay lắm ạ,dễ hiểu rộng sách giáo khoa siêng tin nhiều luôn luôn ạ !!! Cả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ớ.