A lot of information is sourced from Graphs Computer Science

A graph is a set of nodes/vertices connected by edges/pointers.

There are three types of graphs:

• Directed Graph: The edges can only be traversed in the permitted direction
• Undirected Graph: The edges can be traversed in both directions
• Weighted Graph: The edges have weights attached

Storage

Graphs may be stored as either an adjacency matrix or an adjacency list.

Adjacency Matrix

A 2D array which stores edge relationships.

Example

N = -1 # represents none
adjacencies = [ # weighted - int, unweighted could just be 0/1
	# A  B  C
	[ N, 2, 9 ], # A
	[ 2, N, 7 ], # B
	[ 9, 7, N ]  # C 
]

# access weight of B->A
print("B->A edge weight: " + str(adjacencies[1][0]))

Adjacency List

A list/dictionary which stores edge relations.

adjacencies = { # unweighted
	"A": ["B", "C"],
	"B": ["C", "D"],
	"C": ["A", "B"],
	"D": ["B"]
}

# access C edges
print("C edges:")
for adjacency in adjacencies["C"]:
	print(adjacency)