## Instructions

**Objective**

To complete a Java assignment, you need to write a program that implements an undirected graph in the Java language. An undirected graph consists of a set of vertices connected by edges, where the edges have no direction. In the program, you should define classes to represent vertices and edges, along with methods to add vertices, create edges between them, and perform other graph-related operations like traversals or finding paths. Utilize data structures like arrays or linked lists to manage the graph's connectivity efficiently. Make sure to implement the necessary algorithms and error handling to ensure the program runs smoothly and produces correct results.

## Requirements and Specifications

**Source Code**

```
import java.util.*;
public class Graph
{
public int noOfVertices = - 1;
public int[][] edges = null;
public int[][] weights = null;
// Creates a new empty graph.
public Graph() { }
public Graph(int[][] data, boolean weighted)
{
if (weighted) initWeighted(data);
else initUnweighted(data);
}
private void initWeighted(int[][] data)
{
// Structure of data
// ------------------
// length: 2 times number of vertices
// 2i: neighbours of vertex i.
// 2i + 1: weight of edges from vertex i to corresponding neighbour.
noOfVertices = data.length / 2;
edges = new int[noOfVertices][];
weights = new int[noOfVertices][];
for (int i = 0; i < noOfVertices; i++)
{
int dataInd = 2 * i;
int deg = data[dataInd].length;
edges[i] = new int[deg];
weights[i] = new int[deg];
for (int j = 0; j < deg; j++)
{
edges[i][j] = data[dataInd][j];
weights[i][j] = data[dataInd + 1][j];
}
}
}
private void initUnweighted(int[][] data)
{
noOfVertices = data.length;
edges = new int[noOfVertices][];
for (int i = 0; i < noOfVertices; i++)
{
edges[i] = data[i].clone();
}
}
/**
* Relexas an edge of the graph based on the given distances.
* @param vInd The vertex from which the edge starts.
* @param neighInd The index of the vertex in the neighbourhood of v to
* which the edge points. That is, the edge goes from vId
* to edges[vId][neighInd].
*/
public boolean relax(int vInd, int neighInd, int[] distances)
{
int uInd = edges[vInd][neighInd];
int uDis = distances[uInd];
int vDis = distances[vInd];
int vuWeight = weights[vInd][neighInd];
boolean update = false;
// Avoid problems with overflow.
if (vuWeight > 0)
{
update = vDis < uDis - vuWeight;
}
else
{
update = vDis + vuWeight < uDis;
}
if (update)
{
distances[uInd] = vDis + vuWeight;
return true;
}
return false;
}
public int[][] dfs(int startId)
{
// Output data
int[] parIds = new int[noOfVertices];
int[] preOrder = new int[noOfVertices];
int[] postOrder = new int[noOfVertices];
int preCount = 0;
int postCount = 0;
// Helpers to compute DFS
int[] neighIndex = new int[noOfVertices];
int[] stack = new int[noOfVertices];
int stackSize = 0;
boolean[] visited = new boolean[noOfVertices];
for (int vId = 0; vId < noOfVertices; vId++)
{
parIds[vId] = -1;
preOrder[vId] = -1;
postOrder[vId] = -1;
visited[vId] = false;
neighIndex[vId] = 0;
}
// Push
stack[stackSize] = startId;
stackSize++;
while (stackSize > 0)
{
int vId = stack[stackSize - 1];
int nInd = neighIndex[vId];
if (nInd == 0)
{
visited[vId] = true;
// *** Pre-order for vId ***
preOrder[preCount] = vId;
preCount++;
}
if (nInd < edges[vId].length)
{
int neighId = edges[vId][nInd];
if (!visited[neighId])
{
// Push
stack[stackSize] = neighId;
stackSize++;
parIds[neighId] = vId;
}
neighIndex[vId]++;
}
else
{
// All neighbours checked, backtrack.
stackSize--; // Pop;
// *** Post-order for vId ***
postOrder[postCount] = vId;
postCount++;
}
}
return new int[][]
{
parIds,
preOrder,
postOrder
};
}
public int[][] bfs(int startId)
{
// Output data
// 0: distances from start vertex
// 1: BFS-order
// 2: parent-IDs
int[][] bfsResult = new int[3][noOfVertices];
int[] distances = bfsResult[0];
int[] q = bfsResult[1];
int[] parents = bfsResult[2];
for (int i = 0; i < noOfVertices; i++)
{
distances[i] = Integer.MAX_VALUE;
q[i] = -1;
parents[i] = -1;
}
// Set start vertex
distances[startId] = 0;
q[0] = startId;
int qSize = 1;
for (int qInd = 0; qInd < qSize; qInd++)
{
int vInd = q[qInd];
int nDis = distances[vInd] + 1;
for (int nInd = 0; nInd < edges[vInd].length; nInd++)
{
int uInd = edges[vInd][nInd];
if (nDis < distances[uInd])
{
distances[uInd] = nDis;
parents[uInd] = vInd;
q[qSize] = uInd;
qSize++;
}
}
}
return bfsResult;
}
public int[] bellmanFord(int startId)
{
int[] distances = new int[noOfVertices];
Arrays.fill(distances, Integer.MAX_VALUE);
distances[startId] = 0;
HashSet updatedLast = new HashSet();
HashSet updateNext = new HashSet();
updatedLast.add(startId);
while (updatedLast.size() > 0)
{
for (int vId : updatedLast)
{
for (int i = 0; i < edges[vId].length; i++)
{
if (relax(vId, i, distances))
{
updateNext.add(edges[vId][i]);
}
}
}
updatedLast.clear();
HashSet tmp = updatedLast;
updatedLast = updateNext;
updateNext = tmp;
}
return distances;
}
}
```

## Similar Samples

At ProgrammingHomeworkHelp.com, explore a wide range of expertly crafted programming solutions. Our sample section showcases real-world examples and detailed explanations, helping you understand complex concepts with ease. Perfect for students seeking clarity and assistance in their programming assignments.

Java

Java

Java

Java

Java

Java

Java

Java

Java

Java

Java

Java

Java

Java

Java

Java

Java

Java

Java

Java