Graph (Graph)
What is the graph? (What is a graph)
Diagrams simulate a set of links.
A graph models a set of connections.
A Graph consists of nodes and edges.
A node may be directly connected to multiple nodes, called neighbors.
A node can be directly connected to many other nodes. Those nodes are called its neighbors.
Graphs are a way to model how different things are connected to one another.
Directed graph: The directed relationship in a graph, represented by an arrow, in which the relationship is one-way.
Undirected graph: A graph in which a relationship is represented by no arrows and directly connected nodes are neighbors of each other
Realize the figure
A diagram consists of multiple nodes. Each node is connected to a neighboring node. How do you represent a relationship like “you -> Bob”? We can do this using hash tables, because hash tables map keys to values.
Our lines First Search
Breadth-first search is a search algorithm for graphs.
Can help solve two broad categories of problems
- Is there A path from node A to node B?
- What is the shortest way from node A to node B? (the shortest – path – problem)
Here’s an example:
You -> your friend -> your friend’s friend
Here you can find your friends directly, called degree relationships. Friends of friends need you to go through friends to find what’s called a second degree relationship, and so on.
We need to find the first degree relationship and then find the second degree relationship, check in order, usually with queue, such as FIFO data structure to achieve.
Implementation approach
- Use queues to maintain the relationship between checks by degrees
- Flags cleared elements to prevent an endless loop
- Until I find something
Time complexity
O(V + E), where V is the vertice number and E is the edge number.