What is a graph?
A graph is a mathematical structure consisting of vertices (nodes) and edges that connect these vertices. Graphs can be used to represent relationships between objects, for example in social networks or traffic networks. They are a central concept in graph theory and are used in many areas of computer science and mathematics.
What does it mean to traverse a graph?
To traverse a graph means to systematically visit all the vertices of the graph to gather information or perform a specific task. This can be done by various algorithms, such as depth search or width search. Traversing is crucial for applications such as finding the shortest paths or browsing networks.
And that's exactly what you can understand with the small app for Swift Playgrounds (Mac or iPad).
Draw a graph
New vertices are drawn by clicking anywhere in the green field. With a click on a vertex it is marked, with a click on another node an edge is drawn. The options on the buttons can also be applied to this vertex.
Traversing the graph
By clicking on a 'visible' vertex, it is visited (connected by an orange edge). The 'Reachable vertices' list displays all 'visible' vertices. If the list is empty, the graph has been completely traversed, or the graph is not contiguous.
Traversing the graph by width search
Width search is an algorithm that searches nodes in a graph or tree layer by layer, starting at a starting vertex. All direct neighbors are first examined before moving on to the more distant nodes. The width search is performed in the app when the 'Reachable vertices' list is always processed from the top (the vertex to visit is always read at the top of the list).
Crossing a graph by depth search
Depth search is an algorithm that explores a graph by going as deep as possible in one direction before returning and exploring other paths. It is often used to find paths, recognize cycles, or completely traverse structures. The deep search is performed in the app if the 'Reachable vertices' list is always processed from the bottom (the vertex to be visited is always read at the bottom of the list).
Leave a Reply