AI Hints
DSA in Python · Lesson 76 of 132

Graphs

Nodes and edges.

⏱ 2 min read▶ Video at 1:29:42🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

A graph is a set of things, called nodes, connected by links, called edges. Cities connected by roads. People connected by friendships. Web pages connected by links. Graphs are the most flexible data structure of all. Trees and linked lists are just special kinds of graph.

Graphs
From the video: Graphs
  • Nodes connected by edges
  • Cities, friends, web pages
  • Trees are graphs too

Kinds of graph

Edges can be two way, like friendships, which makes an undirected graph. Or one way, like following someone, which makes a directed graph. Edges can carry weights, like the distance of a road. And a graph can contain cycles, paths that loop back to where they started.

Undirectedtwo way, friendships
Directedone way, follows
Weighteddistances, costs
Cyclespaths that loop

Graph problems

Graphs answer questions that other structures can't. Is there a path from here to there? What's the shortest route? Which groups of people are connected? Which task must be done first? Over the next lessons, we'll answer every one of these.

Reachable?is there a path
Shortest pathmaps, networks
Groupsconnected parts
Orderingwhich task first

Summary

A graph is nodes connected by edges, directed or undirected, weighted or not. Next, how to store a graph in Python.

Key takeaways
  • Nodes and edges
  • Directed or undirected
  • Weighted or not
Next up: Storing a Graph — adjacency lists