-
Notifications
You must be signed in to change notification settings - Fork 0
DS: Graphs
-
A graph is a collection of nodes (or vertices) connected by edges (or links), representing relationships between data elements.
-
There are eighteen types of graphs: Directed, Undirected, Null, Simple, Trivial, Complete, Cyclic, Acyclic, Connected, Disconnected, Regular, Finite, Infinite, Pseudo, Bipartite, Planar, Multi, & Euler.
-
A loop is an edge that starts and ends at the same node.
-
A multiple edge is an edge that exists more than once between the same two nodes.
-
A cycle occurs when a node can make it back to itself via traveling through the edges and starting from itself.
-
The degree of a node is equal to the number of edges it has.
-
A trail is a path in a graph where no edge is repeated, but vertices can repeat.
-
A circuit is a trail that starts and ends at the same node.
-
An open path is a path that starts and ends at different vertices, and no edge or node is repeated.
-
A closed path is a path that starts and ends at the same node, with no edge or node repeated, except the first and last node.
-
An Eulerian path in a graph is a path that traverses each edge exactly once.
-
A Eulerian circuit is a circuit that visits every edge in the graph.
- Directed graphs are graphs where the edges have direction to them; i.e one node may point to another, but that node won't necessarily point back.
- Undirected graphs, opposite of directed graphs, are graphs where the edges have no direction to them; i.e each edge represents a two-way relationship between both the nodes it connects.
- Null graphs are graphs that contain no edges. In other words, all the nodes, if any, in a null-graph are disconnected from each other.
- Simple graphs are simply those with no loops and no multiple edges.
- Trivial graphs are graphs that contain one node and zero edges.
- Complete graphs are undirected graphs in which each pair of nodes are connected to each other.
- Cyclic graphs are graphs that contains at-least a single cycle.
- Acyclic graphs, opposite of cycle graphs, are graphs that contain zero cycles.
- Connected graphs are graphs where a path(can be indirect or direct) exists between each pair of nodes.
- Disconnected graphs are the opposite of connected graphs.
- Regular graphs are graphs where each node has the same degree.
- Finite graphs are graphs where both the number of nodes and the number of edges are finite.
- Infinite graphs are the opposite of finite graphs.
- Pseudo graphs are the opposite of simple graphs.
- Bipartite graphs are graphs where the nodes can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex in the other set.
- Planar graphs are graphs that can be drawn on flat surfaces without any of the edges intersecting each other(besides at nodes of course).
- Multi graphs are graphs that permit multiple edges.
- Euler graphs are graphs that contain a Eulerian circuit.