Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit


EE 518 : Homework Set 8


Problem 1

Ioannou 7.18.


Problem 2

Ioannou 7.20.


Problem 3

Ioannou 7.22.


Problem 4

Ioannou 7.23.


Problem 5

Ioannou 7.27.


Problem 6

Depth-First and Breadth-First Search

Write a Java program that reads in an adjacency matrix representing a graph, either from the command line or from a file and outputs the following information for each input matrix:

a Using each vertex of the graph as the starting point, output the order in which the vertices of the graph are visited using depth-first search.

b Using each vertex of the graph as the starting point, output the order in which the vertices of the graph are visited using breadth-first search.

Convert each adjacency matrix into an equivalent adjacency list. Vertices are numbered consecutively from 1 to n. Store adjacent vertices in increasing order in the adjacency list.


Example input: G1 = [[0,0,1,0,1], [0,0,1,0,0], [1,1,0,0,1], [0,0,0,0,0], [1,0,1,0,0]]

Example Output:

Depth-First Search G1:

1 3 2 5
2 3 1 5
3 1 5 2
4
5 1 3 2


Breadth-First Search G1:

1 3 5 2
2 3 1 5
3 1 2 5
4
5 1 3 2


Problem 7

This is a Java exercise.

Use Dijkstra’s Algorithm to find the shortest path(s) from the vertex v4 to all the other vertices of the graph below. Assume that each undirected edge represents two directed edges with the same weight.