Code 401: Class 35 - Graphs
- Non-linear data structure
- Collection of nodes or vertices connected by edges
- Vertex node that can have zero or more adjacent vertices
- Edge connection between two vertices
- Neighbor nodes that are directly connected by an edge
- Degree number of edges connected to a vertex
- Undirected Graph each edge is undirected or bi-directional
- Directed Graph (Digraph) every edge is directed, each node points to another specific node
- Complete Graphs all nodes are connected to all other nodes
- Connected Graph all nodes are connected to at least one other node
- Disconnected Graph some vertices may not have edges
- Islands nodes without edges
- Cycle a directed graph containing nodes that point to each other in a circle
- Acyclic directed graph without cycles
- Cyclic a directed graph that cycles
- Adjacency Matrix 2D representation with an n X n boolean matrix (n = vertices)
- Sparse Graph Very few connections
- Dense Graph many connections
- Adjacency List collection of linked lists or an array that shows a list of all of the vertices linked to each
- Weighted Graph graph with edges that have numbers
- Weighted Graph Matrix places the weight value in the matrix instead of a boolean
- Weighted Adjacency List Places the name and the weight in each node
- Breadth First Traversal
Enqueue the declared start node- Create a loop that will run while the node still has nodes present
Dequeue the first node from the queue- If
Dequeue node has unvisited child nodes, mark as visited and reinsert them into the queue
- Depth First Traversal
Push root node into a stack- Start while loop while stack is not empty
Peek at top node in stack- If top node has unvisited children, mark the top node as visited, then
Push any unvisited children back into the stack
- If top node does not have any unvisited children
Pop that node off stack
- Repeat until stack is empty
Return to reading-notes Deployed Site
Return to reading-notes Mark Down