Graph: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
A graph is a collection of nodes. | A graph is a collection of nodes (also called vertices). | ||
A graph is connected if there is a path between every distinct nodes. | |||
Each node might point to another node. The edge can be directed or undirected. | Each node might point to another node. The edge can be directed or undirected. | ||
| Line 5: | Line 7: | ||
Typical questions we can ask about a graph: | Typical questions we can ask about a graph: | ||
* Is there a path from one node to another? | * Is there a path from one node to another? | ||
There are two ways to represent a graph: | |||
* Adjacency List: every node stores a list of adjacent nodes | |||
** Use in BFS algorithm | |||
* Adjacency Matrix: | |||
** N x N matrix where N is the number of nodes, and where matrix[i][j] is 1 iff node i and node j are connected | |||
** Undirected graph has symmetric adjacency matrix. | |||
== Resources == | == Resources == | ||
Latest revision as of 00:15, 23 October 2020
A graph is a collection of nodes (also called vertices).
A graph is connected if there is a path between every distinct nodes.
Each node might point to another node. The edge can be directed or undirected.
Typical questions we can ask about a graph:
- Is there a path from one node to another?
There are two ways to represent a graph:
- Adjacency List: every node stores a list of adjacent nodes
- Use in BFS algorithm
- Adjacency Matrix:
- N x N matrix where N is the number of nodes, and where matrix[i][j] is 1 iff node i and node j are connected
- Undirected graph has symmetric adjacency matrix.
Resources
| https://www.youtube.com/watch?v=zaBhtODEL0w |