Probleme de informatică
Clasa a IX-a
Elementele de bază C++ (46)
Subprograme predefinite (1)
Fişiere text (2)
Algoritmi elementari (109)
Tablouri unidimensionale (83)
Tablouri bidimensionale (64)
Probleme diverse (13)
Clasa a X-a
Subprograme (funcții) (87)
Şiruri de caractere (49)
Tipul înregistrare (26)
Recursivitate (57)
Alocarea dinamică a memoriei (2)
Liste înlănţuite (25)
Algoritmul lui Lee (1)
Clasa a XI-a
Metoda "Divide et impera" (12)
Metoda Backtracking (85)
Metoda Greedy (6)
Programare dinamică (18)
Grafuri neorientate (37)
Grafuri orientate (38)
Arbori (33)
Clasa a XII-a
Elemente de bază C# (32)
POO în C# (13)
Programare vizuală în C# (10)
Examen de bacalaureat
Competențe digitale
Examen de atestat
Admitere UBB (18)
Exemplu clasa graf neorientat si utilizare.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace grafuri
{
    class muchie
    {
        public int i, j;
        public muchie(int v1, int v2)
        {
            i = v1; j = v2;
        }
    }

    class graf_neorientat
    {
        //campuri ----------------------------------
        private int n;//nr de varfuri
        private int [,] A;//matricea de adiacenta
        private List<muchie> M;//lista muchiilor

        //proprietati -------------------------------
        public int N //proprietate pentru numarul de varfuri
        {
            set
            {
                if (n > 0)
                {
                    int vn = n;//vechiul n
                    n = value;//noul n
                    if (n > vn)//mai multe varfuri => creste matricea de adiacenta
                    {
                        int[,] vA = A;//vechiul A
                        A = new int[n + 1, n + 1];//noua matrice de adiacenta
                        for (int i = 1; i <= vn; i++)//copiez in noua matrice
                            for (int j = 1; j <= vn; j++)
                                A[i, j] = vA[i, j];
                    }
                    else
                        if (n < vn)//mai putine varfuri=> subgraf
                        {
                            for (int i = 0; i < M.Count(); i++)//parcurg muchiile
                                if (M[i].i > n || M[i].j > n)//daca au extremitate>n
                                {
                                    M.RemoveAt(i);//elimin muchia
                                    i--;
                                }
                        }
                }
            }
            get { return n; }
        }

        //indexatori --------------------------------
        public int this[int i, int j]//indexator pentru elementele matricii de adiacenta
        {
            set 
            {   //intai verificam corectitudinea indicilor
                if(i>=1 && i<=n && j>=1 && j<=n && i!=j)
                if ((value == 0 || value == 1) && A[i,j]!=value)
                {//doar daca se modifica in matricea de adiacenta
                    A[i, j] = value;
                    A[j, i] = value;
                    if (value == 0)
                    {//trebuie sa sterg muchia [i,j]
                        for (int k = 0; k < M.Count(); k++)//parcurg muchiile
                            if (M[k].i == i && M[k].j == j || M[k].i == j && M[k].j == i)//daca e muchia cautata
                                M.RemoveAt(k);//elimin muchia
                    }
                    else //value==1
                        M.Add(new muchie(i, j));//creez si adaug muchia [i,j]
                }
            }
            get
            {
                if (i >= 1 && i <= n && j >= 1 && j <= n)
                    return A[i, j];
                else return -1;
            }
        }

        //constructori ------------------------------
        public graf_neorientat(){}//constructor vid
        
        public graf_neorientat(int n, List<muchie> L)
        {//constructor avand la baza lista muchiilor
            this.n = n;//nr varfuri
            M = L;//lista muchiilor
            A = new int[n + 1, n + 1];//creez matricea de adiacenta
            foreach (muchie m in M)//parcurg muchiile
                A[m.i, m.j] = A[m.j, m.i] = 1;//pun 1 corespunzator muchiei
        }

        public graf_neorientat(int n, int[,] A)
        {//constructor pe baza matricii de adiacenta
            this.n = n;//nr de varfuri
            this.A = A;//matricea de adiacenta 
            M = new List<muchie>();//creez lista muchiilor
            for (int i = 1; i <= n; i++)//parcurg matricea
                for (int j = i + 1; j <= n; j++)//deasupra diag. principale
                    if (A[i, j] == 1)  //daca A[i,j]=1
                        M.Add(new muchie(i, j)); //adaug muchia [i,j]
        }

        public graf_neorientat(graf_neorientat G)
        {//constructor de copiere
            n = G.n;
            M = G.M;
            A = G.A;
        }

        //metode ------------------------------------
        public void citire(string fis)//citeste graful din fisierul dat
        {
            StreamReader fin = new StreamReader(fis);
            n=int.Parse(fin.ReadLine());//citesc numarul de varfuri
            M = new List<muchie>();//creez lista muchiilor
            A = new int[n + 1, n + 1];//creez matrice a de adiacenta
            while (!fin.EndOfStream)//citesc pana la sfarsitul fisierelui
            {
                string linie = fin.ReadLine();//o linie
                string[] s = linie.Split();//o desparte in doua
                int x = int.Parse(s[0]);//primul varf
                int y = int.Parse(s[1]);//al doilea varf
                A[x, y] = A[y, x] = 1;//pun in matricea de adiacenta
                muchie m = new muchie(x, y);//creez  o muchie
                M.Add(m);//o adaug in lista muchiilor
            }
            fin.Close();
        }

        public void afisare(string fis)//scrie graful in fisier
        {
            StreamWriter fout = new StreamWriter(fis);
            fout.WriteLine(n);//scriu nr de varfuri
            for(int i=1;i<=n;i++)
            {//scriu matricea de adiacenta
                for (int j = 1; j <= n; j++)
                    fout.Write(A[i, j] + " ");
                fout.WriteLine();
            }
            foreach (muchie m in M)//scriu lista muchiilor
                fout.WriteLine(m.i + " " + m.j);
            fout.Close();
        }

        public string BF(int v)//parcurgere in latime pornind din v
        {
            int[] x = new int[n + 1];//coada
            bool[] p = new bool[n + 1];//vizitat/nevizitat
            int st = 1, dr = 1;//capetele cozii
            x[1]=v;//incep cu v
            p[v] = true;//il marchez pe v ca vizitat
            while (st <= dr)//cat timp exista coada
            {
                for(int i=1;i<=n;i++)
                    if (A[x[st], i] == 1 && !p[i])//vecin nevizitat
                    {
                        dr++;//maresc coada
                        x[dr] = i;//adaug in coada
                        p[i] = true;//marchez ca vizitat
                    }
                st++; //avansez in coada
            }
            string s = "";//sirul rezultat
            for (int i = 1; i <= dr; i++) s = s + x[i] + " ";//adauga varfurile din parcurgere
            return s;
        }

        public bool conex()//verifica daca graful este conex
        {
            string s = BF(1);//situl parcurgerii in latime
            string[] vf = s.Split();//despart in varfuri
            int x = 0;
            foreach (string v in vf)
                if (v != "") x++; //numar varfurile
            if (x == n) return true;//conex daca am parcurs n varfuri
            else return false;
        }
    }
}

