Graph Search Flashcards
Undirected Graph vs Directed
Directed graphs have arrows.
Tree Graph aka Acyclic
Undirected graph that is connected and has no cycles. If it had cycles it would be a graph.
Rooted Tree
This has one vertex that is distinguished and it’s nodes are called leaves.
Connected Components
In a graph that is not connected.
Forests
Undirected. The connected compontents in a forest are trees. Forests don’t have cycles.
Spanning Tree
Applications to the design of communication networks They’re a spanning subgraph that is a tree. They connect all the vertices with a minimum number of edges.
Paths
A sequence of nodes with a start point and end-point.
Pathfinding
Could be more than one path from one node to the other. Path length is of interest and finding the shortest one is a common graph operation.
These operations will find paths from one node to another by traversing:
BFS - Breadth first search
DFS - Depth first search
The algorithm will find all the paths.
Cycles
Cycles in a graph are paths from a node back to itself and must be avoided when traversing a graph as it will be in a constant loop.
Breadth-first Search
This is useful for finding the shortest path on an unweighted graph. It first creates an empty queue.
BFS starts with a node and explores the neighbour nodes first. (It explores nodes in layers).
It does this by maintaining queues of which nodes to visit next.
BFS Runtime Complexity?
BFS on a graph with n vertices and m edges takes O(N+m) time.
The queue process of BFS
First node goes into a queue. The neighbours of this node are put into the queue. These are then searched for their neighbours which are then added to the queue. When a node is found to have no neighbours it is removed from the queue.
DFS
This isn’t useful alone. This is useful for counting connected components, determining connectivity, and finding bridges and articulation points.
DFS is good for a single solution such as a maze (backtracking etc). It’s harder than BFS to parallellise. Uses a stack rather than a queue like BFS.
Weighted Graphs
Graphs that have weight on their edges. They can represent costs and distances etc. You can find the total weight of the graph by using these weights.
Minimum Spanning Tree
Finding the minimum weight for a tree.
