Теория графов. Поиск в ширину JAVA

[Annabel]

Снова слёзно прошу о помощи
смысл в том, чтобы осуществить поиск в глубину и в ширину графа и диграфа (направленного графа) с этим проблем не возникло. Только вот при помощи этого поиска нужно проверить целостность графа или диграфа. С графом проблем не возникает, а вот с диграфом... требуется после проверки на целостность диграфа переделать его в граф и проверить целостность полученного графа... насколько я понимаю, по пути ввода диграфа нудно параллельно запомнить эти значения для будущего графа, потому как если выполнять процедуру сразу после поиска, то оно проверяет полученное при поиске дерево=\ многое переделано, голова распухла( вот что у меня пока получилось:

[Annabel]

import java.util.*;

public class Main
{
public static void main (String[] args)
{
Graf graf = new Graf();
Scanner in = new Scanner(System.in);
int n=0;
int a, b,opcja;
//menu
do{
System.out.println();
System.out.println(" MENU");
System.out.println("1. nowyj graf");
System.out.println("2. nowyj digraf");
System.out.println("3. Dobavit' rebro");
System.out.println("4. udalit' vershinu");
System.out.println("5. Digraf->graf");
System.out.println("6. w glub'");
System.out.println("7. w shirinu");
System.out.println("8. matricy");
System.out.println("0. konec");
System.out.println();

opcja = in.nextInt();

switch(opcja)
{
case 1 :
System.out.print("kolwo wiershin grafa: ");
n = in.nextInt();
if(n<0) System.out.println("oshibka"); else {

graf.nowyGraf(n);

System.out.print(" kolwo reber grafa: ");
n = in.nextInt();
for(int k=0; k<n; ++k)
{
System.out.print("Rebro: ");
a = in.nextInt();
b = in.nextInt();
graf.dodajKrawedz(a,b);
}
graf.wypiszWszystko();
}
break;
case 2 :
System.out.print("Kolvo wershin digrafa: ");
n = in.nextInt();
graf.nowyDigraf(n);
System.out.print("Kolvo reber digrafa: ");
n = in.nextInt();
for(int k=0; k<n; ++k)
{
System.out.print("Rebro: ");
a = in.nextInt();
b = in.nextInt();
graf.dodajKrawedz(a,b);
}
graf.wypiszWszystko();
break;
case 3 :
System.out.print("Rebro: ");
a = in.nextInt();
b = in.nextInt();
graf.dodajKrawedz(a,b);
//graf.wypiszWszystko();
break;
case 4 :
System.out.print("Udaliaemaja vershina: ");
n = in.nextInt();
graf.usunWierzcholek(n);
//graf.wypiszWszystko();
break;
case 5 :
graf.DigraftoGraf();
graf.wypiszWszystko();
break;
case 6 :
graf.wglab();
break;

case 7 :
graf.wszerz();
break;
case 8 :
graf.wypiszWszystko();
break;
default: break;
}
}while(opcja!=0);
}
}

class Graf
{

private int mSasiedztwa[][]; //матрица смежности
private int mIncydencji[][]; //macierz incydencji
private boolean digraf=false; //jesli graf true
private int n; //kolvo wiershin w grafie
private ArrayList<Integer> rem = new ArrayList<Integer>(); // spisok udalionnyh vershin
private boolean odwiedzone[];

public Graf()
{
mSasiedztwa = new int[1][1];
for(int k=0; k<n; ++k)
{
mSasiedztwa[k] = new int[1];
}
for(int i=0; i<mSasiedztwa.length; ++i)
{
for(int j=0; j<mSasiedztwa.length; ++j)
{
mSasiedztwa[i][j]=0;
}
}
}

public void nowyGraf(int n)
{

mSasiedztwa = new int[n][n];
digraf=false;
this.n=n;
rem = new ArrayList<Integer>();

for(int k=0; k<n; ++k)
{
mSasiedztwa[k] = new int[n];
}
for(int i=0; i<mSasiedztwa.length; ++i)
{
for(int j=0; j<mSasiedztwa.length; ++j)
{
mSasiedztwa[i][j]=0;
}
}
}

public void nowyDigraf(int n)
{
mSasiedztwa = new int[n][n];
this.n=n;
digraf=true;

rem = new ArrayList<Integer>();

for(int k=0; k<n; ++k)
{
mSasiedztwa[k] = new int[n];
}
for(int i=0; i<mSasiedztwa.length; ++i)
{
for(int j=0; j<mSasiedztwa.length; ++j)
{
mSasiedztwa[i][j]=0;
}
}
}

public void DigraftoGraf()
{
if (digraf==true){
digraf=false;
}
}

public int nieodwiedzony(int a) //не посещённая вершина
{
for(int k=0; k<n; ++k)
{
if(mSasiedztwa[a][k] > 0 && a != k && odwiedzone[k]==false)
{
return k;
}
}
return -1;
}

public boolean czyOdwiedzone() //посещена ли вершина
{
for(int k=0; k<n; ++k)
{
if(odwiedzone[k]==false)
{
return false;
}
}
return true;
}

public int jeszczeNieodwiedzony() //ещё не посещена
{
for(int k=0; k<n; ++k)
{
if(odwiedzone[k]==false)
{
return k;
}

}
return -1;
}

[Annabel]

public void wypiszMacierzSasiedztwa() //выписать матрицу смежности
{
System.out.print("Macierz sasiedztwa" + '\n');
System.out.print(" ");
for (int i=0; i<mSasiedztwa.length; ++i)
{
if(!rem.contains(i))
System.out.print((i+1) + " ");
}
System.out.print(" " + '\n');

for (int i=0; i<mSasiedztwa.length; ++i)
{
if(!rem.contains(i))
{

for (int j=-1; j<mSasiedztwa.length; ++j)
{
if (j == -1) System.out.print((i+1) + " ");
else if(!rem.contains(j))

System.out.print(mSasiedztwa[i][j] + " ");
}
System.out.print(" "+ '\n');

}
}
System.out.print(" "+ '\n');
}






public void usunWierzcholek(int w) //удаляет вершину
{
if(w <= 0 || w > this.n || rem.contains(w-1))
{
System.out.println("Oshibka. net takoj vershiny");
return;
}
rem.add(w-1);
for(int i=0; i<n; ++i)
{
mSasiedztwa[w-1][i]=0;
mSasiedztwa[i][w-1]=0;
}
System.out.println("Vershina udalena");
}

public void dodajKrawedz(int a, int b)
{
if(a <= 0 || a > this.n || b <= 0 || b > this.n || rem.contains(a-1) || rem.contains(b-1))
{
System.out.println("Oshibka");
return;
}
if(a==b)
{
mSasiedztwa[a-1][a-1]+=2;
}
else
{
mSasiedztwa[a-1][b-1]+=1;
if(!digraf)
mSasiedztwa[b-1][a-1]+=1;
}
System.out.println("Rebro dobavleno");
}

public void wypiszListe() //выписывай список
{
int ile;
if(!digraf) {
System.out.print("Lista sasiedztwa:" + '\n');
for (int i=0; i<mSasiedztwa.length; ++i)
{
if(!rem.contains(i))
{
System.out.print((i+1) + ": ");
for (int j=0; j<mSasiedztwa.length; ++j)
{
if(!rem.contains(j))
{
if(i==j)
ile=(mSasiedztwa[i][j])/2;
else
ile=mSasiedztwa[i][j];
while(ile>0)
{
System.out.print((j+1) + " ");
--ile;
}
}
}
System.out.print(" " + '\n');

}
}
System.out.print(" " + '\n');
}

if(digraf)
{
System.out.print("Lista nastepnikow: " + '\n');
for (int i=0; i<mSasiedztwa.length; ++i)
{
if(!rem.contains(i))
{
System.out.print((i+1) + ": ");
for (int j=0; j<mSasiedztwa.length; ++j)
{
if(!rem.contains(j))
{
if(i==j)
ile=(mSasiedztwa[i][j])/2;
else
ile=mSasiedztwa[i][j];
while(ile>0)
{
System.out.print((j+1) + " ");
--ile;
}
}
}
System.out.print(" " + '\n');

}
}
System.out.print(" " + '\n');
System.out.print("Lista poprzednikow: " + '\n');
for (int i=0; i<mSasiedztwa.length; ++i)
{
if(!rem.contains(i))
{
System.out.print((i+1) + ": ");
for (int j=0; j<mSasiedztwa.length; ++j)
{
if(!rem.contains(j))
{
if(i==j)
ile=(mSasiedztwa[j][i])/2;
else
ile=mSasiedztwa[j][i];
while(ile>0)
{
System.out.print((j+1) + " ");
--ile;
}
}
}
System.out.print(" " + '\n');
}
}
System.out.print(" " + '\n');
}
}

[Annabel]

public void wypiszMacierzIncydencji()
{
int ile=0; //obliczenie ilosci krawedzi
int ak = 0; //aktualna kolumna
System.out.print("Macierz incydencji: " + '\n');
if(digraf==false) //jesli graf ma wartosc true
{

for(int i=0; i<mSasiedztwa.length; ++i)
{
for(int j=i; j<mSasiedztwa.length; ++j)
{
if(i!=j) ile+=mSasiedztwa[i][j];
else ile+=(mSasiedztwa[i][j])/2;
}
}

}else //jesli digraf true
{
for(int i=0; i<mSasiedztwa.length; ++i)
{
for(int j=0; j<mSasiedztwa.length; ++j)
{
if(i!=j) ile+=mSasiedztwa[i][j];
else ile+=(mSasiedztwa[i][j])/2;
}
}
}

mIncydencji = new int[n][ile];
for(int k=0; k<n; ++k)
{
mIncydencji[k] = new int[ile];
}

if (digraf ==false)
{

for(int i=0; i<mSasiedztwa.length; ++i)
{
for(int j=i; j<mSasiedztwa.length; ++j)
{
if(i!=j)
{
int k=mSasiedztwa[i][j];
while(k>0)
{
mIncydencji[i][ak]=1;
mIncydencji[j][ak]=1;
++ak;
--k;
}
}
if(i==j)
{
int k=(mSasiedztwa[i][j])/2;
while(k>0)
{
mIncydencji[i][ak]=2;
++ak;
--k;
}
}

}
}

//выписывает
System.out.print(" ");
for(int i=0; i<ile; ++i)
{
System.out.print("(");
for(int j=0; j<n; ++j)
{

if(mIncydencji[j][i]==1)
{
System.out.print((j+1));
}
if(mIncydencji[j][i]==2)
{
System.out.print((j+1) + "" + (j+1));
}
}
System.out.print(") ");
}
System.out.print("" + '\n');

for(int i=0; i<n; ++i)
{
for (int j=-1; j<ile; ++j)
{
if(!rem.contains(i)) {

if(j == -1) System.out.print((i+1) + "");
else
System.out.print("" + " " + mIncydencji[i][j] + " ");
}
}
if(!rem.contains(i)) {
System.out.print("" + '\n');
}
}

}

if(digraf == true)
{
for(int i=0; i<mSasiedztwa.length; ++i)
{
for(int j=0; j<mSasiedztwa.length; ++j)
{
if(i!=j)
{
int k=mSasiedztwa[i][j];
while(k>0)
{
mIncydencji[i][ak]=-1;
mIncydencji[j][ak]=1;
++ak;
--k;
}
}
if(i==j)
{
int k=(mSasiedztwa[i][j])/2;
while(k>0)
{
mIncydencji[i][ak]=2;
++ak;
--k;
}
}

}
}

//выписывает
System.out.print(" ");
int wch=0;
int wych=0;
for(int i=0; i<ile; ++i)
{
System.out.print("(");
for(int j=0; j<n; ++j)
{

if(mIncydencji[j][i]==1)
{
wch = j+1;
}
if(mIncydencji[j][i]==(-1))
{
wych = j+1;
}

if(mIncydencji[j][i]==2)
{
wch = j+1;
wych = j+1;
}

}

System.out.print(wych + "" + wch + ") ");
}
System.out.print("" + '\n');

for(int i=0; i<n; ++i)
{
for (int j=-1; j<ile; ++j)
{
if(!rem.contains(i)) {

if(j == -1) System.out.print((i+1) + "");
else
if(mIncydencji[i][j]==-1)
{
System.out.print("" + " " + mIncydencji[i][j] + " ");
}
else
{
System.out.print("" + " " + mIncydencji[i][j] + " ");
}
}
}
if(!rem.contains(i)) {
System.out.print("" + '\n');
}
}
}
}

[Annabel]

public void wglab() //поиск в глубину
{
int a = 0;
Stack<Integer> stos = new Stack<Integer>();
String message="";
odwiedzone = new boolean[n];
for(int k=0; k<n; ++k)
{
odwiedzone[k] = false;
}
boolean czyPierwszy = true;
System.out.println();
System.out.println("przeszukiwanie w glab : ");

while(!czyOdwiedzone())
{
stos = new Stack<Integer>();
if(czyPierwszy==true) {
czyPierwszy=false;
if (digraf==false) {
message = '\n' + "graf jest spojny";
}else {
message = '\n' + "digraf jest silnie spojny";
}
}else {
a=jeszczeNieodwiedzony();
if (digraf==false){
message = '\n' + "graf jest niespojny";
}else {
message = '\n' + "digraf nie jest silnie spojny";
}

}
odwiedzone[a]=true;


stos.push(a);
if(nieodwiedzony(a) == -1) {
System.out.print((a+1) + " ");
}

while(!stos.empty())
{
a = stos.peek();
int b= nieodwiedzony(a);
if (b == -1)
{
stos.pop();
}
else
{
stos.push(b);
odwiedzone[b]=true;
System.out.print("(" + (a+1) + ", " + (b+1) + ") ");
}
}
System.out.println();
}

System.out.println(message + '\n');
}



public void wszerz() //поиск в ширину
{
int a = 0;
LinkedList<Integer> kolejka = new LinkedList<Integer>();
String komunikat="";
odwiedzone = new boolean[n];
for(int k=0; k<n; ++k)
{
odwiedzone[k] = false;
}
System.out.println();
System.out.println("przeszukiwanie wszerz: ");
boolean czyPierwszy = true;

while(!czyOdwiedzone())//jesli nie wszystkie odwiedzone wywolanie przeszukiwania ponownie
{
kolejka = new LinkedList<Integer>();
if(czyPierwszy==true) {
czyPierwszy=false;

}else {
a=jeszczeNieodwiedzony();
}
odwiedzone[a]=true;

kolejka.addLast(a);
if(nieodwiedzony(a) == -1) {
System.out.print((a+1) + " ");

}

while(!kolejka.isEmpty())
{
a = kolejka.removeFirst();
int b;

while ((b = nieodwiedzony(a)) != -1)
{
kolejka.addLast(b);
odwiedzone[b]=true;

System.out.print("(" + (a+1) + ", " + (b+1) + ") ");
}
}
System.out.println();

}
}





public void wypiszWszystko() //выписывай всё
{
wypiszMacierzSasiedztwa();
wypiszListe();
wypiszMacierzIncydencji();
}

public void przeszukaj() //поиск
{
wglab();
wszerz();

}


}