Cum pentru a determina dacă sunt conectate două noduri?

voturi
13

Sunt îngrijorat de faptul că acest lucru ar putea fi de lucru pe o problemă NP-completă. Sper că cineva mă poate da un răspuns la întrebarea dacă este sau nu. Și eu caut mai mult decât un răspuns pur și simplu da sau nu. Aș vrea să știu de ce. Dacă se poate spune, „Aceasta este, în principiu această problemă«x», care este / nu este NP-complet. (Link-ul wikipedia)“

(Nici acest lucru nu este temele)

Există o modalitate de a determina dacă două puncte sunt conectate la un grafic de bază non-direcționată arbitrar. de exemplu, următoarele

Well
  |
  |
  A
  |
  +--B--+--C--+--D--+
  |     |     |     |
  |     |     |     |
  E     F     G     H
  |     |     |     |
  |     |     |     |
  +--J--+--K--+--L--+
                    |
                    |
                    M
                    |
                    |
                  House

Punctele A deși M (nu „I“) sunt puncte de control (cum ar fi o supapă într-o conductă de gaze naturale), care poate fi deschis sau închis. De „+“ S sunt noduri (cum ar fi conducta de T), și cred ca bine si Casa sunt, de asemenea, nodurile, de asemenea.

Aș vrea să știu dacă am închis un punct arbitrar de control (de exemplu, C), dacă bine si Casa sunt încă conectate (alte puncte de control poate fi, de asemenea, închise). De exemplu, în cazul în care B, K și D sunt închise, avem încă o cale prin AEJFCGLM, și de închidere C, se va deconecta bine si Casa. Desigur; în cazul în care doar D a fost închis, de închidere numai C nu se debranșează House.

Un alt mod de a pune acest lucru, este C, un pod / tăiat marginea / istm?

