Implementation of graphs, adjaceny matrix

This is a short summary of what graphs are, the types of graphs and how they are implemented. Some methods even have the source code present in the slide

1. Implementation of graphs Rayyan naeem 2024pai7303

2. Adjacency matrix Definition: An adjacency matrix is a 2D array (or matrix) of size VxV , where V is the number of vertices in the graph. Matrix Content : If there is an edge between vertices i and j, matrix[ i ][j] = 1 (for unweighted graphs) or the weight of the edge (for weighted graphs).If there is no edge, matrix[ i ][j] = 0.

3. #include <iostream> #include <vector> using namespace std; class graph{ private: int n; vector<vector<int>> adj_matrix ; public: graph(int num):n(num), adj_matrix ( n,vector <int>(n,0)){} void add_edge (int u, int v) { if(u>=0 && u<n && v>=0 && v<n) { adj_matrix [u][v]=1; adj_matrix [v][u]=1; } } void print_matrix () { for(int i =0;i< n;i ++) { for(int j=0;j< n;j ++) { cout << adj_matrix [ i ][j]<<"\t"; } cout << endl ;}} }; int main() { int x,a,b ; cout <<"enter the number of vertices = "; cin >>x; graph g(x); for(int i =0;i< x;i ++) { cout <<"\n enter the edge="; cin >>a>>b; g.add_edge ( a,b );} cout << endl ; g.print_matrix (); return 0; }

4. Space Complexity: O(V²), where V is the number of vertices. Memory Usage: Efficient for dense graphs (graphs where the number of edges is close to the maximum number of edges, i.e., V²). Inefficient for sparse graphs (graphs with fewer edges). Advantages: Simple and easy to implement. Quick lookup for edge existence between two vertices. Disadvantages: Requires O(V²) space, making it less efficient for sparse graphs. Iterating over all edges can take O(V²) time.

5. Adjacency list Definition: An adjacency list represents a graph as a collection of lists. Each vertex has a list of its adjacent vertices. Structure: Each vertex points to a list containing its neighboring vertices. More memory-efficient than an adjacency matrix, especially for sparse graphs.

6. #include <iostream> #include<list> #include<map> using namespace std; class graph { map < int,list <int>> adjlist ; public: void add_edge (int u,int v) { adjlist [u]. push_back (v); adjlist [v]. push_back (u); } void display() { for(auto i: adjlist ) { cout << endl << i.first << "->"; for(auto j: i.second ) { cout <<j<<" "; }}}}; int main() { graph g; int a,b ; char x; bool n=true; while(n) { cout <<"\n enter the edges="; cin >>a>>b; g.add_edge ( a,b ); cout <<"do you want to enter more edges(y/n)="; cin >>x; if(x=='n') n=false; } g.display (); return 0; }

7. Space Complexity: O(V + E), where V is the number of vertices, and E is the number of edges.More efficient than an adjacency matrix for sparse graphs. Advantages: More space-efficient for sparse graphs. Easier to iterate over neighbors of a vertex. Disadvantages: Slower edge lookups compared to an adjacency matrix (O(V)). Can become complex for weighted graphs.

8. Single source shortest path What is Dijkstra’s Algorithm? Dijkstra's Algorithm is used to find the shortest path from a source vertex to all other vertices in a weighted graph. Key Characteristics: Works with graphs that have non-negative weights. Greedy algorithm approach. Main Idea: Start from a source vertex and expand to its neighboring vertices. Keep track of the shortest known distance to each vertex. Update these distances as shorter paths are found using neighboring vertices. Greedy Approach: Always selects the unvisited vertex with the smallest known distance.

9. algorithm 1. function Dijkstra(Graph, source): 2. dist [source] ← 0 // Distance from source to source is 0 3. for each vertex v in Graph: 4. if v ≠ source: 5. dist [v] ← ∞ // Set all other distances to infinity 6.add v to unvisited set 7. while unvisited set is not empty: 8. u ← vertex in unvisited set with smallest dist [u] remove u from unvisited set for each neighbor v of u: alt ← dist [u] + length(u, v) if alt < dist [v]: dist [v] ← alt // Update distance if shorter path is found return dist []

10. All pair shortest path Floyd- Warshall is an algorithm used to find the shortest paths between all pairs of vertices in a weighted graph. Key Characteristics: Works for both directed and undirected graphs. Can handle graphs with negative edge weights, but no negative cycles. Main Idea: It uses a dynamic programming approach. It considers all pairs of vertices and iteratively improves the shortest path by including intermediate vertices. Key Concept: If a path from vertex i to j through vertex k is shorter than the previously known path from i to j , then update the path to pass through k .

11. algorithm function FloydWarshall ( dist [][]): for k from 1 to n: for i from 1 to n: for j from 1 to n: if dist [ i ][j] > dist [ i ][k] + dist [k][j]: dist [ i ][j] ← dist [ i ][k] + dist [k][j] return dist [][]

12. Thank you