Πρώτα Βήματα - Αρχές προγραμματισμού

Απ: Connectivity problem

agmarios — Tue, 12 Sep 2006 02:31:53 GMT

το μαθηματικό μοντέλο που περιγράφει το πρόβλημά σου είναι ο γράφος (υπάρχει ολόκληρος κλάδος η γραφο θεωρία που ασχολείται με αυτά τα μαραφέτια ) και συγκεκριμένα είναι αφμίδρομος (η σύνδεση 2-3 είναι ίδια με την 3-2) χωρίς βάρη (όλες οι συνδέσεις είναι ίδιες από πλευράς κόστους, απόστασης, ταχήτητας κλπ κλπ). Οι γράφοι είναι χρησιμότατοι όταν θέλουμε να περιγράψουμε δίκτυα (μάλλον κι εσύ αυτό θες). Στους γράφους λοιπόν έχεις κόμβους (τα αντικείμενά σου) και ακμές (οι συνδέσεις σου)

Στο συγκεκριμένο θέμα τώρα εσύ ψάχνεις τις απαραίτητες ακμές του γράφου έτσι ώστε όλοι οι κόμβοι να είναι συνδεδεμένοι μεταξύ τους χωρίς να σχηματίζονται κύκλοι. Ψάχνεις δηλαδή το ελάχιστο συνεκτικό δένδρο ( ένα γράφο δηλαδή που ξεκινώντας από έναν κόμβο μπορώ να επισκευτώ όλους τους άλλους χωρίς όμως να σχηματίζονται κυκλικές διαδρομές. Προφανώς αν ο γράφος σου έχει Ν κόμβους τότε το συνεκτικό δένδρο πρέπει να έχει ακριβώς Ν-1 ακμές. (πιστεύω να είναι προφανές αυτό )

μια αναζήτηση στο google gia graph spanning tree θα σου βγάλει σίγουρα τον αλγόριθμο που ψάχνεις

Απ: Connectivity problem

tommaσ — Tue, 12 Sep 2006 00:54:07 GMT

επισεις θα ήθελα να ρωτήσω(η να μάθω):
ότι σχετική ιστοσελίδα ξέρεται με αλγόριθμους.

και γενικά πληροφορίες που μπορούν να μουν φανούν χρήσιμες

σημείωση:
μήπως πρέπει να μπει και ένα Forum με τίτλο αλγόριθμοι?(αφου εκεί είναι οι βάσεις του προγραμματισμός)

Connectivity problem

tommaσ — Tue, 12 Sep 2006 00:43:07 GMT

Καλυσπέρα!!

          θα ήθελα την βοηθειά σας στην δημιουργεια ενος αλγόριθμου..

                            με δεδομένη μια ακολουθία ζευγών ακεραίων που αντιπροσωπεύουν τις συνδέσεις μεταξύ αντικειμένων (στα αριστερά) ,δουλεία ενός αλγόριθμου συνδετικότητας είναι να εξάγει εκείνα τα ζευγη που παρέχουν τις νέες συνδέσεις (στο κεντρο) . Για παράδειγμα, το ζεύγος 2-9 δεν περιλαμβάνεται στην έξοδο επειδή η σύνδεση 2-3-4-9 συνεπάγεται απο προηγούμενες συνδέσεις(όπως σείχνει δεξιά

    p-q// in // out               // Σχόλεια!   |(0) = id[0]|
1. |3-4       | 3-4                | (0) 3->4
2. |4-9        | 4-9                | (0) 3->4->9
3. |8-0        | 8-0                | (0) 3->4->9    (1) 8->0
4. |2-3        | 2-3                | (0) 2->3->4->9
5. |5-6        | 5-6                | (0) 2->3->4->9 (1) 8->0 (2) 5->6
6. |2-9        |     | 2-3-4-9       | (0) 2->3->4->9 (1) 8->0 (2) 5->6
7. |5-9        | 5-9                | (0) 2->3->4->9->5->6 (1) 8->0
8. |7-3        | 7-3                | (0) 2->3->7->4->9->5->6 (1) 8->0
9. |4-8        | 4-8                | (0) 2->3->7->4->8->0->9->5->6
10. |5-6    |     | 5-6           | (0) 2->3->7->4->8->0->9->5->6
11. |0-2    |      |0-8-4-3-2     | (0) 2->3->7->4->8->0->9->5->6
12. |6-1    | 6-1                | (0) 2->3->7->4->8->0->9->5->6->1

                το τρίτο μέρος είναι δικο μου το πρόσθεσα για την βοήθεια "μου" γαι την επίληση του αλγορίθμου όπως διακρίνεται χριάζεται η ανάπτηξει κάπιον δέντρον(δηλαδεί δασοι) και στο τέλος η ένωση του.δηλαδεί θα χρειαστεί : ψάξιμο και ένωση για την ολοκλήρωση του αλγόριθμου.

    προσθέτω μια ΑΠΟΤΗΧΉ προσπάθεια μου για την επίληση του αλγορίθμου

#define N 10
#include <iostream>
using namespace std;
//
//
static int id[ N][ N];
static int p,q,Fid = 0;
static int Iid[ N] = {0};
// προσπαθώ να φτιάξω ενα δυναμικό πίνακα
// όπου όποτε χρείθαζεται να προστεθεί ένα δέντρο να πρεσθέτετε
// και ένας πίνακας
// στον κάθε πίνακα προσθέτω τα δεδομένα(γνωστα ως data)
// και αφξάνω την Fid έτσι ωστε να έχω τον τελευταίο πίνακα
//..
int main()
{
        while( cin >> p/*3*/ >> q/*4*/)
            {
                for(static int i = 0;Fid >= i;i++)
                    for(static int ii = 0;ii <= N; ii++)
                        if(id[ i][ ii] == p || id[ i][ ii] == q)
                            { id[ i][ Iid[ i]++] = p; id[ i][ Iid[ i]++] = q; break; }
                        else
                            {
                                id[ Fid ][ 0] = p;
                                id[ Fid++][ 1] = q;
                                Iid[ Fid] = 2;
                            }
            }
    system("PAUSE");// πάυσει
    return 0;
}