Graphs XandY..andZ - abukhalil-LTUC-ASAC/amman-401d4 GitHub Wiki
Is this math?
Not exactly, this is the theory behind math! Not much at depth but just enough to understand what is happening here.
The A to Z
You must be familiar with linearity and linear patterns right? How everything is lined neatly and are consecutive such as arrays and linked lists. Graphs are not as neat, and were not meant to. How on earth would you be able to map anything on earth, otherwise?
To get behind the complexity, the basics must be comprehended:
- Vertex: the general, fancier type of node that is also a node, it is defined by adjacent nodes or none at all.
- Edge: the connecting line.
- Neighbors: they exist around a vertex, and are connected by an edge.
- Degree: How far, or how many edges connect a vertex to another.
So how math graphs relates?
You might have likely dealt with graphs, seeing that almost everyone goes to school these days, unlike the old good days. 2D Graphs were represented by two infinite lined vertices. If you think about it, an x axes, represent an infinitely large and small numbers of vertex points, and each point is defined consecutively in a linear data structure similar to arrays.
Putting X and Y together allowed for non linearity, where not only X is bigger than X - 1, but also is defined by some Y. Your own vertex point C, when put is simply 1 edge away from an x and y, and is defined by them since it does not relate or is connected by any other x and y values.
DSA Graphs
The general method would involve any shape and finite number of vertices, x and y has there uses in the 3d world, but to map objects and their behavior in discrete values it is necessary to provide this general method instead. So here are the common shapes:
-
Directed vs Undirected graphs: they are simply defined by if the edge has a defined direction or not, showing which is from and which is to.
-
Complete vs Connected vs Disconnected:
1 - A complete graph is when all vertices are connected with an edge to all vertices, very messy.
2 - Connected is when all vertices connect at least once to other vertices.
3 - Disconnected is when some vertices or even just one has no edge connecting them at all.
-
Acyclic vs Cyclic: which tells you if vertices have connections that lead back to them or not.
Dealing with DSA Graphs
There are two general ways we have learned, that helps present graphs in a table of sorts.
- Using Adjacency matrix
- Using Adjacency list
The matrix represents what you might have also took at math, all vertices are lined on both sides of a 2D matrix. And whenever there is a connection between two vertices on each side a 1 is added, otherwise its a zero.
Adjacency list is simply a column of all vertices, and each index in the column represents all the connections it contains.
And finally, a set of breadth and depth search will be used to go through. The methods will be similar to trees, with a stack used in two different ways to express visiting all children first before moving for breadth first, and to visit all possible children first starting with the first child before going back once no children are found.