




 !
Đề bài:
TÌM THÀNH PHẦN LIÊN THÔNG
"#$ % &
'( %)&)*+),))
! %

-

  !/ .
.
0
!/
) 123 
4 12!56
, 7869
: ;1
& 8
< .
= >;
* 12!5
? 1281

@A@A
)B"CDEDF$
)B)GH"IB

• Đồ thị vô hướng liên thông.
- Đồ thị vô hướng G = ( X,U) được gọi là liên thông nếu hai đỉnh phân biệt bất kỳ
của đồ thị liên thông với nhau.
• Đồ thị có hướng liên thông.
- Đồ thị có hướng G = ( X,U) được gọi là liên thông mạnh nếu hai đỉnh phân biệt
bất kỳ của đồ thị là liên thông.
- Đồ thị có hướng G = ( X,U) được gọi là liên thông yếu nếu đồ thị vô hướng nền là
liên thông.
• Thành phần liên thông.
Cho G
1
= (X
1
, U
1
) và G
2
= (X
2
, U
2
) là hai đồ thị liên thông không chung đỉnh. Khi
đó, ta nói đồ thị G= ( X, U), trong đó X= X
1
U X
2
, U = U
1
U U
2

dấu và chuyển sang Bước 3.
Z'A,: Thực hiện Bước 2 cho đến khi không còn thực hiện được nữa chuyển sang
Bước 4.
Z'A:: Nếu số số đỉnh đánh dấu bằng n kết thúc thuật toán, ngược lại quay về Bước 1.
Mô tả bài toán: Cho đồ thị vô hướng G=(V,E) hãy đếm số thành phần liên thông của đồ
thị G.
"TSGH"I^N"Z'EO_:S`E"a%
bcHHdE"LDMEH"NEOSGH"IefEOH"W\HHTCE+-%

• Z'A)%CEE"gEACAS`E"LJ]
• Z'A4%
• !'Dh)%OCEE"gES`E"h)^JicHHjS`E"A#SZVEOSDSkEACAS`E"AlE
LmDn"NEO
• QopH"qrHjS`E")A#SZVEOSDSkES`E"4EMEopOCEE"gE4LJ)

• mDS`E"4HQis$A#SZVEOSDHj4SkEACAS`E"AlELmDn"NEOtHjS`E"4HQSD
SZuASkES`E",EMEHQopOCEE"gEAPQS`E",LJE"gEAPQS`E"4

• mDS`E",HQis$A#SZVEOSDHj,SkEACAS`E"AlELmDn"NEOtHjS`E",HQSD
SZuASkES`E":EMEHQopOCEE"gEAPQS`E":LJE"gEAPQS`E",

• jS`E")HQSgSDSZuASkEACA
S`E"AlELmDHUTEOSGH"IEME
LJ)SGH"ILDMEH"NEO^vA"`A#
)A"WHUvE"wWrE"qHBkHH"xA
H"W\HHTCE
• "JE"("KELDMEH"NEO)%)4,
:
,BR("yAHm(APQH"W\HHTCE
Độ phức tạp của thuật toán :

if(A[u][v] && chuaxet[v])
{
DFS_Dequi(v);
}
}
}
}

void nhapbp()
{
printf ("nhap ma tran ke");
printf ("\n nhap so dinh:");
scanf ("%d",&n);
for (int i=1;i<=n;i++){
printf("\n");
chuaxet[i]=TRUE;
for (int j=1; j<=n; j++)
{
printf("nhap phan tu %d%d:\n",i,j);
scanf ("%d",&A[i][j]);
}
}
printf("\n ");
for(int i=1; i<=n; i++){
printf("\n");
for(int j=1; j<=n; j++){
printf("%3d",A[i][j]);
}
}
}

case 1:nhapbp();break;
case 2:nhapfile();break;
case 3:
d=0;
printf("\n cac thanh phan lien thong la:\n");
for ( u=1;u<=n;u++){
if (chuaxet[u]){
d++;
printf("\n thanh phan lien thong thu %d\n",d);
DFS_Dequi(u);
}
};break;
case 4:return 0;
default:printf("nhap sai vui long nhap lai \n");break;
}
}
getch();
return 0;
"mrHUTEOws^A