c - 在C中使用深度优先搜索找到最小生成树

Question

我正在尝试在 c 中实现一种算法，该算法使用 DFS 查找 MST。我已经找到了 DFS 算法并且我非常了解它。我也知道我应该遵循以下步骤来实现我的目的:

1 运行 DFS，直到发现边缘向后移动或 DFS 停止。如果停止则返回 G。

2 在由向后的边构成的圆上找到最重的边并将其从 G 中删除。

3 返回 1。

这是 DFS 代码:

#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);
}

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

Answer 1

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

首先，修改您的 DFS 实现以使用显式堆栈而不是递归。创建一个新数组 int stack[10]; 和一个变量 int stacksize = 0;。这个想法是 stack[0], stack[1], ..., stack[stacksize-1] 将对应于最外层主动调用的参数 i DFS 到最里面。我将保留一些粗略的细节，因为我确信还有关于这方面的其他问题/答案对。

其次，每当图有一条回到访问过的顶点的边时，就从堆栈顶部扫描回到访问过的顶点，寻找最重的边。找到它后，通过修改 G 删除该边。要重新启动深度优先搜索，请弹出堆栈，直到弹出已删除边的端点之一。每次弹出某些内容时，请清除其已访问标志。深度优先搜索从这里继续(不需要完全重新启动，因为它会做同样的事情到这里)。