Data Structure-Graphs
Graph is a data structure design to show relationships between objects. Graph can be called Networks. The graph’s nodes called Vertices, and graph connection called Edges. The vertices and the edges contain data. Commonly the edges data is how strong a connection is. Edge’s data must represent some information about the connection. Two vertices connected with an edge called adjacent.
Directions:
Edge can have a direction, meaning the relationship between two vertices only applies on one way and not the other. Graph with direction edges called Directed Graphs. You can have more then one edge between two vertices. A graph with no directed edges called Undirected Graph.
Graphs can have cycles, meaning you can visit the same node more then one time. This graph’s property is very dangerous because it can cause infinite loops when traversing the graph. Often you need to make sure the graph you’re taking in at input is acyclic, meaning there are no cycles in your graph. A common type of graph is DAG stands for Directed Acyclic Graph.
Graph Connectivity:
A disconnected graph by definition is a graph with one or more vertices that have no edges with the main graph. Thus a connected graph have no disconnect vertices. Graph’s connectivity measure by the minimum edges need to be removed in-order to disconnect the graph. A graph with high connectivity called a stronger graph. Connectivity also measure by direction, meaning, a graph with a path from A to B and from B to A is more strong then just one direction graph. Thus direct graphs are always counts as weakly connected.
Graph Implementations:
- Edge list: list of edges stored in a 2D array.
- Adjacency list: list of vertices in a 2D array. The vertices have an ID number that correspond to the indexes of the array. In every vertice index the connected vertices IDs are stored.
3. Adjacency Matrix: A matrix or a rectangular array is essentially a 2D array that the lists inside have the same length. In the matrix every row is a vertice. The inside array show the adjacent vertice. 1 if it adjacent and 0 if it’s not.
Graph Traversal:
DFS: Same as in trees pick a random node to start with, and then go to its next left node. You can implement this algorithm with recursive function or a stack when there is no place to go. The time complexity is O(E + V), E= number of edges , V = number of vertices
BFS: Same as in trees first go throw all the nodes connected to the chosen node and then do the same for the leftest connect node. We can use queue to implement the algorithm, because after we check all the “children” we continue to the last checked “child”. The efficiency is O(E + V).
Paths in Graphs:
A path is just a specific rout you take in a traversal or search.
Eulerian Path:
Eulerian path travels through every edge in the graph at least once. Graphs can only have eulerian cycles if all vertices have an even degree. Meaning the number of edges of each vertex are the same. But it’s okay if two nodes have an odd degree as long as they are the start and end of the path. To find an eulerian path just start at a vertex and follow edges until you return back to that same vertex. If you didn’t encounter every edge you can start from an unseen edge connected to a node you already visited. Then repeat this process until you seen every node once. Then combine the path of each cycle together with the nodes they have in common. For example, A, B, E + B, C, D = A, B, C, D, E. This takes O(E), E stands for edges.
Hamiltonian Path:
Hamiltonian path must go through every vertex once. A hamiltonian cycle start and end with the same vertex.