Aș putea trata fiecare punct de control ca o greutate pe grafic (fie 0 pentru deschis sau 1 pentru închise); și apoi a găsi calea cea mai scurtă dintre bine și Casa (un rezultat> = 1 ar indica faptul că au fost deconectate. Există mai multe moduri pot scurtcircuita algoritmul pentru a găsi calea cea mai scurtă prea (de exemplu, aruncați o cale odată ce ajunge la 1, opriți se caută o dată avem orice cale care leagă bine si Casa, etc). şi, bineînțeles, eu pot, de asemenea, pus în unele limite artificiale de cât de multe hamei pentru a verifica înainte de a renunța.

Cineva trebuie să fi clasificat acest tip de problemă înainte, eu doar lipsește numele.

Întrebat 09/12/2008 la 22:41
sursa de către utilizator
În alte limbi...                            


11 răspunsuri

voturi
31

Descrierea dvs. pare să indice că sunteți interesați doar dacă două noduri sunt conectate, nu a găsi calea cea mai scurtă.

Găsirea în cazul în care sunt conectate două noduri este relativ ușoară:

Create two sets of nodes:  toDoSet and doneSet
Add the source node to the toDoSet 
while (toDoSet is not empty) {
  Remove the first element from toDoList
  Add it to doneList
  foreach (node reachable from the removed node) {
    if (the node equals the destination node) {
       return success
    }
    if (the node is not in doneSet) {
       add it to toDoSet 
    }
  }
}

return failure.

Dacă utilizați un tabel hash sau ceva similar pentru toDoSet și doneSet, cred că acest lucru este un algoritm liniar.

Rețineți că acest algoritm este, în principiu porțiunea marca de colectare a gunoiului marca și-matura.

Publicat 09/12/2008 la 22:52
sursa de către utilizator

voturi
6

A se vedea http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm , magazin unic pentru toate problemele legate de grafic. Cred că problema ta este , de fapt , rezolvabilă în timp pătratic.

Publicat 09/12/2008 la 22:45
sursa de către utilizator

voturi
5

Nu ai nevoie de algoritmul lui Dijkstra pentru această problemă, deoarece folosește un Heap, care nu este necesară și introduce un factor de log (N) la complexitatea dumneavoastră. Aceasta este doar prima lățime de căutare - nu includ marginile închise ca margini.

Publicat 09/12/2008 la 23:08
sursa de către utilizator

voturi
3

Problema de a găsi calea cea mai scurtă nu este NP-completă. Se numește Problema cea mai scurtă cale (suficient inițial) și există algoritmi pentru rezolvarea mai multe variante diferite ale acestuia.

Problema de a determina dacă sunt conectate două noduri nu este NP-completă, fie. Puteți utiliza o căutare adâncime prima de pornire la oricare nod pentru a determina dacă acesta este conectat la celălalt nod.

Publicat 09/12/2008 la 22:51
sursa de către utilizator

voturi
2

Presupunând că aveți o matrice de adiacență:

bool[,] adj = new bool[n, n];

În cazul în care bool [i, j] = true dacă există o cale deschisă între i și j și bool [i, i] = false.

public bool pathExists(int[,] adj, int start, int end)
{
  List<int> visited = new List<int>();
  List<int> inprocess = new List<int>();
  inprocess.Add(start);

  while(inprocess.Count > 0)
  {
    int cur = inprocess[0];
    inprocess.RemoveAt(0);
    if(cur == end)
      return true;
    if(visited.Contains(cur))
      continue;
    visited.Add(cur);
    for(int i = 0; i < adj.Length; i++)
      if(adj[cur, i] && !visited.Contains(i) && !inprocess.Contains(i))
        inprocess.Add(i);
  }
  return false;
}

Aici este o versiune recursiva a algoritmului de mai sus (scris în Ruby):

def connected? from, to, edges
  return true if from == to
  return true if edges.include?([from, to])
  return true if edges.include?([to, from])

  adjacent = edges.find_all { |e| e.include? from }
                  .flatten
                  .reject { |e| e == from }

  return adjacent.map do |a|
    connected? a, to, edges.reject { |e| e.include? from }
  end.any?
end
Publicat 09/12/2008 la 23:23
sursa de către utilizator

voturi
2

Pentru mine se pare ca esti pe la o soluție, dar este posibil am înțeles greșit problema. Dacă faci ca tine spun, și să dea marginile închise 1 ca greutate, poti aplica doar algoritmul lui Dijkstra, http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm . Acest lucru ar trebui să rezolve problema în O (E * lg (V))

Publicat 09/12/2008 la 22:49
sursa de către utilizator

voturi
2

nu NP-completă, rezolvată cu o soluție bine - cunoscut - Algoritmul lui Dijkstra

Publicat 09/12/2008 la 22:43
sursa de către utilizator

voturi
0

Văd că am primit răspunsul că este cu siguranta nu NP-completă și aceasta este o întrebare foarte veche, de asemenea.

Cu toate acestea, voi propune doar o altă abordare să se uite la problema. Ai putea folosi seturi disjuncte pentru acest lucru. În cele mai multe cazuri, pentru scenariul dat, abordarea va avea ca rezultat mai bun timp decât a face un grafic traversal (Aceasta include constanta de timp pentru o bucată mare de teste). Cu toate acestea, construirea graficului s - ar putea lua sumă bună de timp, în cazul în care este utilizat uniunea de compresie rang sau cale.

Puteți citi despre structura de date aici .

Publicat 03/09/2018 la 13:36
sursa de către utilizator

voturi
0

Dacă tot ce ai nevoie este de a determina dacă 2 noduri sunt conectate, puteți utiliza în loc seturi, care este mai rapid decât algoritmi de grafic.

  1. Split, întregul grafic în margini. Adăugați fiecare margine la un set.
  2. La iterație următoare, trage marginile între cele 2 noduri exterioare ale marginii făcute în pasul 2. Aceasta înseamnă adăugarea de noi noduri (cu seturile lor corespunzătoare) la setul marginea inițială era. (Practic set fuzionare)
  3. Repetați 2 până la 2 noduri pe care le căutați sunt în același set. Veți avea nevoie, de asemenea, pentru a face o verificare după etapa 1 (doar în cazul în care cele 2 noduri sunt adiacente).

La început, nodurile vor fi fiecare în setul său,

o   o1   o   o   o   o   o   o2
 \ /     \ /     \ /     \ /
 o o     o o     o o     o o
   \     /         \     /
   o o o o         o o o o 
      \               /
       o o1 o o o o o o2

Pe măsură ce algoritmul progresează și fuzionează seturi, relativ înjumătățește de intrare.

In exemplul de mai sus am fost în căutarea pentru a vedea dacă a existat o cale între o1 și o2. Am găsit această cale doar la sfârșitul anului, după care fuzionează toate marginile. Unele grafice pot avea componente separate (deconectat), ceea ce presupune că nu va fi capabil de a avea un set la sfârșitul anului. Într-un astfel de caz, puteți utiliza acest algoritm pentru a testa și chiar pentru conectare contoriza numărul de componente într-un grafic. Numărul de componente este numărul de seturi sunteți capabili de a obține atunci când termină algoritmul.

Un posibil grafic (pentru arborele de mai sus):

o-o1-o-o-o2
  |    |
  o    o
       |
       o
Publicat 17/12/2011 la 04:14
sursa de către utilizator

voturi
0

lui Dijkstra este nejustificată !! Doar utilizați lățime de căutare în primul rând de la A pentru a căuta nodul pe care doriți să ajungă. Dacă nu se poate găsi, nu este conectat. Complexitatea este O (nm) pentru fiecare căutare, care este mai puțin atunci Dijkstra.

Ceva legat este max-flow / cut-min problema. Uite-l, ar putea fi relevante pentru problema ta.

Publicat 12/12/2008 la 15:11
sursa de către utilizator

voturi
-1

Orice grafic algoritm calea cea mai scurtă va fi nejustificată , dacă tot ce ai nevoie este de a găsi în cazul în care un nod este conectat la altul. O bună bibliotecă Java care realizează că este JGraphT . Este de utilizare este destul de simplu, aici este un exemplu de grafic Integer:

public void loadGraph() {
    // first we create a new undirected graph of Integers
    UndirectedGraph<Integer, DefaultEdge> graph = new SimpleGraph<>(DefaultEdge.class);

    // then we add some nodes
    graph.addVertex(1);
    graph.addVertex(2);
    graph.addVertex(3);
    graph.addVertex(4);
    graph.addVertex(5);
    graph.addVertex(6);
    graph.addVertex(7);
    graph.addVertex(8);
    graph.addVertex(9);
    graph.addVertex(10);
    graph.addVertex(11);
    graph.addVertex(12);
    graph.addVertex(13);
    graph.addVertex(14);
    graph.addVertex(15);
    graph.addVertex(16);

    // then we connect the nodes
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.addEdge(3, 5);
    graph.addEdge(5, 6);
    graph.addEdge(6, 7);
    graph.addEdge(7, 8);
    graph.addEdge(8, 9);
    graph.addEdge(9, 10);
    graph.addEdge(10, 11);
    graph.addEdge(11, 12);
    graph.addEdge(13, 14);
    graph.addEdge(14, 15);
    graph.addEdge(15, 16);

    // finally we use ConnectivityInspector to check nodes connectivity
    ConnectivityInspector<Integer, DefaultEdge> inspector = new ConnectivityInspector<>(graph);

    debug(inspector, 1, 2);
    debug(inspector, 1, 4);
    debug(inspector, 1, 3);
    debug(inspector, 1, 12);
    debug(inspector, 16, 5);
}

private void debug(ConnectivityInspector<Integer, DefaultEdge> inspector, Integer n1, Integer n2) {
    System.out.println(String.format("are [%s] and [%s] connected? [%s]", n1, n2, inspector.pathExists(n1, n2)));
}

Acest lib oferă, de asemenea, toate cele mai scurte algoritmi căile de asemenea.

Publicat 14/11/2016 la 06:34
sursa de către utilizator

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more