Алгоритмы на графах
public void del(Rebro r) { int s=r.i, e=r.j;
if (mas[s][e] == true) Reb--; mas[s][e] = false;
if (!orient) mas[e][s] = false;
}
public boolean find(int x, int y) { return mas[x][y];
}
void show() {
for(int s=0; s<Ver; s++) { System.out.print("\n"+s+": "); IterM A = new IterM(this, s);
for (int p=A.beg(); !A.end(); p=A.next()) System.out.print(p+" ");
}
}
}
21
|
Алгоритмы на графах |
|
|
class IterM { |
|
|
|
GrafSmeg gg; int k; int v; |
|
|
|
IterM(GrafSmeg obj, int ver) { |
gg = obj; |
v = ver; } |
|
public int beg() { |
k = -1; return next(); |
} |
|
public int next() { |
|
|
|
for(k++; k<gg.getV(); k++) |
|
|
|
if (gg.mas[v][k] == true) |
return k; |
|
|
return -1; |
|
|
|
} |
|
|
|
public boolean end() { |
|
|
|
return (k >= gg.getV()); |
|
|
|
} |
|
|
|
} |
|
|
|
22
Алгоритмы на графах
Enter number vershin -> 5 Add rebro? (Yes - y, No - n) y Enter value vershin rebra -> 0 1 Add rebro? (Yes - y, No - n) y Enter value vershin rebra -> 0 2 Add rebro? (Yes - y, No - n) y Enter value vershin rebra -> 1 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 3 Add rebro? (Yes - y, No - n) n
Graf: 0: 1 2 1: 0 3 2: 0 4 3: 1 4: 2
Delete rebro? (Yes - y, No - n) y Enter value vershin rebra -> 0 1 Delete rebro? (Yes - y, No - n) n Graf after delete:
0: 2 1: 3 2: 0 4 3: 1 4: 2
Enter rebro for find? (Yes - y, No - n) y |
|
Enter value vershin -> 3 2 |
23 |
Rebro no find! |
Алгоритмы на графах
Список смежных вершин
Представляет собой одномерный массив ссылок на однонаправленные списки, где индекс элемента массива является вершиной, а список, связанный с каждой вершиной, определяет смежные ей вершины.
0 |
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
0 |
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
5 |
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
2 |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
5 |
|
|
|
|
3 |
|
|
|
|
|
|
|
0 |
|
|
|
|
|
4 |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0
1 2
3
5 4
24