CSE222- HOMEWORK 7 Solved

Course Assistant: Fatma Nur Esirci 1 Q1

This part about Question1 in HW7

1.1    Problem Soluton Approach
Graphs are created with random vertexes and,it is used Dijkstram Algorithm in order to find shortest path between two vertexes. It is just used ListGraph graph.

1.2    Test Cases
Order of vertex adding to directed graph:

AbstractGraph graph = new ListGraph(11,true); graph.insert(new Edge(0,1,41)); graph.insert(new Edge(1,2,10)); graph.insert(new Edge(2,3,15)); graph.insert(new Edge(2,10,20)); graph.insert(new Edge(3,4,5)); graph.insert(new Edge(4,5,30)); graph.insert(new Edge(5,10,45)); graph.insert(new Edge(5,6,80)); graph.insert(new Edge(5,9,56)); graph.insert(new Edge(6,7,3)); graph.insert(new Edge(7,8,60)); graph.insert(new Edge(8,9,55)); graph.insert(new Edge(1,10,23)); graph.insert(new Edge(3,10,21)); graph.insert(new Edge(4,10,1)); graph.insert(new Edge(1,5,57)); graph.insert(new Edge(9,10,100)); graph.insert(new Edge(1,9,81)); graph.insert(new Edge(2,5,43)); graph.insert(new Edge(6,8,71)); graph.insert(new Edge(1,8,19));

Graph representation :

 

Result of plot_graph :

 

Result of is_undirected:

 

Result of is_acyclic_graph:

 

Result Of shortest_path:

 

2       Q2
This part about Question2 in HW7

2.1      Problem Soluton Approach
Graphs are created with random vertexes and,it is used Dijkstram Algorithm in order to find shortest path between two vertexes. It is just used ListGraph graph.

2.2      Test Cases
Order of vertex adding to undirected graph:

AbstractGraph graph = new ListGraph(19,false);

graph.insert(new Edge(0,2)); graph.insert(new Edge(1,2)); graph.insert(new Edge(2,3)); graph.insert(new Edge(3,4)); graph.insert(new Edge(14,13)); graph.insert(new Edge(15,13)); graph.insert(new Edge(13,12)); graph.insert(new Edge(12,11)); graph.insert(new Edge(11,10)); graph.insert(new Edge(5,6)); graph.insert(new Edge(5,9)); graph.insert(new Edge(15,9)); graph.insert(new Edge(6,7)); graph.insert(new Edge(6,8)); graph.insert(new Edge(7,8));
graph.insert(new Edge(8,9)); graph.insert(new Edge(9,12)); graph.insert(new Edge(4,15)); graph.insert(new Edge(15,5)); graph.insert(new Edge(16,17)); graph.insert(new Edge(17,18));

Graph representation :

 

Result of plot_graph :

 

Result of is_undirected:

 

Result of is_acyclic_graph:

 

Result of is_connected:

 

3       Q3
3.1      Problem Soluton Approach
Graphs are created with random vertexes and,it is used Dijkstram Algorithm in order to find shortest path between two vertexes. It is just used ListGraph graph.

3.2         Test Cases
Order of vertex adding to undirected graph:

AbstractGraph graph = new ListGraph(16,false);

graph.insert(new Edge(0,1)); graph.insert(new Edge(1,2)); graph.insert(new Edge(2,3)); graph.insert(new Edge(3,0)); graph.insert(new Edge(3,4)); graph.insert(new Edge(14,13)); graph.insert(new Edge(15,13)); graph.insert(new Edge(13,12)); graph.insert(new Edge(12,11)); graph.insert(new Edge(11,10)); graph.insert(new Edge(5,6)); graph.insert(new Edge(5,9)); graph.insert(new Edge(15,9)); graph.insert(new Edge(6,7)); graph.insert(new Edge(6,8)); graph.insert(new Edge(7,8)); graph.insert(new Edge(8,9)); graph.insert(new Edge(9,12)); graph.insert(new Edge(4,15)); graph.insert(new Edge(15,5));
Graph representation :

 

Result of plot_graph :

 

Result of is_undirected:

 

Result of is_acyclic_graph:

 

Result of DepthFirstSearch (Show that spanning tree): parents and childs:

 

Spaninig  tree:

 

Result of  BreathFirstSearch (Show that spanning tree): parents and childs:

 

Spaninig  tree:

 

4       Q4