Алгоритмы на графах
Представление графа
1.Массива ребер
2.Матрицы смежности
3.Списка смежных вершин
13
Алгоритмы на графах
Массив ребер
class Rebro { int i, j;
Rebro(int x, int y) { i = x; j = y; } public boolean equals(Object o) {
return ((i==((Rebro)o).i) && (j==((Rebro)o).j));
}
}
interface Graf { int getV(); int getR();
boolean getDir(); boolean inst(Rebro r); boolean del(Rebro r); boolean find(int x, int y);
}
14
Алгоритмы на графах
class GrafMas implements Graf { private Rebro mas[];
private boolean orient; private int Ver, Reb; GrafMas(int V, boolean or) {
Ver = V;
mas = new Rebro[V*(V-1)/2]; orient = or;
} |
|
|
|
public int getV() { |
return Ver; |
} |
|
public int getR() { |
return Reb; |
} |
|
public boolean getDir() { |
return orient; } |
||
15
Алгоритмы на графах
public boolean inst(Rebro r) { for(int k=0; k<Reb; k++)
if (mas[k].equals(r)) return false; mas[Reb++] = r;
return true;
}
public boolean del(Rebro r) { for(int k=0; k<Reb; k++)
if (mas[k].equals(r)) {
for(int m=k; m<(Reb-1); m++) mas[m] = mas[m+1];
mas[--Reb] = null; return true;
}
return false; }
16