Pentru testare:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace grafuri
{
    class Program
    {
        static void Main(string[] args)
        {
            graf_neorientat G = new graf_neorientat();
            G.citire("graf.in");
            G.afisare("graf.out");
            Console.WriteLine(G.BF(6));//BF din varful 6
            if (G.conex()) Console.WriteLine("este conex");
            else Console.WriteLine("nu este conex");
            
            //teste pentru constructori
            List <muchie> L = new List<muchie>();//creea o lista de muchii
            L.Add(new muchie(3, 5));//adaug muchii
            L.Add(new muchie(1, 5));
            L.Add(new muchie(2, 3));
            L.Add(new muchie(3, 4));
            graf_neorientat G1 = new graf_neorientat(5, L);//creez un graf cu 5 varfuri si lista de muchii L 
            G1.afisare("g1.out");

            int[,] A ={{0,0,0,0,0},{0,0,1,1,1},{0,1,0,0,0},{0,1,0,0,1},
                    {0,1,0,1,0}};//initializare matrice
            G1 = new graf_neorientat(4, A);//construire graf cu matricea A
            G1.afisare("g2.out");

            G1 = new graf_neorientat(G);
            G1.afisare("g3.out");
           
            //teste proprietati
            G1.N = 10;
            G1.afisare("g4.out");
            G1.N = 4;
            G1.afisare("g5.out");

            //teste indexatori
            G1[1, 1] = 1;//nu face nimic pt ca indicii cu sunt corecti
            G1[2, 3] = 1;//adauga muchia [2,3]
            G1[2, 3] = 1;//nu face nimic pt ca muchie exista deja
            G1[56, -23] = 1;//nu face nimic pt indicii nu sunt corecti
            G1.afisare("g6.out");
            G1[1, 2] = 0;//sterg muchia [1,2]
            G1.afisare("g7.out");      
            Console.ReadKey();
        }
    }
}

19 oct 2018
Site-ul conține 867 de probleme rezolvate
Copyright © 2009-2018 Muresan Vasile Ciprian