2.DUYỆT ĐỒ THỊ THEO CHIỀU SÂU - Fish IT

Các bạn có thể tham khảo bài viết này để đăng ký hosting miễn phí nhé!

Video của thầy Thức

Một số bài mẫu trên hệ thống else về duyệt theo chiều sâu:

Bài 1:

Cho một đồ thị vô hướng đơn. Hãy in ra thứ tự của các đỉnh khi duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh 1. Nếu đồ thị không liên thông, sau khi duyệt xong lần 1, tìm đỉnh có chỉ số nhỏ nhất chưa duyệt mà duyệt nó, và cứ tiếp tục như thế cho đến khi tất cả các đỉnh đều được duyệt. Quy ước: Các đỉnh kề của 1 đỉnh được liệt kê theo thứ tự tăng dần Đầu vào (Input): Dữ liệu đầu vào được nhập từ bàn phím với định dạng: – Dòng đầu tiên chứa 2 số nguyên n và m, tương ứng là số đỉnh và số cung. – m dòng tiếp theo mỗi dòng chứa 2 số nguyên u v nói rằng mô tả cung (u, v). Đầu ra (Output): In ra các đỉnh theo thứ tự duyệt, mỗi đỉnh trên 1 dòng.

Code:

include define MAX_ELEMENTS 100 typedef struct { int A[100][500]; int n; }dothi; void khoitao(dothi *G,int n){ int i,j; G->n = n; for(i=1;i<=n; i++) for(j=1;j<=n;j++) G->A[i][j]=0; } void themcung(dothi *G,int x,int y){ G->A[x][y] =1; G->A[y][x] =1; } int kiemtradinh(dothi G,int x, int y){ return G->A[x][y] != 0; } int tinhbac(dothi G, int x){ int y, bac = 0; for (y = 1; y <= G->n; y++ ) if(G->A[x][y] > 0 ) bac++; return bac; } // Danh sach List typedef struct { int data[MAX_ELEMENTS]; int size; // danh sach toi da } List; /* Tao danh sach rong / void make_null(List L) { L->size = 0; } /* Them mot phan tu vao cuoi danh sach / void push_back(List L, int x) { L->data[L->size] = x; L->size++; } /* Lay phan tu tai vi tri i, phan tu bat dau o vi tri 1 / int element_at(List L, int i) { return L->data[i-1]; } /* Tra ve so phan tu cua danh sach / int count_list(List L) { return L->size; } List cacdinhke(dothi* G, int x){ int y; List L; make_null(&L); for (y=1;y<= G->n; y++){ if (kiemtradinh(G,x,y)) push_back(&L,y); } return L; } typedef struct { int data[MAX_ELEMENTS]; int front, rear; } Queue; void khoitaoHD(Queue* Q) { Q->front = 0; Q->rear = -1; } void push(Queue* Q, int x) { // day noi dung vao HD Q->rear++; Q->data[Q->rear] = x; } int top(Queue* Q) { // Lay ra noi dung HD return Q->data[Q->front]; } void pop(Queue* Q) { // Xoa vi tri Q->front++; } int empty(Queue* Q) { // kiem tra rong return Q->front > Q->rear; } //Duyet Theo chieu Rong void duyetrong(dothi* G) { Queue H; int mark[100]; khoitaoHD(&H); // khoi tao mark ( chua xet ) int i,j; for (j=1;j <= G->n; j++) // duyet tu dinh 1 -> n mark[j] = 0; // dua 1 vao HD //printf("1 \n"); for(i=1;i<=G->n;i++){ if(mark[i]==1) // ki?m tra tính liên thông continue; push(&H,i); mark[i]=1; while (!empty(&H)){ int x = top(&H); pop(&H); printf("%d \n",x); // kiem tra cac dinh ke List L = cacdinhke(G,x); for (j=1;j <= L.size; j++){ int y = element_at(&L,j); if (mark[y] == 0) { mark[y] = 1; push(&H,y); } } } } } int main(){ dothi G; int n, m, u, v, e; scanf("%d%d", &n, &m); khoitao(&G, n); for (e = 0; e < m; e++) { scanf("%d%d", &u, &v); themcung(&G, u, v); } duyetrong(&G); }

