-
Notifications
You must be signed in to change notification settings - Fork 18
Data Structures Graphs
Resource - Graphs
##Graph A graph is a non-linear data structure that can be looked at as a collection of vertices (or nodes) potentially connected by line segments named edges.
An Undirected Graph is a graph where each edge is undirected or bi-directional. This means that the undirected graph does not move in any direction.
A Directed Graph also called a Digraph is a graph where every edge is directed.
Unlike an undirected graph, a Digraph has direction. Each node is directed at another node with a specific requirement of what node should be referenced next.
A complete graph is when all nodes are connected to all other nodes.
A connected graph is graph that has all of vertices/nodes have at least one edge.
A disconnected graph is a graph where some vertices may not have edges.
A graph is said to have a cycle when a node can be visited more than once during a traversal of the graph.
An acyclic graph is a graph without cycles.
A Cyclic graph is a graph that has cycles.
A cycle is defined as a path of a positive length that starts and ends at the same vertex.
An Adjacency matrix is represented through a 2-dimensional array. If there are n vertices, then we are looking at an n x n Boolean matrix
Each Row and column represents each vertex of the data structure. The elements of both the column and the row must add up to 1 if there is an edge that connects the two, or zero if there isn’t a connection.
When there are very few connections.
When there are many connections
An adjacency list is the most common way to represent graphs. An adjacency list is a collection of linked lists or array that lists all of the other vertices that are connected.
Adjacency lists make it easy to view if one vertices connects to another.
A weighted graph is a graph with numbers assigned to its edges. These numbers are called weights. This is what a weighted graph looks like:
- GPS and Mapping
- Driving Directions
- Social Networks
- Airline Traffic
- Netflix uses graphs for suggestions of products