[Chuyên ngành] Hướng dẫn em bài tập cấu trúc dữ liệu và giải thuật ni cấy !!!

[nguyen_mai193]

viết chương trình minh họa mô tả giải thuật và các giải thích khác
1. đường đi ngắn nhất trong đồ thị không trọng số được cho bởi ma trận kề. Chương trình minh họa

[HongPhong]

Cái này sử dụng thuật toán gì em, tìm kiếm theo chiều rộng hay sâu... có tới mấy thuật toán lận đó.

[nguyen_mai193]

nếu tim kiém thi bọn e chỉ được học tìm kiếm tuyến tính và tim kiếm nhị phân .thầy ko giới hạn sử dụng thuật toán .mà em cụng chưa biết sử dụng cây chi
em vẫn chưa tím được mối liên hệ giữa ma trận kề và đồ thị ko trọng số .
[ Tự động gộp bài ]
bây giờ làm răng mà viết chương trình để chạy được!!!!anh hay viết trên turbo c hay vsc++

[daihoccanhsat_tr]

ai đó bít thì giúp bạn ni cấy tề!
cứ im im rứa là ko đc

[HongPhong]

Nếu em đọc tài liệu thì em sẽ hiểu ma trận kề biểu diễn như thế nào thôi.
Chẳng hạn có mt A(n*n) thì A[i][j]=1 khi giữa v[i] và v[j] có đường nối với nhau ( Trong đó v[] là ma trận đỉnh ) và A[i][j]=0 khi không có đường nối giữa chúng

Để tìm đường đi ngắn nhất với đồ thị vô hướng thì bạn sử dụng thuật toán Dijkstra

Nếu bạn đã rõ thuật toán thì dùng ngôn ngữ gì cũng được, nếu biết C# thì dùng C# sẽ nhanh, tiện hơn nhiều so với BORLANDC
http://spktit.net/showthread.php?t=828

Đây là toàn bộ đồ án lớp mình làm năm nhất (viết bằng BORLANDC )


Chuyển đổi giữa các cách biểu diễn đồ thị
http://www.mediafire.com/?smn1tlgwj2h

Chương trình biểu diễn các đồ thị đơn giản:
http://www.mediafire.com/?euyjmmgd9w1

Chu trình Hamilton:
http://www.mediafire.com/?mmijjmm2vwm

Duyệt đồ thị theo chiều rộng
http://www.mediafire.com/?dojlbiwgjl1

Mô phỏng duyệt đồ thị theo DFS
http://www.mediafire.com/?ejhjhono4ey

Đồ thị liên thông:
http://www.mediafire.com/?n1f70iuy4kj
Mô phỏng chu trình Euler
http://www.mediafire.com/?adn1omzv94n

Xử lý ma trận kề từ file
http://www.mediafire.com/?jfnm4311jwn

Mô phỏng thuật toán Prim
http://www.mediafire.com/?htnjxxkbnot

DIJKSTRA
http://www.mediafire.com/?9z3nnjnfxzs

hoặc:
http://www.mediafire.com/?qysh9mzlgsz (cái này bro hơn )

Đồ thị có trọng số :
http://www.mediafire.com/?fmcokdlsml4

[nguyen_mai193]

.mấy cái này phức tạp hơn bọn em học .bài tập của em lại phải viết chương trình ...... nói chung là giờ em ko biết viết như răng . khi bắt đầu viết chương trình thì mô tả ma trận trước rồi tìm đường đi ngắn nhất ạ . anh có chương trình mô viết ma trận mà đơn giản hơn một tì đc ko.ma trận thì em hiều nhưng ko biết liên kết giữa ma trận và cách tìm đường ngắn nhất

[HongPhong]

Ở trên đó em, cái đồ án DIJKSTRA đó. Còn việc liên kết giữa ma trận và cách tìm đường ngắn nhất thì em phải đọc thuật toán mới hiểu được.
Còn ma trận, như anh đã nói ở trên, là một cách để "số hóa" đồ thị thôi. Nó cho em biết thông tin như :đồ thị có bao nhiêu đỉnh (chính là cấp của ma trận) mà đỉnh nào được nối với nhau (đã nói ở trên).
Trong quá trình em duyệt ma trận thì em xét giá trị của các phần tử để xem đỉnh đang duyệt tới có kề với đỉnh đang xét không.
Nói vậy không biết em có hiểu được không (không có khiếu sư phạm )

