34 lines
961 B
Markdown
34 lines
961 B
Markdown
# Graphen
|
|
|
|
## Graph-Klasse
|
|
|
|
Wir wollen hier einen Graphen modellieren, Graphen kennt ihr bereits als Bäume. Diese sind spezielle Graphen welche eine Wurzel haben, also den ersten Knoten. Und dann immer maximal zwei weitere Knoten (**left** und **right**). Die letzten Knoten nennt man auch Blätter. Allgemeine Graphen hingegen kann jeder Knoten auf beliebig viele weitere Knoten verweisen. Diese Verweise nennt man Kanten.
|
|
|
|
Unsere **Graph** Klasse modellieren wir etwas anders mit einem `dict` welcher immer einen Knoten auf eine Liste von weiteren Knoten mappt.
|
|
|
|
```python
|
|
from dataclasses import dataclass, field
|
|
|
|
|
|
@dataclass
|
|
class Graph[T]:
|
|
vertecies: dict[T, list[T]] = field(default_factory=dict)
|
|
```
|
|
|
|
Als Beispiel:
|
|
|
|
|
|
|
|
würde dann im Code so aussehen:
|
|
|
|
```python
|
|
|
|
my_graph: Graph[str] = Graph(
|
|
vertecies={
|
|
'A': ['B', 'D'],
|
|
'B': ['A', 'C'],
|
|
'C': ['B', 'D'],
|
|
'D': ['C', 'A'],
|
|
})
|
|
|
|
``` |