What is the difference (if any) between a node and a vertex? I can't find the answer after looking at countless sites! Even my book doesn't specify it so I am kind of lost!
It is worth mentioning that I am looking for the difference besides the fact that it is called a 'vertex' when used in a graph and a 'node' when used in a tree.
There are no differences between the words Node and Vertex. Even in some books that explain graph theory and graph algorithms they name it as:
Vertex denoted by v, and sometimes it's called nodes also
There are no major nor minor differences between them.
This is mentioned in the book: Data structure and Algorithms with Object Oriented Design Patterns in C#, Bruno R, Preiss.
In "The Practitioner's Guide to Graph Data", the author avoid the term "node/nodes" and only use vertex/vertices and they explain it as below:
...because we are focusing on distributed graphs, and nodes has different meanings in distributed systems, graph theory and computer science.
In distributed systems, a node can be a client, server or peer, while in computer network it can be a computer or a modem. In computer science, as you already point out, it could be used either for graph theory or tree system.
So in the context of graph theory, node and vertex are used interchangeable. But if you would like to make it clear and avoid any misunderstanding, vertex/vertices is the way to go.
In think both terminologies come from the different perception of graphs and networks. Albert-László Barabási writes in his recent text book.
"In the scientific literature the terms network and graph are used interchangeably:
| Network science | Graph theory |
|---|---|
| Network | Graph |
| Node | Vertex |
| Link | Edge |
Yet, there is a subtle distinction between the two terminologies: the {network, node, link} combination often refers to real systems: The WWW is a network of web documents linked by URLs; society is a network of individuals linked by family, friendship or professional ties; the metabolic network is the sum of all chemical reactions that take place in a cell. In contrast, we use the terms {graph, vertex, edge} when we discuss the mathematical representation of these networks: We talk about the web graph, the social graph (a term made popular by Facebook), or the metabolic graph. Yet, this distinction is rarely made, so these two terminologies are often synonyms of each other."
<tl;dr> Same, same, but different.
There is no difference between a node and a vertex. Most books use V to represent the vertex of a graph. I've seen node mostly associated with a tree.
For instance, you may have come across O(V + E) being used to represent the time complexity for depth first search and breadth first search graph traversals.
Similarly, V is used as part of time complexity analysis for other graph algorithms like Prim's, Kruskal's, etc.
