lien thong
Thuật toán BFS (u):
Bước 1 (Khởi tạo):
Queue= Æ; Push(Queue,u); Chuaxet[u] = FALSE;
Bước 2 (Lặp):
while (Queue ≠ Æ ) {
s = Pop(Queue); <Thăm đỉnh s>;
for each t Î Ke(s) do {
if ( Chuaxet[t] ) {
Push( Queue, t); Chuaxet[t] = False;
}
}
}
Bước 3 (Trả lại kết quả) :
Return (<Tập đỉnh được duyệt) ;
Procedure DFS(v);
(*tim kiem theo chieu sau bat dau tu dinh v; cac bien Chuaxet, Ke la bien toan cuc*)
Begin
Tham_dinh(v);
Chuaxet[v]:=false;
For u Ke(v) do
If Chuaxet[u] then DFS(u);
End; (*dinh v da duyet xong*)
Một đồ thị vô hướng liên thông G =<V,E> được gọi là định chiều được nếu thay thế mỗi cạnh của G bằng một cung định hướng để được một đồ thị có hướng G’=<V,E> liên thông mạnh
CODE
#include <conio.h>
#include <stdio.h>
int *u;
void DFS(int **matrix,int n,int start){
//printf("%d ",start+1);
u[start] = 1;
for(int i=0;i<n;i++){
if(u[i] == 0 && matrix[start][i] != 0){
DFS(matrix,n,i);
}
}
}
/***********/
struct queue{
int *value;
int k;
} *QUEUE;
void create(queue *q,int size){
q->value = new int[size];
q->k = 0;
}
void push(queue *q,int value){
q->value[q->k] = value;
q->k++;
}
int pop(queue *q){
int next = q->value[0];
for(int i=1;i< q->k;i++){
q->value[i-1] =q->value[i];
}
q->k--;
return(next);
}
int empty(queue *q){
return(!q->k);
}
//
void BFS(int **matrix,int n,int start){
create(QUEUE,n);
push(QUEUE,start);
int i,next;
while(!empty(QUEUE)){
next = pop(QUEUE);
// printf("%d ",next+1);
u[next] = 1;
for(i=0;i<n;i++){
if(u[i] == 0 && matrix[next][i] !=0){
u[i] = 1;
push(QUEUE,i);
}
}
}
}
/****************/
int LienThong(int **matrix,int n){
/* Dem so thanh phan lien thong */
int i,k=0;
for(i=0;i<n;i++){
if(u[i] == 0){
k++;
DFS(matrix,n,i);
// BFS(matrix,n,i);
}
}
return(k);
}
/***************/
void CanhCau(int **matrix,int n){
//Khoi tao mang danh dau dinh chua xet
for(int m=0;m<n;m++){
u[m] = 0;
}
int lienThong = LienThong(matrix,n);
int k;
printf("
Cac canh cau :
");
for(int i = 0;i<n;i++){
for(int j=i;j<n;j++){
if(matrix[i][j] != 0){
matrix[i][j] = 0;
matrix[j][i] = 0;
//Khoi tao mang danh dau dinh chua xet
for(int m=0;m<n;m++){
u[m] = 0;
}
//
k = LienThong(matrix,n);
if(k>lienThong){
printf("(%d,%d) ",i+1,j+1);
}
matrix[i][j] = 1;
matrix[j][i] = 1;
}
}
}
}
/**********/
void DinhTru(int **matrix,int n){
//Khoi tao mang danh dau dinh chua xet
for(int m=0;m<n;m++){
u[m] = 0;
}
//
int lienThong = LienThong(matrix,n);
int i,j,k;
printf("
Cac Dinh tru :
");
int *temp = new int[n];
for(i = 0;i<n;i++){
for(j=0;j<n;j++){
temp[j] = matrix[i][j];
matrix[i][j] = 0;
matrix[j][i] = 0;
}
//Khoi tao mang danh dau dinh chua xet
for(int m=0;m<n;m++){
u[m] = 0;
}
//Khong xet dinh i
u[i] = 1;
//
k = LienThong(matrix,n);
if(k>lienThong){
printf("%d ",i+1);
}
for(j=0;j<n;j++){
matrix[i][j] = temp[j] ;
matrix[j][i] = temp[j];
}
}
}
void main(){
clrscr();
int **a,k,i,j;
FILE *in;
in = fopen("DFS.txt","r");
//Doc chi so mang va tao mang 2 chieu
fscanf(in,"%d",&k);
a = new int*[k];
for(i=0;i<k;i++){
a[i] = new int[k];
}
//Doc gia tri mang
for(i=0;i<k;i++){
for(j=0;j<k;j++){
fscanf(in,"%d",&a[i][j]);
}
}
//In mang ma tran
for(i=0;i<k;i++){
for(j=0;j<k;j++){
printf("%d ",a[i][j]);
}
printf("
");
}
//
u = new int[k];
for(i=0;i<k;i++){
u[i] = 0;
}
// int soLienThong = LienThong(a,k);
// printf("
%d
",soLienThong);
CanhCau(a,k);
DinhTru(a,k);
getch();
}
Bạn đang đọc truyện trên: Truyen247.Pro