Find all the way from between two vertices of graph


1. Introduction:

The idea of the algorithm: technical use depth-first search.
Description of inputs and outputs of the problem:
Input Data connected graph in the file and for File3.inp
- The first line contains the number n is the number of vertices in a graph (0 <n <100)
- The second line D peak and peak flow C.
- Line i + 2 (1 <= i <= n) contains n number of A [i, 1], A [i, 2] ... A [i, n] each number separated by a space.
Data output: Output to the screen all the way from the top of the D to C or notification does not exist in the path from D to C

timduongdi_exam

2. Source code:

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define FileIn "File3.inp"
int Count = 0;
int *L;
char *_tick;
int **A,n,D,C;
//Read data from file
void Read_File() {
FILE*f = fopen(FileIn,"rb");
fscanf(f,"%d%d%d",&n,&D,&C);
cout<<"Matric ressponding link: \n"<<D<<" "<<C<<endl;
*A = new int [n];
for(int i =0;i<n;i++) {
A[i] = new int [n];
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<A[i][j]<<" ";
}
cout<<endl;
}
fclose(f);
D--;
C--;
}
//Initial variable
void Initial() {
_tick = new char [n];
L = new int [n];
for (int i = 0; i<n; i++) {
_tick[i] = 0;
L[i] = 0;
}
_tick[D] = 1;
L[0] = D;
}
void PrintPath(int NumberOfEdges) {
Count++;
cout<<endl<<D+1;
for (int i = 1; i<NumberOfEdges; i++)
cout<<" -> "<<L[i]+1;
}
void Try(int NumberOfEdges) {
if(L[NumberOfEdges-1] == C)
PrintPath(NumberOfEdges);
else {
for(int i = 0; i<n; i++)
if( A[L[NumberOfEdges-1]][i]>0 && _tick[i] == 0 ){
L[NumberOfEdges] = i;
_tick[i] = 1;
Try(NumberOfEdges+1);
L[NumberOfEdges] = 0;
_tick[i]= 0;
}
}
}
//main function
void main() {
Read_File();
Initial();
cout<<"Path from "<<D+1<<" to "<<C+1;
Try(1);
if(Count==0)
cout<<" No path";
delete *A,DanhDau,L;
getch();
}

3. Result:

timduongdi_result


Advertisements