Please enable JavaScript.
Coggle requires JavaScript to display documents.
M11, Graphs, Depth-First Search and Breadth-First Search, Topologicalā¦
-
Graphs
Algorithms
Shortest Path Algorithm
Dijkstraās Algorithm: Finds the shortest path from a single source to all other vertices in a weighted graph with non-negative weights.
Bellman-Ford Algorithm: Finds the shortest path from a single source to all other vertices in a graph with negative weights.
-
-
Graph Coloring
-
Applications: Scheduling problems, register allocation in compilers.
Topological Sorting
Ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u to v, u appears before v.
Applications: Task scheduling, resolving symbol dependencies in linkers.
types
Undirected graph: edges have no direction. An edge (u, v) is identical to (v, u).
Directed Graph (Digraph): Edges have a direction. An edge (u, v) is not the same as (v, u).
Weighted Graph: Edges have weights representing costs, distances, or other measures.
-
Simple Graph: No loops (edges connecting a vertex to itself) and no multiple edges between the same pair of vertices.
-
-
-
Graph representations
Adjacency Matrix
.
Time Complexity for Operations: Checking for an edge is O(1), adding/removing edges is O(1).
-
A 2D array where A[i][j] = 1 if there is an edge between vertex i and vertex j, otherwise A[i][j] = 0.
Adjacency List
-
-
Time Complexity for Operations: Checking for an edge is O(d) where d is the degree of the vertex, adding/removing edges is O(1).
Traversal Algorithms
Depth first search (DFS)
-
-
Applications: Path finding, cycle detection, topological sorting.
-
-
-
-
-