문자열 경로 지정 BFS

두 문자열 사이의 최단 경로를 찾고 얼마나 많은 단계를 수행했는지 int를 반환하려고합니다. 각 String (키)에 해당 문자열이 모두 들어있는 String[] (객체)가있는 HashMap이 있다고 가정합니다.문자열 경로 지정 BFS

이 코드는 내가 채찍질 한 것입니다. 방금 기본 BFS를 가져 와서 복사하려고했으나 진행 방법을 알 수 없습니다. 물고기에서 암소에

Goat, adj[] {Fish, Cow, Chicken} 
Cow, adj[] {Pig, Pigeon} 
Fish, adj[] {Goat, Bulbasaur, Dolphin, Eagle}

내가 두 단계가 필요합니다

public class Main { 
private static HashMap<String, String[]> list; 

private static int makePath(String from, string to) { 

    int path = 0; 
    PriorityQueue<String> queue = new PriorityQueue<>(); 
    queue.add(from); 

    while (!queue.isEmpty()) { 
     String u = queue.poll(); 
     if (u == to) { 
      return path; 
     } 
     else { 
      for (String r : list.get(u)) { 

       ... 

      } 
      return path; 
     } 
    } 
    return 0; 
} 

}

이 내 HashMap의이 어떻게 보이는지 단지 예입니다. 물고기에서 염소, 염소에서 물고기까지. 당신이 가지고있는 경우

그래서 어떤 아이디어는 내가 2 대기열을 사용하는 생각입니다 :)

출처

2013-04-30 Swidtter

당신이 "문자열 경로"가 무엇을 의미합니까? [edit distance] (http://en.wikipedia.org/wiki/Levenshtein_distance)와 같은 것을 의미합니까? –

집합의 두 문자열 사이에 경로가 있습니다. HashMap에 포함되어있는 각 문자열에는 이웃 배열이 있습니다. – Swidtter

나는 그가 그래프 데이터 구조를 가지고 있다고 말하려고 노력하고 있으며, 노드들 사이의 최단 경로 알고리즘을 찾고있다. –

공유 주시기 바랍니다. from 단어를 firstQueue에 대기열에 넣고 firstQueue은 비어 있지 않지만 그 이웃 주소가 여전히 to이 아닌 경우 다른 대기열에 이웃 노드를 저장하는 대체 논리를 수행합니다.

나는 코드를 제공하는 경우 그것은 분명있을거야

private static int makePath(final HashMap<String, String[]> tree, final String from, final String to) { 

     int path = 0; 
     Queue<String> firstQueue = new PriorityQueue<>(); 
     Queue<String> secondQueue = new PriorityQueue<>(); 
     firstQueue.add(from); 

     while (!firstQueue.isEmpty()) { 
      String key = firstQueue.poll(); 
      String[] neighbors = tree.get(key); 
      if (neighbors != null) { 
       path++; 
       for (String neighbor : neighbors) { 
        if (neighbor.equals(to)) { 
         return path; 
        } else { 
         secondQueue.add(neighbor); 
        } 
       } 
      } 

      while (!secondQueue.isEmpty()) { 
       key = secondQueue.poll(); 
       neighbors = tree.get(key); 
       if (neighbors != null) { 
        path++; 
        for (String neighbor : neighbors) { 
         if (neighbor.equals(to)) { 
          return path; 
         } else { 
          firstQueue.add(neighbor); 
         } 
        } 
       } 

      } 

     } 
     return 0; 
    }

출처

2013-04-30 19:34:07

문자열 경로 지정 BFS

답변

관련 문제