DEV Community

A Gentle Introduction To Graph Theory

Vaidehi Joshi on March 21, 2017

So many things in the world would have never come into existence if there hadn’t been a problem that needed solving. This truth applies to everyt...
Collapse
 
fannyvieira profile image
Fanny

💜💜

Collapse
 
jpenuchot profile image
Jules Pénuchot

Graphs, Grammars, Lexing etc. are fundamental to computer science, nobody should go without at least knowing the basics about these, but still there are only few articles about theoretical computer science on dev related websites, but yours are just so nice ! Great job

Collapse
 
annarankin profile image
Anna Rankin

This is wonderful! Thank you so much for putting this together - I wish I'd known about this resource when I first started trying to learn about graphs. Great work breaking it down and making it more accessible!!

Collapse
 
pingsoli profile image
pingsoli

nice post, impressive. Thanks a lot.

Collapse
 
aodev profile image
AoDev

It's nice to have mentioned the mathematics origin to explain graph. Many students get no explanation about why they have to "eat" a lot of mathematics when learning computer science. Unless the teachers are good, they won't describe the "from math to computer science" story making it less likely to trigger interest for the mathematics courses. It's common for students to drop university when they see they do math instead of computer science.

Collapse
 
dartdog profile image
Tom Brander

Excellent and very helpful but one thing I don't get, for instance in Python how would one define the order graph as distinct from the un-ordered notation, you seem to indicate the same notation? Surely there is some difference in code representation between order and unorder?

Collapse
 
artyom profile image
Artyom Yakovenko

Maybe using lists and tuples? And then it's just a matter of interpretation, whether you treat your structures as those representing a directed or undirected graph.

Collapse
 
maribelduran profile image
Maribel Duran

I loved this so much! Keep writing!

Collapse
 
vaidehijoshi profile image
Vaidehi Joshi

I'm glad you liked it!!

Collapse
 
watarilog profile image
Paul Guss

Nicely written.

I am new to the topic, introduced to me as a solution to the classic puzzle Instant Insanity. I have some problems with the terminology used, particularly the terms "vertices" and "edges" (I like much better your terms, nodes and links). A vertex by definition is a point where two or more lines meet to form an angle. However, some of the "vertices" in the graphs you've described (for example, Liz in the Facebook graph) are isolated, having only one line linked to them. How is this a vertex?

Also, I am confused about the term "edges". What makes it an edge (the outer or farthest point of something)?

I am sure there must be some reason why these terms were chosen. They have cropped up in other articles I've read too.

Would appreciate whatever insight you might be able to offer.

Collapse
 
courier10pt profile image
Bob van Hoove

Thanks for writing this, you've done a great job (re-)educating me about the fundamentals.

I'm interested in using (or perhaps even implementing) an in memory graph for a music selection program. I use C#, recommendations are welcome.

Oh and I have considered Neo4j, it's great but I'd like something more light weight.

Collapse
 
alexmm2 profile image
Alexander Mayorga M.

Thank you. 🌹🌹🌹🌼🌼🌷

Collapse
 
can_atac profile image
ATAC Jan

Really nice course. We want more !!

Collapse
 
hjoaco profile image
Hector J. Medina

Magnifico!!

Collapse
 
jeansberg profile image
Jens Genberg

Very helpful and well explained!

Collapse
 
artyom profile image
Artyom Yakovenko

Great article! Thank you!

Collapse
 
robdwaller profile image
Rob Waller

Really interesting post.

Collapse
 
umoqnier profile image
Diego Alberto Barriga Martínez

Thanks for this article. I learned a lot :D

Collapse
 
debdeepg profile image
Debdeep Ganguly • Edited

Comparing Facebook to an undirected graph and Twitter to a directional one sounds confusing. Nice article though!

Collapse
 
vaidehijoshi profile image
Vaidehi Joshi

Social networks are a pretty standard example of graphs (if you take a look at some CS curricula, you'll notice they come up again and again as widely-used examples).

Facebook or LinkedIn are both examples an undirected graph as "friendships" work two-ways. But on Twitter or Google+, the concept of "followers" rather than "friendships" make these graphs directed, and not bidirectional.

Hope this clears that up.