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();
}
}
}
|