Graph: Difference between revisions

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:

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.


https://www.youtube.com/watch?v=zaBhtODEL0w

@@ 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.
@@ Line 5: / Line 7: @@
 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 ==
 {| class="wikitable"
 !