4.1.8.3 Operations on Graphs
Computational Structures
Graphs support various operations to manipulate and explore their structure. Here are some essential operations:
- Insertion: Adding a new vertex or edge to the graph.
- Example: If a new city is added to the transport map, it introduces a new vertex and possibly new edges.
- Deletion: Removing a vertex or edge from the graph.
- Example: If a city is removed from the map, its corresponding vertex and all edges connected to it are deleted.
- Traversal: Visiting all vertices and edges systematically. Traversal can be done using different functions:
- Breadth-First Search (BFS): This technique starts from a source vertex and explores all its immediate neighbors before moving to the next level of vertices. Example: Imagine you are at a central train station in a city, and you want to visit all the nearby neighborhoods. First, you would take the trains that directly connect to the central station and explore all the neighborhoods they reach. Once you have visited all these neighboring areas, you then move to the next set of neighborhoods that are directly connected to the previously visited ones. This process continues until you have explored all reachable neighborhoods from the central station.
- Depth-First Search (DFS)