Anzahl der Knoten entlang eines Pfades finden

Question

Ich versuche, durch eine Ghetto-Karte zu navigieren. Ich Eingabe meine Knoten aus einer .txt, die Werte wie folgt hat:

3 -1 
2 3 -1 
1 -1 
0 1 4 6 -1 
3 5 7 -1 
4 7 8 -1 
3 7 -1 
4 5 6 8 -1 
5 7 -1 
10 -1 
9 -1 

So: 2

• Knoten 0 wird mit dem Knoten 3
• Knoten zu Knoten werden verbunden 1 und 3
• Knoten 2 wird mit dem Knoten 1

und so weiter verbunden sein ... ‚-1‘ wird nur die Leitung zu beenden

Momentan speichere ich sie in einem Array der Größe 11, wo ich gerade getline() verwendet habe, um jede Zeilennummer in die passende Array-Zelle zu ziehen; Dies wird auf dem Bildschirm ausgegeben. Ich werde sie auch in ein 2D-Array setzen, wo jeder Wert seine eigene Zelle hat. Ich werde den Benutzer nach einem Startknoten und Endknoten fragen, dann werde ich eine rekursive Funktion verwenden, um einen Pfad zwischen den beiden zu berechnen (falls es einen gibt), und ausgeben, wie viele Knoten sich auf diesem Pfad befinden. Ich bin nicht einmal am optimalen Weg interessiert, irgendjemand wird es tun.

Wie würde ich rekursiv darüber gehen? so weit

Der unvollendete Code:

#include<iostream> 
#include<fstream> 
#include<string> 
using namespace std; 

const int ARRAY_SIZE = 11; 

void toString(string network[ARRAY_SIZE]); 
int numNodes(string network[], int start, int end); 

int main() 
{ 
    int start; 
    int end; 

    // inputting network into array 
    string network[ARRAY_SIZE]; 

    ifstream in; 
    in.open("network.txt"); 

    if (in.is_open()) 
    { 
     while (!in.eof()) 
     { 
      for (int i = 0; i < ARRAY_SIZE; i++) 
      { 
       getline(in, network[i]); 
      } 
     } 
    } 

    in.close(); 

    //start of user prompts 
    cout << "Welcome. " << endl << "Here is the network " << endl << endl; 

    toString(network); 

    // the loop for start val 
    do 
    { 
     cout << "Please enter a a starting node number (0-10), enter '-1' to quit" << endl; 
     cin >> start; 
     if (start == -1) 
      return 0; 
    } while (start < 0 && start > 10); 

    toString(network); 


    //loop for end value 
    do 
    { 
     cout << "Please enter an ending node number (0-10), enter '-1' to quit" << endl; 
     cin >> end; 
     if (start == -1) 
      return 0; 
    } while (end < 0 && end > 10); 


    //recursive stuffs 

    return 0; 
} 

int numNodes(string network[], int start, int end) 
{ 
    //unfinished function 
    int num; 

    //base case 
    if (start == end) 
    { 
     return 1; 
    } 

    //recursion 
    else 
    { 

    } 

    return num; 
} 

void toString(string network[ARRAY_SIZE]) 
{ 
    cout << endl; 
    for (int i = 0; i < ARRAY_SIZE; i++) 
    { 
     cout << network[i] << endl; 
    } 

    cout << endl; 
} 

Answer 1

nicht sicher, was du mit ‚Ghetto Karte‘ meine, ich bin Ihnen seine nur einen Witz zu erraten.

Worüber Sie eigentlich sprechen, ist ein Konzept in Informatik/Diskrete Mathematik genannt Graph. Es gibt viele Arten von Diagrammen, Grafiken, die nur positive Gewichte Graphen haben, die negative Gewichte enthalten, Graphen, in denen alle Wege sind bidirektional, graphische Darstellungen, die Wege sind unidirektional, Graphen, in denen alle Kanten verbunden werden müssen, Grafiken Kanten waren eine gewisse Wicht, Kapazität und/oder einige andere Funktionen etc ...

In diesem Fall, was ich denke, was Sie zu tun haben, ist eine ungewichtete (keine Gewichte an Kanten zugewiesen) directed (eine Verbindung von A nach B impliziert keine Verbindung von B zu A) Graphen (ungewichteter gerichteter Graph) und wo der Graph zusätzlich unconnected sein kann oder nicht.

Sie verwenden zusätzlich einen Typ Adjacency List, um die Verbindungen zwischen Graphknoten darzustellen.

Es gibt viele Algorithmen, um eine grafische Darstellung (wie Dijkstras für Wegfindung oder Uniform Cost Search) zu durchqueren, aber die meisten, wenn nicht alle diese Algorithmen stammen aus zwei Algorithmen einfache Suche genannt Depth First Search und Breadth First Search

Tiefensuche ist genau was der Name impliziert. Wenn Sie eine gewisse Struktur haben Ihr Diagramm darstellen (sagen wir, Ihre Adjazenzliste) Sie den rechten oder linken meisten Knoten zum tiefsten Punkt immer wieder suchen, bis Sie entweder Hit Ihr Ziel oder in eine Sackgasse. Diese wie folgt aussehen könnte (man beachte dies Python):

def DepthFirstSearch(adjacencylist, start, end): 
    traversallist = [] 
    traversallist.push(start) 
    for edge in adjacencylist[start]: 
     if edge.connectsTo(end): 
      traversalstack.push(end) 
      return traversallist 
     else: 
      resursivelist = DepthFirstSearch(adjacencylist, edge.endNode(), end) 
      if resursive_list != []: 
       return traversallist.extend(recursivelist) 
    return [] 

wenn es eine leere Liste ([]) gibt es keine Verbindung. Wenn dies nicht der Fall war, gab es eine Verbindung und gab den ersten gefundenen Pfad zurück.

Breitest Suche ist exaclty was seine Name impliziert.Im selben Szenario wie zuvor suchen Sie nicht nach dem tiefsten Knoten, sondern suchen zuerst an jeder Verbindungskante, bevor Sie tiefer gehen. Dies könnte wie folgt aussehen:

#note that queue starts with the start element 
def BreadthFirstSearch(adjacencylist, queue, end): 
    start = queue.pop() 
    traversallist = [] 
    traversallist.push(start) 

    for edge in adjacencylist[start]: 
     if edge.connectsTo(end): 
      traversalstack.push(end) 
      return traversallist 
    queue.push(adjacencylist[start]) 
    if not queue.empty(): 
     return traversallist.extend(BreadthFirstSearch(adjacencylist, queue, end)) 
    else: 
     return [] 

Beide Verfahren sind jedoch läuft infinently in dem Fall, in dem Sie eine Schleife während Traversal haben. Um dies zu vermeiden, können Sie eine Liste (oder eine bessere Laufzeit-Komplexität, eine Hashtabelle) einrichten, um zu sehen, ob Sie bereits etwas durchlaufen haben.

def DepthFirstSearch(adjacencylist, start, end, closedset): 
    ... 
    if start not in closedset: 
    ... 
    else: 
     return [] 

def BreadthFirstSearch(adjacencylist, queue, end, closedset): 
    ... 
    if start not in closedset: 
    ... 
    else: 
     return [] 

Dies sollten Sie genügend Informationen geben einen Graphweg finder zu implementieren, die einen Weg zurück (von denen Sie einfach die Größe zurückkehren kann, wenn man die Anzahl der Knoten benötigen nur) in C++.