Graphs Flashcards
What is a graph?
A graph is a data structure made up of nodes and possibly pointers connecting them together.
How many edges can a graph have?
The number of edges, E, given the number of vertices V will always be less than or equal to V^2. E<=V^2. This is because each node can at most point to itself, and every other node in the graph.
What are the ways of representing a graph?
Matrix
Adjacency Matrix
Adjacency List
Matrix representation of a graph
The elements in the grid are vertices. To traverse a graph, we are allowed to move up, down, left and right. If we are to connect the 0s together, using our edges, we would end up getting a bunch of connected zeroes, which are connected components, and that denotes a graph.
Adjacency matrix representation of a graph
The indicies of the matrix (row and col nums) represent verticies. If there is a 1 in the element, it means there is an edge between the two verticies.
an edge exists from v1 to v2
adjMatrix[v1][v2] = 1
an edge exists from v2 to v1
adjMatrix[v2][v1] = 1
No edge exists from v1 to v2
adjMatrix[v1][v2] = 0
No edge exists from v2 to v1
adjMatrix[v2][v1] = 0
Adjacency list representation of a graph
Vertices are represented by node objects, which store a list of its neighbors.
GraphNode used for adjacency list
class GraphNode:
def __init__(self, val):
self.val = val
self.neighbors = []
How to find the shortest path in a graph?
Use BFS
