найти минимальное остовное дерево с использованием глубины первого поиска в C

Question

Я пытаюсь реализовать алгоритм в c, который находит MST с использованием DFS. Я уже нашел DFS algortihm, и я понимаю это довольно хорошо. Я также знаю, что я должен выполнить следующие шаги для достижения своей цели:

1 Запустите DFS, пока не найдете, что ребро назад или DFS остановлено. Если остановили возвращение Г.

2 На окружности, построенного в обратном перепаду найти самый тяжелый край и удалить его из G.

3 Возврат к 1.

Вот код ДФС:

#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. Чтобы перезапустить поиск по глубине, поместите стек, пока не нажмете одну из конечных точек удаленного края. Каждый раз, когда вы что-то выскакиваете, очищайте свой посещаемый флаг. Поиск по глубине продолжается отсюда (полный перезапуск не нужен, потому что он будет делать то же самое до этого).