Алгоритмы на графах
public boolean find(int x, int y) { for (int k=0; k<Reb; k++)
if ((x==mas[k].i) && (y==mas[k].j)) return true; return false;
}
void show() {
for(int k=0; k<Ver; k++) { System.out.print("\n"+k+": "); for(int m=0; m<Reb; m++)
if(mas[m].i == k) System.out.print(mas[m].j+" ");
}
}
}
17
Алгоритмы на графах
Enter number vershin -> 5 Add rebro? (Yes - y, No - n) y Enter value vershin rebra -> 0 4 Add rebro? (Yes - y, No - n) y Enter value vershin rebra -> 0 3 Add rebro? (Yes - y, No - n) y Enter value vershin rebra -> 2 4 Add rebro? (Yes - y, No - n) y Enter value vershin rebra -> 1 2 Add rebro? (Yes - y, No - n) y Enter value vershin rebra -> 2 3 Add rebro? (Yes - y, No - n) y Enter value vershin rebra -> 2 4 Add rebro? (Yes - y, No - n) n
Graf:
0:4 3
1:2
2:4 3
Delete rebro? (Yes - y, No - n) y Enter value vershin rebra -> 0 4 Delete rebro? (Yes - y, No - n) n Graf after delete:
0:3
1:2
2:4 3
Enter rebro for find? (Yes - y, No - n) y Enter value vershin -> 3 4
Rebro no find!
18
Алгоритмы на графах
Матрица смежности
Матрица смежности – это матрица логических значений размерности V (V – количество вершин), элемент которой
на пересечении i-й строки и j-го столбца устанавливается |
||||||||||
в true, если в графе имеется ребро, соединяющее i-ю |
||||||||||
вершину с j-й вершиной. |
|
|
|
|
0 |
|||||
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
|
|
|
|
|
|
3 |
||||||
|
|
|||||||||
0 |
|
0 |
1 |
1 |
0 |
0 |
1 |
1 |
4 |
|
1 |
|
1 |
0 |
0 |
0 |
0 |
0 |
|||
|
|
|
||||||||
2 |
|
1 |
0 |
0 |
0 |
0 |
0 |
|
2 |
|
3 |
|
0 |
0 |
0 |
0 |
1 |
1 |
|
5 |
|
|
|
|
||||||||
4 |
|
0 |
0 |
0 |
1 |
0 |
1 |
|
|
|
5 |
|
1 |
0 |
0 |
1 |
1 |
0 |
|
19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Алгоритмы на графах |
|
class GrafSmeg implements Graf { |
|
||
private int Ver, Reb; |
private boolean orient; boolean mas[][]; |
||
GrafSmeg(int V, boolean or) { |
|
||
Ver = V; |
orient = or; mas = new boolean [V][]; |
||
for(int k=0; k<V; k++) |
|
||
mas[k] = new boolean[V]; |
|
||
} |
|
|
|
public int getV() { |
return Ver; |
} |
|
public int getR() { |
return Reb; |
} |
|
public boolean getDir() { return orient; } |
|||
public void inst(Rebro r) { |
|
||
int s = r.i, |
e = r.j; |
|
|
if (mas[s][e] == false) Reb++; |
|
||
mas[s][e] = true; |
|
|
|
if (!orient) |
mas[e][s] = true; |
|
|
} |
|
|
20 |