在C中使用深度优先搜索找到最小生成树 [英] find minimum spanning tree using depth first search in C

问题描述

我试图在c中实现一个使用DFS发现MST的算法。我已经找到了DFS algortihm，我理解得非常好。我也知道我应该按照以下步骤达到我的目的：

运行DFS，直到您发现边缘倒退或DFS停止。如果停止返回G。

<2>在由向后边缘构建的圆上找到最重的边并从G中移除。

<3>返回1.

以下是DFS代码：

 ＃包括< stdio.h中> 
 void DFS（int）; 
 int G [10] [10]，visited [10]，n; // n是顶点的数目，并且图形在数组G中排序[10] [10] 
 void main（）
 {
 int i，j; 
 
 printf（输入顶点数：）; 
 scanf（％d，& n）; 
 
 //读取adjecency矩阵
 printf（\\\
Enter图的adjecency矩阵：）;对于（j = 0; j  fscanf（％d，& G [i]），
对于（i = 0; i< n; i ++） J]）;对于（i = 0; i  visited [i] = 0，
 $ b $ // // visited被初始化为零
; 
 
 DFS（0）; 
} 
 void DFS（int i）
 {
 int j; 
 printf（\\\
％d，i）; 
 visited [i] = 1;如果（！visited [j]&& G [i] [j] == 1）
，则对于（j = 0; j ，//éviter循环
 DFS（J）; 
} 
  

我需要您的帮助来实现完整的算法或至少一些建议。这将非常感激。

解决方案

这听起来像是家庭作业，所以我会告诉你我将如何解决问题。 >

首先，修改您的DFS实现以使用显式堆栈而不是递归。创建一个新的数组 int stack [10]; 和一个变量 int stacksize = 0; 。这个想法是， stack [0]，stack [1]，...，stack [stacksize-1] 将对应于参数 i 的最外面的活动调用 DFS 到最里面。第二，每当图形有一个边缘的时候回到访问的顶点，从栈顶扫描回访问的顶点，寻找最重的边缘。一旦找到它，通过修改 G 删除该边。要重新开始深度优先搜索，请弹出堆栈，直到弹出删除边缘的其中一个端点。每次你弹出一些东西时，清除它的访问标志。深度优先搜索从这里继续（完全重新启动并不是必须的，因为它可以做同样的事情，直到这里）。

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("\nEnter 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("\n%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.

解决方案

This sounds like homework, so I'll tell you how I would approach the problem.

First, modify your DFS implementation to use an explicit stack instead of recursion. Create a new array int stack[10]; and a variable int stacksize = 0;. The idea is that stack[0], stack[1], ..., stack[stacksize-1] will correspond to the arguments i of the outermost active invocation of DFS to the innermost. I'll leave the details a bit sketchy because I'm sure that there have been other question/answer pairs about this aspect.

Second, whenever the graph has an edge back to a visited vertex, scan from the top of the stack back to the visited vertex, looking for the heaviest edge. Once you find it, delete that edge by modifying G. To restart the depth-first search, pop the stack until you pop one of the endpoints of the deleted edge. Each time you pop something, clear its visited flag. The depth-first search continues from here (a complete restart is not necessary because it would do the same thing up to here).

这篇关于在C中使用深度优先搜索找到最小生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！