Как кодировать матрицу смежности из файла взвешенного графа

Question

Я только начал изучать графы и матрицы смежности, и мне нужно создать матрицу смежности из текстового файла взвешенного графа.Текстовый файл будет выглядеть примерно так:

0 4 5 0 6
4 0 0 3 6
5 0 0 0 8
0 3 0 0 0
6 6 8 0 0

(Можно предположить, что матрица всегда будет симметричной)

Исходя из этого, мы должны создать метод для поиска в ширину.и поиск в глубину.Я понимаю теорию графов и поисков, но у меня возникают проблемы с ее кодированием.Кроме того, если бы вы могли делать код sudo вместо реального кода, чтобы я все еще мог изучить / сделать это сам, это было бы здорово!Большое вам спасибо!

Answer 1

Для поиска в глубину я бы использовал рекурсивную функцию и передавал бы int текущего узла и список уже посещенных в нем узлов, повторял это до тех пор, пока не будут посещены все узлы, и не возвращался бы к рекурсии, чтобы перейти к следующему.вместе с посещением всех

check node(currentNode, ListOfVisited)

     check=0
     while(check!=n)//where n is the size of the array
         if (matrix.get(check,currentNode) is not in ListOFVisited)
         add n to listOfVisted 
         checkNode(currentNode, ListOfVisited)
     end while

// этот код будет вызываться при возврате функции

check++

 end while

для первого поиска. Я бы также сделал это рекурсивноно сначала проверьте всех соседей и удерживайте их в очереди, а затем повторите через очередь после

 queue is empty

 checknode(node, visited)
     check=0
     while(check!=n)
         if (matrix.get(check,currentNode) isn't in visited)
             queue.add(check)
         end if
         check++
     end while
 while(queue isn't empty)
     checkNode(queue.pop)
 end while