[nguyen_mai193]

em thấy mặt cười mà nỏ cười được.em cụng muốn hiểu lắm chứ
bài của em cụng được thầy gọi là đồ án hix nhưng nỏ ai hướng dẫn .nhưng anh ơi em vẫn chưa biết làm răng .làm răng để có chương trình để đến hôm chạy cho thày coi.
[ Tự động gộp bài ]
em hiểu cây ni hơn 2. Tìm đường đi ngắn nhất bằng thuật toán Dijkstra

Thuật toán Dijkstra chỉ áp dụng cho đồ thị có trọng số không âm. Tu tưởng thuật toán cũng dựa trên ý tưởng so sánh d[v] > d[u]+A[u][v] nhưng tối ưu hơn Ford-Bellmann nhờ giảm số vòng lặp lòng nhau trong quá trình xét các đỉnh.

void Dijkstra(int *d, int s)

{

int T[MaxV];

for (int v=0; v<V; v++)

{

d[v] = A[s][v];

Truoc[v] = s;

}

d[s] = 0; T[s] = 1;

while ( 1 )

{

int u = -1;

for (int z=0; z<V; z++)

if (T[z] != 1 && (u==-1 || d[u] > d[z]))

u = z;

if (u == -1)

break;

T[u] = 1;

for (int v=0; v<V; v++)

if (T[v]!=1 && d[v]>d[u]+A[u][v])

{

d[v] = d[u]+A[u][v];

Truoc[v] = u;

}

}

}

3. Tìm đường đi từ đỉnh s đến đỉnh t.

{ Tìm đường đi dựa vào thông tin được lưu trong mảng Truoc[MaxV]

int InDuongDi_sdTruoc(int Truoc[ ], int s, int t)

{

int STACK[MaxV], topS = 0;

STACK[topS++] = t;

while (Truoc[ STACK[topS-1] ] != s)

STACK[topS++] = Truoc[ STACK[topS-1] ];

STACK[topS++] = s;



cout<<"\nDuong di tu "<<s<<" den "<<t<<" la: ";

for ( int i=topS-1; i>=0; i-- )

cout<<STACK[ i ] +1<<" ";

}

{ Tìm đường đi dựa vào thông tin trọng số đường đi của các đỉnh được lưu trong mảng d[MaxV], không sử dụng thông tin của mảng trước.

Đặc điểm: Nếu đỉnh u là đỉnh trước của v trên đường đi s đến v thì

d[v] == d[u]+A[u][v]

Dựa vào đặc điểm này để tìm ngược đường đi từ s đến t.

int InDuongDi_ksdTruoc(int d[ ], int s, int t)

{

int STACK[MaxV], topS = 0;

STACK[topS++] = t;

int v = t;

while ( v != s )

{

int v = STACK[topS-1];

for (int u = 0; u<V; u++)

if (d[v] == d[u]+A[u][v])

break;

if ( u == V)

break;

STACK[topS++] = u;

v = u;

}



cout<<"\nDuong di tu "<<s<<" den "<<t<<" la: ";

for ( int i=topS-1; i>=0; i-- )

cout<<STACK[ i ] +1<<" ";

}



4. Cài đặt hàm main ( )

Để hoàn thiện chương trình, phải sử dụng lại những hàm thao tác trên đồ thị đã được xây dựng trước: DocMTKe(…..), XuatMTKe(…..). Hãy copy chúng vào source code của chương trình.

Định nghĩa hàm main ( ) để tìm đường đi trên đồ thị từ đỉnh s đến đỉnh t của đồ thị.

Source code main ( )

int main(int argc, char* argv[])

{

DocMTKe("D:\\GRAPH1.TXT", A, V);

XuatMTKe(A, V);



int s, t;

printf("Nhap dinh dau, dinh cuoi cua duong di: "); scanf("%d %d", &s, &t);



int d[MaxV];

memset( d, 0, sizeof(d) );



// Ford_Bellman( d, s ); // Chon 1 trong 2, thuat toan nao cung duoc !

Dijkstra( d, s ) ;



// InDuongDi_sdTruoc(Truoc, s, t); // Chon 1 trong 2, ham nao cung duoc!

InDuongDi_ksdTruoc(d, s, t);



getch();

return 0;

}