Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.Threading.Tasks;
- using System.IO;
- namespace Euler
- {
- class Graf
- {
- private int liczbaWierzcholkow;
- private int liczbaKrawedzi;
- private int wielkosc=10;
- public List<int>[] lista = new List<int>[10];
- public bool[] odwiedzony = new bool[11];
- public Graf()
- {
- liczbaWierzcholkow = 0;
- liczbaKrawedzi = 0;
- }
- public void zbudujGraf()
- {
- Console.WriteLine("Podaj ilosc wierzcholkow: ");
- liczbaWierzcholkow = Convert.ToInt32(Console.ReadLine());
- Console.WriteLine("Podaj ilosc krawedzi: ");
- liczbaKrawedzi = Convert.ToInt32(Console.ReadLine());
- for (int i = 0; i <= liczbaWierzcholkow; i++)
- lista[i] = new List<int>();
- for (int i = 1; i <= liczbaKrawedzi; i++)
- {
- int w1, w2;
- Console.WriteLine("Krawędź: " + i + ": ");
- w1 = Convert.ToInt32(Console.ReadLine());
- w2 = Convert.ToInt32(Console.ReadLine());
- lista[w1].Add(w2);
- lista[w2].Add(w1);
- }
- zapiszGraf();
- Console.WriteLine();
- }
- public void dodajKrawędź(int w1, int w2)
- {
- if (lista[w1].Count == 0)
- liczbaWierzcholkow++;
- if (lista[w2].Count == 0)
- liczbaWierzcholkow++;
- lista[w1].Add(w2);
- lista[w2].Add(w1);
- liczbaKrawedzi++;
- }
- public void usuńKrawędź(int w1, int w2)
- {
- bool czyUsunieto = false;
- if (lista[w1].Count != 0)
- {
- lista[w1].Remove(w2);
- lista[w2].Remove(w1);
- czyUsunieto = true;
- }
- if (czyUsunieto == true)
- {
- Console.WriteLine("Usunieto krawedz: "+ w1 + " -> " + w2);
- if (lista[w1].Count == 0)
- liczbaWierzcholkow--;
- if (lista[w2].Count == 0)
- liczbaWierzcholkow--;
- liczbaKrawedzi--;
- }
- else
- Console.WriteLine("Blad usuwania krawedzi! Podana krawedz " + w1 + " -> " + w2 + " nie istnieje.");
- zapiszGraf();
- Console.WriteLine();
- }
- public void wyświetlListęSąsiadów()
- {
- if (liczbaWierzcholkow == 0)
- Console.WriteLine("Graf jest pusty!");
- else
- {
- Console.WriteLine("Lista sasiedztwa wyglada nastepujaco: ");
- for (int i = 1; i < liczbaWierzcholkow + 1; i++)
- {
- Console.Write("Wierzcholek " + i + ": ");
- for (int j = 0; j < lista[i].Count; j++)
- {
- if (j != lista[i].Count - 1)
- Console.Write(lista[i][j] + ", ");
- else
- Console.WriteLine(lista[i][j] + " ");
- }
- }
- }
- Console.WriteLine();
- }
- public void zapiszGraf()
- {
- StreamWriter zapisz = new StreamWriter("wyniki.txt");
- if (liczbaWierzcholkow == 0)
- Console.Write("Graf jest pusty!");
- else
- for (int i = 1; i < liczbaWierzcholkow + 1; i++)
- for (int j = 0; j < lista[i].Count; j++)
- zapisz.WriteLine(i + " " + lista[i][j]);
- zapisz.Close();
- }
- public void wczytajGraf()
- {
- StreamReader odczytaj = new StreamReader("wyniki.txt");
- string[] dane = new string[10];
- int liczbaLinii = 0;
- if (File.Exists("wyniki.txt"))
- {
- foreach (string line in File.ReadLines("wyniki.txt"))
- {
- if (line != String.Empty)
- liczbaLinii++;
- }
- for (int i = 0; i < liczbaLinii; i++)
- dane[i] = odczytaj.ReadLine();
- for (int i = 0; i <= liczbaLinii; i++)
- lista[i] = new List<int>();
- for (int i = 0; i < liczbaLinii; i++)
- {
- int w1, w2;
- w1 = Convert.ToInt32(dane[i].Substring(0, dane[i].IndexOf(" ")));
- w2 = Convert.ToInt32(dane[i].Substring(dane[i].IndexOf(" ")));
- if (lista[w1].Count == 0)
- liczbaWierzcholkow++;
- lista[w1].Add(w2);
- liczbaKrawedzi++;
- }
- }
- else
- Console.WriteLine("Nie można wczytać grafu! Nie zapisano żadnych krawędzi grafu.");
- odczytaj.Close();
- Console.WriteLine();
- }
- public void DFSHelper(int start, bool[] odwiedzony)
- {
- odwiedzony[start] = true;
- Console.Write(start + "->");
- if (lista[start] != null)
- foreach (var element in lista[start])
- if (!odwiedzony[element] == true)
- DFSHelper(element, odwiedzony);
- }
- public void DFS(int wierzcholekStart)
- {
- Console.WriteLine("DFS");
- DFSHelper(wierzcholekStart, odwiedzony);
- }
- public int s=0;
- public void Euler(int wierzcholekStart)
- {
- int[,] cykl = new int[wielkosc,wielkosc];
- int[] wypiszCykl = new int[wielkosc];
- for (int i = 1; i < liczbaWierzcholkow + 1; i++)
- for (int j = 0; j < lista[i].Count; j++)
- cykl[i,j] = lista[i][j];
- for (int i = 0; i < liczbaWierzcholkow; i++)
- {
- if (lista[i].Count % 2 != 0)
- {
- Console.WriteLine("Graf nie posiada Cyklu Eulera!");
- return;
- }
- }
- for (int i = 0; i < liczbaWierzcholkow; i++)
- {
- Nullable<int> value = cykl[wierzcholekStart,i];
- while (value.HasValue)
- {
- cykl[wierzcholekStart,i]--;
- cykl[i,wierzcholekStart]--;
- Euler(i);
- }
- wypiszCykl[s++] = wierzcholekStart;
- Console.Write(wypiszCykl[s++] + " -> ");
- }
- /*for (int i = 1; i < liczbaWierzcholkow + 1; i++)
- {
- Nullable<int> value = lista[wierzcholekStart][i];
- while (value.HasValue)
- {
- lista[wierzcholekStart].Remove(i);
- lista[i].Remove(wierzcholekStart);
- Euler(i);
- }
- wypiszCykl[s++] = wierzcholekStart;
- Console.Write(wypiszCykl[s++] + " -> ");
- }*/
- }
- }
- class Program
- {
- static void Main(string[] args)
- {
- Graf g1 = new Graf();
- g1.zbudujGraf();
- //g1.wyświetlListęSąsiadów();
- //g1.wczytajGraf();
- //g1.usuńKrawędź(1, 3);
- g1.wyświetlListęSąsiadów();
- //g1.DFS(1);
- g1.Euler(1);
- Console.ReadKey();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement