Biểu Diễn đồ Thị.docx

Biểu diễn đồ thị Xây dựng các hàm phục vụ cho việc tạo ma trận kề của đồ thị cần biễu diễn, gồm có: Nhập ma trận kề: Cho phép nhập thông tin về đồ thị bằng tay gồm số đỉnh N, các giá trị Ai,j của ma trận kề Đọc ma trận kề từ file: Cho phép nhập thông tin về đồ thị từ file chứa các giá trị của ma trận kề gồm số đỉnh N, các giá trị Ai,j. Xuất ma trận kề: In thông tin về đồ thị ở dạng ma trận kề gồm các giá trị Ai,j .

Source code : #define MaxV 20 //Define su dung cho so dinh cuc dai cua do thi

int A[MaxV][MaxV]; int V = 0;

//Ma tran ke //So dinh cua do thi

int ChuaXet[MaxV];

//Thu tuc nhap matran ke bang ban phim. void NhapMTKe(int A[][MaxV], int &V) { printf("Nhap V:"); scanf("%d", &V); for (int i=0; i
{ printf("A[%d,%d] = ", i+1, j+1); scanf("%d", &(A[i][j])); } } }

// Xuat ket qua ma tran ke cua do thi ra man hinh. void XuatMTKe(int A[][MaxV], int V) { printf("\nMa tran ke:\n"); for (int i=0; i
//Doc du lieu ma tran ke cua do thi da duoc tao thanh file text luu san tren dia. int DocMTKe(char *fileName, int A[][MaxV], int &V) { FILE *f = fopen(fileName, "rt");

