Module 5 Flashcards
- MATHEMATICAL STRUCTURE THAT REPRESENTS RELATIONSHIPS BETWEEN PAIRS OF OBJECTS.
- DENOTED AS G = (V, E),
o VERTICES (V): A FINITE SET OF DISTINCT POINTS REPRESENTING ENTITIES.
o EDGES (E): A SET OF PAIRS OF VERTICES, INDICATING RELATIONSHIPS
Graphs
Different Kinds of Graphs
Undirected Graphs
Complete Undirected Graphs
Directed Graphs (Disgraphs)
Completed Directed Graphs
- IN AN ___________, EDGES DO NOT HAVE A DIRECTION ASSOCIATED WITH THEM.
Undirected Graphs
- A ______________ IS ONE WHERE EVERY PAIR OF DISTINCT VERTICES IS CONNECTED BY AN EDGE.
Complete Undirected Graphs
- IN A _______, EDGES HAVE A DIRECTION ASSOCIATED WITH THEM.
Directed Graphs (Disgraphs)
- A ___________ HAS EVERY PAIR OF DISTINCT VERTICES CONNECTED BY TWO EDGES—ONE IN EACH DIRECTION
Completed Directed Graphs
Graph Terminologies
Subgraphs
Path and Connectivity
- IT CONSISTS OF SELECTED VERTICES AND EDGES FROM THE ORIGINAL GRAPH.
Subgraphs
- Path
o A SEQUENCE OF VERTICES CONNECTED BY EDGES FROM A STARTING VERTEX TO AN ENDING VERTEX. - Simple Path
o A PATH WHERE ALL VERTICES ARE DISTINCT. - Simple Cycle
o A SIMPLE PATH THAT FORMS A CLOSED LOOP, BEGINNING AND ENDING AT THE SAME VERTEX. - Connectivity
o TWO VERTICES ARE CONNECTED IF THERE EXISTS A PATH BETWEEN THEM
Path and Connectivity
o A SEQUENCE OF VERTICES CONNECTED BY EDGES FROM A STARTING VERTEX TO AN ENDING VERTEX
Path
o A PATH WHERE ALL VERTICES ARE DISTINCT.
Simple Path
o A SIMPLE PATH THAT FORMS A CLOSED LOOP, BEGINNING AND ENDING AT THE SAME VERTEX.
Simple Cycle
o TWO VERTICES ARE CONNECTED IF THERE EXISTS A PATH BETWEEN THEM
Connectivity
Advanced Concepts
Weighted Concepts
Spanning Trees
- REFERS TO THE PROCESS OF VISITING ALL VERTICES AND EDGES OF A GRAPH SYSTEMATICALLY TO PERFORM SPECIFIC OPERATIONS OR SEARCHES.
Graph Traversals
- BEGIN AT A CHOSEN START VERTEX AND EXPLORE AS DEEPLY AS POSSIBLE ALONG EACH BRANCH BEFORE BACKTRACKING.
o DEEP EXPLORATION: FOCUSES ON DIVING DEEPLY INTO THE GRAPH’S STRUCTURE, BEFORE BACKTRACKING.
o STACK-BASED BACKTRACKING: USES A STACK OR RECURSION
o TO TRACK AND BACKTRACK FROM DEAD-END PATHS.
Depth First Search (DFS)
- BEGIN AT A CHOSEN START VERTEX AND EXPLORE ALL ITS NEIGHBORS BEFORE MOVING ON TO THE NEXT LEVEL OF NEIGHBORS.
- Characteristic of BFS
o LAYER-BY-LAYER EXPLORATION: FOCUSES ON EXPLORING ALL NEIGHBORS OF A VERTEX BEFORE MOVING ON TO THE NEXT
o QUEUE-BASED TRAVERSAL: USES A QUEUE TO MAINTAIN ORDER AND PRIORITIZE VISITING NEIGHBORS BEFORE DEEPER EXPLORATION.
Breadth First Search(BFS)
SUITABLE FOR EXPLORING DEEPER PATHS
Depth First Search (DFS)
IDEAL FOR SHORTEST PATH FINDING
Breadth First Search(BFS)
- CHOOSE AN INITIAL VERTEX AND PLACE IT IN U.
- SELECT THE VERTEX CONNECTED TO U BY THE LOWEST-COST EDGE AND ADD IT TO U AND ITS CORRESPONDING EDGE TO T.
- REPEAT STEP 2 UNTIL U INCLUDES ALL VERTICES (U = V), CREATING THE MST.
Prim’s Algorithm
- START WITH THE EDGE OF LEAST COST AS THE INITIAL EDGE IN T.
- CONSIDER EDGES IN NON-DECREASING ORDER OF COST.
- INCLUDE AN EDGE IF IT DOESN’T CREATE A CYCLE IN T; REJECT OTHERWISE.
- EMPHASIZE THE SIGNIFICANCE OF SORTING EDGES IN NON-DECREASING ORDER FOR COMPUTATIONAL EFFICIENCY.
Kruskal Algorithm
- ASSIGNS VERTICES TO DIFFERENT CLASSES BASED ON THEIR CALCULATED SHORTEST DISTANCES FROM THE SOURCE.
- ITERATIVELY DETERMINES THE SHORTEST PATH FROM A SINGLE SOURCE VERTEX TO ALL OTHER VERTICES.
Dijkstra Algorithm
- COMPUTES THE SHORTEST PATHS BETWEEN ALL PAIRS OF VERTICES IN A WEIGHTED GRAPH.
- STEPS OF ______
o INITIALIZATION OF MATRICES A AND PATH.
o ITERATIVE COMPUTATION OF SHORTEST PATHS USING INTERMEDIATE VERTICES
Floyds Algorithm
