Δημιουργία γραφου σε C++

[MixalisDev]

Καλησπερα ειμαι νεος σχετικα στον χωρο του προγραμματισμου το προβλημα μου ειναι οτι  δεν ξερω πως πρεπει ακριβως να σκεφτομαι...

Αυτο που θελω να κανω εινια να φτιαξω ενα προγραμμα που να δημηουργει ενα γραφο και μετα να μπορω να κανω αναζητησεις πανω στο γραφο(bfs,dfs,ucs)...

Αλλα για αρχη θα ηθελα την βοηθεια σας για να φτιαξω εναν πολυ απλο γραφο....

Την θεωρια την ξερω αλλα δεν ξερω πως μπορω να το υλοποιησω σε c++

Ευχαριστω....

[albNik]

Ο πιο εύκολος τρόπος ειναι να φτιαξεις ενα διδιαστατο πινακα NxN οπου Ν ειναι οι κομβοι και να βάλεις τιμες A[i,j]=1 αν οι κομβοι i,j συνδεονται απευθειας, αλλιως A[i,j]=0.

 

Για αναζητηση δες:

http://stackoverflow.com/questions/23128064/depth-first-search-on-adjacency-matrix

[lion2486]

Χμμ.. Εγω θα προτεινα αυτοαναφορικες δομες, δλδ δεικτες μεσα στον κομβο για αλλο κομβο. Ισως σε μπερδεψει πιο πολυ, αλλα ειναι μια επιλογη..

[MixalisDev]

Ο πιο εύκολος τρόπος ειναι να φτιαξεις ενα διδιαστατο πινακα NxN οπου Ν ειναι οι κομβοι και να βάλεις τιμες A[i,j]=1 αν οι κομβοι i,j συνδεονται απευθειας, αλλιως A[i,j]=0.

 

Για αναζητηση δες:

http://stackoverflow.com/questions/23128064/depth-first-search-on-adjacency-matrix

Εννοεις να χρησιμοποιησω πίνακα γειτνίασης....εγω σκεφτομουν να χρησιμοποιησω λιστα  γειτνίασης αλλα παιζει να ειναι πιο δυσκολο...

Χμμ.. Εγω θα προτεινα αυτοαναφορικες δομες, δλδ δεικτες μεσα στον κομβο για αλλο κομβο. Ισως σε μπερδεψει πιο πολυ, αλλα ειναι μια επιλογη..

Συνδεδεμενη λιστα εννοεις?οντως ειναι λιγο μπερδεμα..το vector τησ STL το ιδιο δεν ειναι?

[zynif]

Εννοεις να χρησιμοποιησω πίνακα γειτνίασης....εγω σκεφτομουν να χρησιμοποιησω λιστα  γειτνίασης αλλα παιζει να ειναι πιο δυσκολο...

Συνδεδεμενη λιστα εννοεις?οντως ειναι λιγο μπερδεμα..το vector τησ STL το ιδιο δεν ειναι?

Μια χαρά θα είναι ενα vector που θα περιέχει τους γείτονες

[MixalisDev]

Ωραια σκεφτομαι να φτιαξω δομη η οποια να πιερχει δυο στοιχεια

το ενα θα ειναι ενας πινακας μονοδιαστατος που θα περιεχει τις κορυφες και το αλλο θα ειναι ενα vector το οποιο θα εχει τους γειτονες...

Σωστη η σκεψη μου ή ειναι τελειως ακυρη??

[zynif]

Όχι ακριβώς .

Ένα vector γειτόνων για κάθε κόμβο .

Κάτιι σαν το παρακάτω  δηλαδή

 

class Node:

     int NodeID;

     vector<int> Neighbours;

 

 

και στην main σου

vector<Node> MyGraph;

 

και ο DFS θα ναι κάπως έτσι

DFS(int goalNode,int currentNode) {
  if (currentNode==goalNode) {
    //OK
  }    
  else {
    for (int nextNode : MyGraph.at(currentNode)->Neighbours) {
      DFS( goal,nextNode);
   }
}

[defacer]

Για το θέμα που συζητάμε υπάρχει παραπάνω από αρκετή βιβλιογραφία. Ακόμα και το λήμμα της wikipedia (που είναι σίγουρα κάθε άλλο παρά η καλύτερη δυνατή αναφορά) παραθέτει τις κλασικές μεθόδους αναπαράστασης. Γιατί δε χρησιμοποιείς μια από αυτές;

[MixalisDev]

 

Όχι ακριβώς .

Ένα vector γειτόνων για κάθε κόμβο .

Κάτιι σαν το παρακάτω  δηλαδή

 

class Node:

     int NodeID;

     vector<int> Neighbours;

 

 

και στην main σου

vector<Node> MyGraph;

 

και ο DFS θα ναι κάπως έτσι

DFS(int goalNode,int currentNode) {
  if (currentNode==goalNode) {
    //OK
  }    
  else {
    for (int nextNode : MyGraph.at(currentNode)->Neighbours) {
      DFS( goal,nextNode);

Λοιπον κατι εκανα πολυ απλο για αρχη αλλα με stuct(θα το αναιβασω αργοτερα)...τωρα για τις αναζητησεις θα το δουμε αργοτερα μην το μπερδευουμε τωρα.

Ευχαριστω πολυ για την βοηθεια.

Επεξ/σία 6 Απριλίου 2015 από MixalisDev

[the other one]

Στο search εφόσον μικάμε για γράφο κι όχι για δέντρο θες μια δομή να κρατάς από πού περνά για να αποφύγεις τους κύκλους και τα ατέρμονα. Μάλιστα αν ξέρεις από την αρχή και το goal node μπορείς να το κάνεις και αμφίδρομο ( όπου σε αυτή τη περίπτωση ίσως να βόλευε καλύτερα η bfs ).

[MixalisDev]

Εκανα κατι πολυ απλο (μπορει να ειναι και τελειως λαθος...) για αρχη για να δουμε πως τα παω και βλεπουμε πως θα συνεχισω:

 
#include<iostream>
#include<vector>

using namespace std;

struct Node{
	int NodeID;
	vector<int>Neighbours;
};

int main(){
    vector<Node>Graph;
    Graph.push_back(Node());{
    	 Graph[0].NodeID=1;
    	 Graph[0].Neighbours.push_back(2);
    	 Graph[0].Neighbours.push_back(4);
    	 Graph[0].Neighbours.push_back(5);
    	 Graph[0].Neighbours.push_back(2);

    }
cout<<"Ο κόμβος:"<<Graph[0].NodeID<<" εννονεταi:";
for(unsigned int i=0; i< Graph[0].Neighbours.size();i++)
cout<<" με τον κομβο:"<<Graph[0].Neighbours[i];
}

[brute-force]

Η πτυχιακή μου out in the wild (δημιουργία ενός προσημασμένου γράφου και διάσχιση του είτε με BFS είτε με DFS). Προσωπικά δεν θεωρώ τον κώδικα δύσκολο, ειδικά ο αλγόριθμός δημιουργίας γράφων είναι πολύ απλός.

Σε ό,τι έχει να κάνει με το είδος της υλοποίησης ενός γράφου (πίνακας vs λίστα), όλα εξαρτώνται από το τι θεωρείς σημαντικότερο, πχ, θέλεις fast access σε τυχαίους κόμβους; Πίνακας. Θέλεις να εξοικονομήσεις χώρο; Λίστα. Και πάει λέγοντας...