Bài 2:

Cho một đồ thị vô hướng đơn. Hãy in ra thứ tự của các đỉnh khi duyệt đồ thị theo chiều sâu (sử dụng ĐỆ QUY) bắt đầu từ đỉnh 1. Nếu đồ thị không liên thông, sau khi duyệt xong lần 1, tìm đỉnh có chỉ số nhỏ nhất chưa duyệt mà duyệt nó, và cứ tiếp tục như thế cho đến khi tất cả các đỉnh đều được duyệt. Quy ước: Các đỉnh kề của 1 đỉnh được liệt kê theo thứ tự tăng dần. Đầu vào (Input): Dữ liệu đầu vào được nhập từ bàn phím với định dạng: – Dòng đầu tiên chứa 2 số nguyên n và m, tương ứng là số đỉnh và số cung. – m dòng tiếp theo mỗi dòng chứa 2 số nguyên u v nói rằng mô tả cung (u, v). Đầu ra (Output): In ra các đỉnh theo thứ tự duyệt, mỗi đỉnh trên 1 dòng. Xem thêm các ví dụ bên dưới.

Code:

include define MAX_ELEMENTS 100 define MAX_VERTICES 100 typedef int Element_Type; typedef struct { Element_Type data[MAX_ELEMENTS]; int size; }List; void make_null_list(List *L){ L->size=0; } void push_back(List *L, Element_Type x){ L->data[L->size]=x; L->size++; } Element_Type element_at(List *L, int i){ return L->data[i-1]; } int count_list(List *L){ return L->size; } typedef struct { int n; List adj[MAX_VERTICES]; }Graph; void init_graph(Graph *G, int n){ G->n=n; int i; for(i=1; i<=n; i++) make_null_list(&G->adj[i]); } void add_edge(Graph *G, int x, int y){ push_back(&G->adj[x], y); push_back(&G->adj[y], x); } int adjacent(Graph *G, int x, int y){ int i; for(i=1; i<=G->adj[x].size; i++) if(element_at(&G->adj[x],i) == y) return 1; return 0; } int degree(Graph *G, int x){ return G->adj[x].size; } List neighbors(Graph *G, int x){ List L; make_null_list(&L); int y; for(y=1 ;y<=G->n; y++){ if(adjacent(G,x,y) ) push_back(&L, y); } return L; } int mark[MAX_VERTICES]; void traversal(Graph *G, int x){ if(mark[x] == 1) return; mark[x]=1; printf("%d\n",x); List L=neighbors(G,x); int i; for(i=1; i<=L.size; i++){ int y=element_at(&L,i); traversal(G,y); } } void depth_first_search(Graph *G, int x){ int i; for(i=1; i<=G->n; i++) //mark[i]=0; traversal(G,x); } int main(){ // freopen("dt.txt", "r", stdin); Graph G; int n, m, u, v, w, e; scanf("%d%d", &n, &m); init_graph(&G, n); for (e = 0; e < m; e++) { scanf("%d%d", &u, &v); add_edge(&G, u, v); } depth_first_search(&G, 1); for (w = 1; w <= n; w++) if (mark[w] == 0) depth_first_search(&G,w); }

Bài 3:

Cho một đồ thị vô hướng đơn. Hãy in ra thứ tự của các đỉnh khi duyệt đồ thị theo chiều sâu (sử dụng NGĂN XẾP) bắt đầu từ đỉnh 1. Nếu đồ thị không liên thông, sau khi duyệt xong lần 1, tìm đỉnh có chỉ số nhỏ nhất chưa duyệt mà duyệt nó, và cứ tiếp tục như thế cho đến khi tất cả các đỉnh đều được duyệt. Quy ước: Các đỉnh kề của 1 đỉnh được liệt kê theo thứ tự tăng dần. Đầu vào (Input): Dữ liệu đầu vào được nhập từ bàn phím với định dạng: – Dòng đầu tiên chứa 2 số nguyên n và m, tương ứng là số đỉnh và số cung. – m dòng tiếp theo mỗi dòng chứa 2 số nguyên u v nói rằng mô tả cung (u, v). Đầu ra (Output): In ra các đỉnh theo thứ tự duyệt, mỗi đỉnh trên 1 dòng. Xem thêm các ví dụ bên dưới.

Code:

include define MAX_VERTEXES 100 define MAX_ELEMENTS 100 define MAX_NODES 100 /* Khai bao Stack*/ typedef struct { int data[MAX_ELEMENTS]; int size; } Stack; void make_null_stack(Stack* S) { S->size = 0; } void push(Stack* S, int x) { S->data[S->size] = x; S->size++; } int top(Stack* S) { return S->data[S->size - 1]; } void pop(Stack* S) { S->size--; } int empty(Stack* S) { return S->size == 0; } // khi bao do thi typedef struct { int n, m; int A[MAX_VERTEXES][MAX_VERTEXES]; }Graph; // khoi tao do thi void init_graph (Graph *G, int n) { int i, j; G->n = n; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) G->A[i][j] = 0; } // them cung void add_edge (Graph *G, int x, int y) { G->A[x][y] = 1; G->A[y][x] = 1; } // kiem tra co ke int adjacent (Graph *G, int x, int y) { return G->A[x][y] != 0; } // khai bao danh sach typedef int ElementType; typedef struct { ElementType data [MAX_ELEMENTS]; int size; }List; // tao rong void make_null(List * L) { L->size = 0; } // them phan tu void push_back(List *L, ElementType x) { L->data[L->size] = x; L->size++; } // lay phan tu tai vi tri i, phan tu dat o bat ky dau ElementType element_at(List * L, int i) { return L->data[i-1]; } // tra ve so phan tu danh sach int count_list(List *L) { return L->size; } // tim cac dinh ke List neighbors (Graph * G, int x) { int y; List list; make_null(&list); for (y = 1; y <= G->n; y++) if (adjacent(G, x, y)){ push_back(&list, y); } return list; } int mark[MAX_VERTEXES]; /* Duyet do thi theo chieu sau / void depth_first_search(Graph G, int x) { Stack frontier; //int mark[MAX_VERTEXES]; make_null_stack(&frontier); /* Khoi tao mark, chua dinh nào duoc xét */ int j ; for (j = 1; j <= G->n; j++) //mark[j] = 0; /* Ðua 1 vào frontier */ push(&frontier, x); /* Vong lap chinh dung de duyet */ while (!empty(&frontier)) { /* Lay phan tu dau tiên trong frontier ra / int x = top(&frontier); pop(&frontier); if (mark[x] != 0) continue; printf("%d\n", x); mark[x] = 1; //Ðánh d?u nó dã duy?t / L?y các d?nh k? c?a nó / List list = neighbors(G, x); / Xét các d?nh k? c?a nó */ for (j = 1; j <= list.size; j++) { int y = element_at(&list, j); push(&frontier, y); } } } int main () { Graph G; int n, m, u, v, w, e; scanf("%d%d", &n, &m); init_graph(&G, n); for (e = 0; e < m; e++) { scanf("%d%d", &u, &v); add_edge(&G, u, v); //depth_first_search(&G); } depth_first_search(&G, 1); for (w = 1; w <= n; w++) if (mark[w] == 0){ depth_first_search(&G, w); } return 0; }

Share this:

• Click to share on Twitter (Opens in new window)
• Click to share on Facebook (Opens in new window)
• Click to share on LinkedIn (Opens in new window)

Like Loading...

Related