# GÓC SÁNG TẠO > Khu vực lập trình > C/C++ >  duyệt đồ thị theo chiều sâu dùng danh sách kề để mô tả đồ tihị

## chicilonmedia

các pác ơi giúp em với .Em sắp thi CTDL&GT mà vẫn chưa làm được, bài này khó quá
ĐỀ BÀI
(VIẾT BẰNG NGÔN NGỮ C) 
*Đồ thị G vô hướng, không trọng số,có n đỉnh n<255, được cho bởi danh sách kề DK[1..n] các đỉnh được đánh số từ 1 đến n.Với mỗi i=1,2...,DK là một danh sách các đỉnh kề của i.DK[0] chỉ số đỉnh kề của i.Số hiệu các đỉnh kề của i được lưu trữ liên tiếp tù DK[1] đến DK[DK[0] 
a) Viết thủ tục duyệt đồ thị dựa trên phép tìm kiếm ưu tiên chiều sâu.Khi duyệt đến đỉnh nào thì đưa số hiệu đỉnh đó vào mảng TD[1..n] 
b)Viết thủ thuc tìm đường đi ngắn nhất nối 2 đỉnh u và v của đồ thị*_ 
không phải do em lười mà thú thực em chỉ hiểu thuật toán của nó thôi chứ còn viết chương trình thì em bó tay.Các pác giúp em với nhé ,em cám ơn tất cả các pác_

----------


## bedaukute

không có bác nào giúp em à, gửi từ năm ngoái rồi

----------


## benhvienaau

Hì! không biết có phải cái bạn cần ko nữa? Mình làm chương trình bằng C đây là thủ tục tìm đường đi ngắn nhất giữa hai đỉnh áp dụng thuật toán floyd. Có chỗ nào sai thì nói nhé! Mình làm chương trình thấy chạy đúng. Thân!
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <dos.h>
#define MAX 100
#define TRUE 1
#define FALSE 0
int A[50][50],D[50][50],S[50][50];
int n,u,v,k;
FILE *fp;
void Init(int u, int v) 
{
int i,j,k;
fp=fopen("DOTHI.IN","r");
if(fp==NULL)
{
printf("
 Khong co tap tin input");
getch();
return;
}
for(i=1;i<=n;i++)
for( j=1;j<=n;j++)
A_[j]=0;
fscanf(fp,"%d",&n);
printf("
 So dinh cua do thi %d",n);
printf("
 Di tu dinh: %d --> %d",u,v);
printf("
 Ma tran co trong so:
");
for (i=1;i<=n;i++)
{
printf("\t
");
for (j=1;j<=n;j++)
{
fscanf(fp,"%d",&A[j]);
printf("%3d",A[j]);
if (i!=j && A[j]==0)
A[j]=MAX;
}
}
printf("
");
fclose(fp);
//getch();
}
void Floy(void)
{
int i,j,k,found;
for (i=1;i<=n;i++)
{
for( j=1;j<=n;j++)
{
D[j]=A[j];
if (D[j]==MAX)
S[j]=0;
else S[j]=j;
}
}
for (k=1;k<=n;k++)
{
for( i=1;i<=n;i++)
{
for( j=1;j<=n;j++)
{
if (D[k]!=MAX && D[j] > (D[k]+D[k][j]))
{
D[j]=D[k]+D[k][j];
S[j]=S[k];
}
}
}
}
}
void Result(void)
{
if (D[v]>=MAX)
{
printf("
 Khong co duong di");
getch();
return;
}
else
{
printf("
 Do dai duong di ngan nhat:%d",D[v]);
printf("
 Duong di ngan nhat la: %3d",u);
while(u!=v)
{
printf(" -->%3d",S[v]);
u=S[v];
}
}
}
void main(void)
{printf("
 Tim duong di tu dinh nao toi dinh nao? "); scanf("%d%d",&u,&v);
Init(u,v);}
---------------------------------Bài viết đã được trộn ---------------------------------
quên hàm void floy(void) chính là hàm bạn cần đo!_

----------

