граф в SML Нью-Джерси - PullRequest
Новая
       2

граф в SML Нью-Джерси

1 голос
/ 29 ноября 2010

Мне нужно написать некоторую функцию, используя ML, эта функция получает список ребер направленного графа [(1,2), (1,3), (3,2)] , это означает направленное ребро от 1 до 2 и от 1 до 3 ... и я также получаю две вершины, мне нужно найти все возможные пути от первой вершины ко второй и список возможных путей, дляпример для вершин 1, 2 , мне нужно отобразить список [[1,2], [1,3,2]] , как я могу сделать это ML, если можно 'не храните данные о вершинах, заранее спасибо за любую идею.

Ответы [ 3 ]

3 голосов
/ 01 декабря 2010

Если вы хотите хранить данные о вершинах, вам нужна конечная карта от вершин до данных. Карта может предложить такую ​​подпись: 

type 'a vmap (* vertex map *)
val empty : 'a vmap  (* empty map *)
val insert : vertex * 'a * 'a vmap -> 'a vmap  (* add info about a vertex *)
val lookup : vertex * 'a vmap -> 'a option  (* look for info about a vertex *)

Чтобы реализовать эту сигнатуру, вы можете рассмотреть простой список из vertex * 'a пар или нечто более амбициозное, например сбалансированное дерево двоичного поиска.

2 голосов
/ 29 ноября 2010

Вы можете хранить данные о вершинах!

Например, хотите ли вы записать, какие вершины вы посетили?

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

Может принимать вектор неизведанных ребер, а также текущую вершину и целевую вершину.Он вернет вектор путей, которые успешно дойдут до целевой вершины.

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

0 голосов
/ 10 декабря 2010

Извините, я не смог устоять

Я видел эту же головоломку (вопрос) на Yahoo!Отвечает , и я ответил на него.

Реализация началась как проект, основанный на создании дерева для обхода графа;но в итоге он соответствовал дизайну, выраженному ранее Алексом Брауном .

Первоначально планирование было выполнено в Haskell , следовательно, эта вспомогательная функция: 

fun replicate len el = 
    if len = 0 then nil else el::replicate (len -1) el

Основная реализация: 

fun routes  dst (edges:(int * int) list) src  = 
    let val (very_possible,remotely_possible) =
            if null edges
            then (nil,nil)
            else List.partition ((fn s=> s = src) o #1) edges 
        val (raw_solutions,dsts_is_nx_srcs) = 
            List.partition  ((fn d => d = dst) o #2) very_possible
        val solutions = replicate  (length raw_solutions) [src,dst]
        val full_rest_routes =
            let val rest_rest_routes = 
                    map (routes dst remotely_possible)  
                            ( map #2 dsts_is_nx_srcs )
              in map (fn lst => src::lst) (List.concat rest_rest_routes)
     end
     in case (very_possible, solutions, remotely_possible)
        of (nil, _,  _)       => nil
         |  (_::_, (p::ps), _) =>  solutions @ full_rest_routes
         |  (_::_, nil, _::_)  =>  full_rest_routes
  |  (_   , nil, nil )  => nil
     end

Пользовательский интерфейс: 

fun getPaths edges src dst  =  routes dst edges src

Код выше взят из rout4.sml ;но тестирование и ввод-вывод опущены.Даже если это не слишком долго, я все еще надеюсь, что это будет проще.

...