if (f == NULL) { printf("Doc file loi !!!"); return 0; } fscanf(f, "%d", &V); for (int i=0; i
Duyệt theo chiều sâu có sử dụng đệ quy

thế

Duyệt theo chiều sâu không sử dụng đệ quy, sử dụng STACK thay

-

Duyệt theo chiều rộng sử dụng cấu trúc QUEUE

Source code các hàm //Thu tuc duyet DFS, duyet theo chieu sau su dung ky thuat de quy. void DFS(int v)

{ ChuaXet[v] = 1; for ( int u=0; u
//The hien u la dinh ke cua v

if ( ChuaXet[u]==0 ) DFS( u );

//Dinh u chua duoc duyet qua==>

Duyet u }

//Thu tuc duyet DFS, duyet theo chieu sau su dung STACK de khu de quy. void DFS0DeQuy(int v) { int STACK[MaxV], topS = 0; rong

STACK[topS++] = v;

//Khoi tao STACK voi mot STACT

//Dua dinh v vao dinh STACK

ChuaXet[v] = 0;

while(topS > 0)

//Xem nhu da duyet dinh v

//Lap trong khi STACK khac rong

{ v = STACK[--topS];

//Lay mot dinh v tu dinh cua STACK ra

for (int u=V-1; u>=0; u--) if (A[v][u] != 0)

//Xet dinh u ke voi dinh v

if ( ChuaXet[u]==0 ) { STACK[topS++] = u; //Dua u vao dinh STACK ChuaXet[u] = 1;

//Xem dinh nay la da

xet. } }

}

//Thu tuc duyet DFS, duyet theo chieu rong su dung QUEUE de chay khong de quy. void BFS0DeQuy(int v) { int QUEUE[MaxV], topQ=0, bottomQ=0; rong

QUEUE[topQ++] = v;

//Khoi dau voi mot QUEUE

//Dua dinh v vao QUEUE, xem no nhu la da

xet ChuaXet[v] = 1;

while ( bottomQ < topQ )

//Lap trong khi QUEUE khac rong

{ v = QUEUE[bottomQ++];

//Lay dinh v tu day cua QUEUE

for (int u=0; u
//The hien u ke voi

dinh v if ( ChuaXet[u]==0 ) { QUEUE[topQ++] = u;

// Dua u vao dinh

cua QUEUE ChuaXet[u] = 1; } }

} Xây dựng hàm main( ) tiến hành gọi thuật toán duyệt đồ thị: + Gọi hàm đọc, xuất ma trận kề của đồ thị + Gọi hàm duyệt đồ thị với đỉnh bất kỳ, ví dụ như đỉnh đầu tiên ( đỉnh 0 ) + In ra các thành phần đã duyệt được trong đồ thị bơi Source code hàm main( ) int main(int argc, char* argv[]) { DocMTKe("D:\\Dothi_1.txt", A, V); XuatMTKe(A, V);

memset(ChuaXet, 0, sizeof(ChuaXet) ); DFS0DeQuy(v);

printf( "Các dinh da duyet: " ); if (ChuaXet[j] == tp) printf( "%d ", v+1 ); getch ( ); } Tạo mới file đồ thị D:\\Graph_1.TXT ở dạng ma trận kề, ví dụ: 13 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 3. Thành phần liên thông Để tìm số thành phần liên thông, thì mỗi lầ duyệt hãy gán cho mỗi thành phần liên thông một chỉ số vào giá trị của mảng ChuaXet, thay vì luôn ghi giá trị là 1. Các đỉnh của cùng thành phần liên thông sẽ có giá trị lưu trong ChuaXet giống nhau. Các bước tiến hành: 1. Truyền tham so nSoTPLT ve thành phần liên thông đang duyệt cho các hàm duyệt, cụ thể là: void DFS0DeQuy(int v, int nSoTPLT)

void BFS0DeQuy(int v, int nSoTPLT) void DFS0DeQuy(int v, int nSoTPLT) 2. Thay thế chỉ số index cho các thành phần liên thông trong các hàm duyệt: Thay thế các dòng gán ChuaXeti = 0 thành ChuaXet[i ] = nSoTPLT. Ví dụ: ChuaXet[v] = nSoTPLT;

//Xem dinh nay la da xet.

Chỉnh sửa lại hàm main ( ) để in ra tất cả các đỉnh của từng thành phần liên thông int main(int argc, char* argv[]) { int nSoTPLT = 0;

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

for (int v=0; v
cout<
1. Tìm đường đi + Khai báo mảng lưu vết : int DinhTruoc[MaxV]; + Bổ sung để hàm duyệt DFS lưu vết tìm đường đi: //Thu tuc duyet DFS, duyet theo chieu sau su dung ky thuat de quy. void DFS(int v) { ChuaXet[v] = nSoTPLT; for ( int u=0; u
//The hien u la dinh ke cua v

if ( ChuaXet[u]==0 ) { DinhTruoc[u] = v; DFS( u );

//Dinh u chua duoc duyet qua==>

Duyet u } } + Hoàn thiện hàm main ( ) để tìm đường đi từ s đến t. int main(int argc, char* argv[])

{ int nSoTPLT = 0;

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

int s, t; cout<<"Nhap dinh bat dau, dinh ket thuc:"; cin>>s>>t; s--; t--; DFS(s);

int DuongDi[MaxV], k = 0; DuongDi[k++] = t; while ( DinhTruoc[ DuongDi[k-1] ] != s) DuongDi[k++] = DinhTruoc[ DuongDi[k-1] ]; DuongDi[k++] = s;

cout<<"\nDuong di tu "<<s<<" den "<=0; i-- ) cout<
/* Do mang tinh tu G[0][0] nen can giam vi tri di 1 don vi de tinh toan cho phu hop*/ a--; b--; printf("start dijkstra\n"); int* Len = (int *) malloc(n * sizeof(int)); int* S = (int *) malloc(n * sizeof(int)); int sum = 0;

// gia tri vo cung

// tinh gia tri vo cung (sum) for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { sum += G[i][j]; } } // dat vo cung cho tat ca cap canh khong noi voi nhau for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j && G[i][j] == 0) G[i][j] = sum; } } for (int i Len[i] la vo cung S[i] = P[i] = a }

= 0; i < n; i++) { = sum; // khoi tao do dai tu a toi moi dinh 0; a;

Len[a] = 0;

// danh sach cac diem da xet // dat diem bat dau cua moi diem la

// dat do dai tu a -> a la 0

int i; // tim duong di ngan nhat tu 1 dinh den moi dinh khac thi thay bang vong for: //for (int k = 0; k < n; k++) while (S[b] == 0) { // trong khi diem cuoi chua duoc xet

for (i = 0; i < n; i++) phai la vo cung if (!S[i] && Len[i] < sum) break;

// tim 1 vi tri ma khong

// i >=n tuc la duyet het cac dinh ma khong the tim thay dinh b -> thoat if (i >= n) { printf("done dijkstra\n"); return 0; } for (int j = 0; j < n; j++) { // tim diem co vi tri ma do dai la min if (!S[j] && Len[i] > Len[j]) i = j; } S[i] = 1;

// cho i vao danh sach

xet roi for (int j = 0; j < n; j++) { // tinh lai do dai cua cac diem chua xet if (!S[j] && Len[i] + G[i][j] < Len[j]) { Len[j] = Len[i] + G[i][j]; // thay doi len P[j] = i; // danh dau diem truoc no } } } printf("done dijkstra\n"); return Len[b]; } // truy vet duong di void back(int a, int b, int *P, int n, char *path) { //char *path = (char *) malloc((n * 10) * sizeof(char)); /* Do mang tinh tu G[0][0] nen can giam vi tri di 1 don vi de tinh toan cho phu hop*/ a--; b--; printf("start find path\n");

int i = b; int point[n]; int count = 0;

// danh sach cac dinh cua duong di

/* Do ta dang tinh toan tu dinh 0 nen muon hien thi tu dinh 1 thi can dung i + 1 de phu hop */ point[count++] = i + 1; while (i != a) { i = P[i]; point[count++] = i + 1; } strcpy(path, ""); char temp[10]; for (i = count - 1; i >= 0; i--) { sprintf(temp, "%d", point[i]); strcat(path, temp); if (i > 0) { sprintf(temp, " --> "); strcat(path, temp); } } printf("done find path\n"); } void outResult(int len, char* path) { FILE *fo = fopen(OUT, "w"); if (len > 0) { fprintf(fo, "\nLength of %c to %c is %d\n", path[0], path[strlen(path) - 1], len); } fprintf(fo, "path: %s\n", path); fclose(fo); } int main() { int **G, n, a, b, len; if (readData(&G, &n, &a, &b) == 0) { return 0;

} char *path = (char *) malloc((10 * n) * sizeof(char)); int P[n]; len = dijkstra(G, n, a, b, P); if (len > 0) { back(a, b, P, n, path); outResult(len, path); } else { char *path = (char *) malloc((n * 10) * sizeof(char)); sprintf(path, "khong co duong di tu %d den %d\n", a, b); outResult(len, path); } printf("done - open file output to see result\n"); return 0; }

#include #include #include #include #include

"stdafx.h"

using namespace std; #define MAX 50 #define VOCUC 10000 int n, Diem_Cuoi, Diem_dau; int c[MAX][MAX], Truoc[MAX], d[MAX]; void Doc_File_Ford_BellMan(){ ifstream filein( "fordbellman.txt", ios::in);

filein >> n; cout << " v."; for(int i=0; i> c[i][j]; if(c[i][j]==0){ c[i][j]= VOCUC; cout << " "; } else cout << setw(3) << c[i][j]; } cout << endl; } } void XuaKQ(){ int i,j; cout << "\nDuong di ngan nhat tu " << Diem_dau << " den " << Diem_Cuoi << " la:\n" << Diem_Cuoi; i = Truoc[Diem_Cuoi]; while(i!=Diem_dau){ cout << " " << i; i = Truoc[i]; } cout << " " << Diem_dau << "\nDo dai duong di: " << d[Diem_Cuoi]; getch(); } bool bellmanFord(){ for(int i = 0; i
for(int v = 0; v tmp){ d[v] = tmp; Truoc[v] = u; stop = false; } } } if(stop) return 1; } // kiêm tra chu trình âm for(int u = 0; u d[u]+c[u][v]){ return 0; } } } return 1; } int main(){ Doc_File_Ford_BellMan(); cout << "\nNhap diem dau va diem cuoi: "; cin >> Diem_dau >> Diem_Cuoi; if(bellmanFord()) XuaKQ(); else cout << "Do thi co chu trinh am!"; return 0; } Thuat toan : typedef struct node *ptr; struct node{int data,cost;ptr pnext;}; void chen(ptr &f,int v,int c) { ptr p=new node; p->data=v; p->cost=c; p->pnext=f; f=p; } ptr a[nm];

int c[nm][nm]; int f[nm][nm]; int trace[nm]; int n,m,t,s,k; int u,v; int res=0; dequeq; bool findpath() { q.clear(); memset(trace,0,sizeof(trace)); q.push_back(s); trace[s]=n+1; while (q.size()) { int u=q.front();q.pop_front(); ptr p=a[u]; while (p) { int v=p->data; if (!trace[v]&&c[u][v]>f[u][v]) { trace[v]=u; if (v==t)return true; q.push_back(v); } p=p->pnext; } } return false; } void incflow() { int u,v,delta=1000000000; v=t; while (v!=s) { u=trace[v]; delta=min(delta,c[u][v]-f[u][v]); v=u; } v=t; while (v!=s) { u=trace[v];

f[u][v]+=delta; f[v][u]-=delta; v=u; } } int main() { scanf ("%d%d%d%d",&n,&m,&s,&t); for (int i=1;i<=m;i++) { scanf ("%d%d%d",&u,&v,&k); c[u][v]=k; chen(a[u],v,k); } while (1) { if (!findpath())break; incflow(); } for (int v=1;v<=n;v++) if (f[s][v]>0)res+=f[s][v]; printf ("%d",res); getch(); return 0; }