I'm trying to implement an algorithm in c which finds MST using DFS. I've already found the DFS algortihm and i understand it pretty well. I also know that i should follow these steps to achieve my purpose :
1 Run DFS till you find an edge going backwards or DFS stopped. If stopped return G.
2 On the circle that is constructed by the backwards going edge find the heaviest edge and remove it from G.
3 Return to 1.
Here is the DFS code :
#include<stdio.h>
void DFS(int);
int G[10][10],visited[10],n; //n is no of vertices and graph is sorted in array G[10][10]
void main()
{
int i,j;
printf("Enter number of vertices:");
scanf("%d",&n);
//read the adjecency matrix
printf("
Enter adjecency matrix of the graph:");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
fscanf("%d",&G[i][j]);
//visited is initialized to zero
for(i=0;i<n;i++)
visited[i]=0;
DFS(0);
}
void DFS(int i)
{
int j;
printf("
%d",i);
visited[i]=1; // éviter cycle
for(j=0;j<n;j++)
if(!visited[j]&&G[i][j]==1)
DFS(j);
}
I need your help to implement the full algorithm or at least some advices. That would be much appreciated. Thank's in advance.
See Question&Answers more detail:
os 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…