# How to Construct a Graph?

I'm working on a project that involves parsing through a data file and reading it into a graph. In this graph I must find the shortest distance between two vertices. I've been trying for a couple days actually but I just can't seem to figure out how to even get this graph up.

I tried to use Dijkstra's algorithm but I figured that a simple BFS would be simpler and easier to understand but I do not know how to construct the graph in the first place.

`````` import java.util.ArrayList;

/*
* Here we create an undirected graph
*/
public class Graph
{

public int vertices;

public Graph(int vertices)
{
// TODO Auto-generated constructor stub
this.vertices = vertices;

}

public void addEdge(String actor, String actor2, String movie)
{
if(getVertex(actor) == -1)
{

}
}

public int[] neighbors(int vertex)
{

ArrayList<Integer> neighbors = new ArrayList<>();

for (int i = 0; i < vertices; i++) {

{
}
}

int size = neighbors.size();

int[] neighbor = new int[size];

for(int i = 0; i < size; i++){

neighbor[i] = neighbors.get(i);
}
return neighbor;
}

public void makePath(String actor, String actor2)
{

}
}
``````

The result is to create a graph and make a function that finds the shortest distance. I do not need help figuring out how to find the shortest distance as that function is straightforward for me but I need help constructing the graph in the first place. On

Assuming you have the number of vertices (only a count of how many there are), use a 2D - Array.

`int [][] edges = new int[vertices][vertices]; // vertices of map`

`edges[BeginningVertex][EndingVertex] = Weight or time needed to cross;` On

I suggest that for creating Graph (Directed Graph) and run BFS algorithm ,use this code:

Graph.java:

``````public class Graph {

private final boolean [][]MAT;

private final int NODE_NUMBER;

public Graph(int NODE_NUMBER) {
this.NODE_NUMBER = NODE_NUMBER;
this.MAT = new boolean [NODE_NUMBER][NODE_NUMBER];
}

public void addEdge(int nodeA , int nodeB){
this.MAT[nodeA][nodeB] = true;
}

public boolean hasEdge(int nodeA, int nodeB){
return MAT[nodeA][nodeB];
}

public final int getNodeSize(){
return NODE_NUMBER;
}
}
``````

BfsResult.Java:

``````import java.util.ArrayList;
import java.util.List;

public class BfsResult {

private final int root;

private final boolean []visited;

private final int []distance;

private final int []parent;

public BfsResult(int root, boolean[] visited, int[] distance, int[] parent) {
this.root = root;
this.visited = visited;
this.distance = distance;
this.parent = parent;
}

public int getRoot() {
return root;
}

public int getParent(int node){
return parent[node];
}

public int getDistance(int node){
return distance[node];
}

public boolean isAccessible(int node){
return visited[node];
}

public int[] getPath(int node){

List<Integer> path = new ArrayList <>(  );

int cur = node;
do{
cur = parent[cur];

}while ( cur != -1 );

int []pathArray = new int[path.size()];

for(int i = 0 ; i < path.size() ; ++i){
pathArray[i] = path.get( path.size() - (i + 1) );
}

return pathArray;

}

public String getPathString(int node) {
int[] path = getPath( node );

StringBuilder builder = new StringBuilder(  );

for ( int i = 0; i < path.length; i++ ) {
builder.append( path[i] );

if(i + 1 < path.length){
builder.append( " -> " );
}
}

return builder.toString();
}
}
``````

BfsAlgorithm.java:

``````import java.util.LinkedList;
import java.util.Queue;

public class BfsAlgorithm {

private final Graph graph ;
private final int root;

public BfsAlgorithm(Graph graph, int root) {
this.graph = graph;
this.root = root;
}

public BfsResult run() {

boolean []visit     = new boolean[graph.getNodeSize()];
int     []distances = new int    [graph.getNodeSize()];
int     []parents   = new int    [graph.getNodeSize()];

visit[root]     = true;
distances[root] = 0;
parents[root]   = -1;

while( !queue.isEmpty() ){

int currentNode = queue.poll();

for(int i = 0 ; i < graph.getNodeSize() ; ++i){

if( graph.hasEdge( currentNode , i ) && !visit[i] ){

visit    [i] = true;
distances[i] = distances[currentNode] + 1;
parents  [i] = currentNode;

}
}
}

return new BfsResult( root, visit, distances, parents );

}
}
``````

Main.java:

``````public class Main {

public static void main(String[] args) throws Exception {

//create sample graph with 6 node
Graph graph = new Graph( 6 );

//directed edges:

//select root node of bfs
int root = 0;

BfsAlgorithm algorithm = new BfsAlgorithm( graph, root );

BfsResult result = algorithm.run();

//show result
for ( int i = 0; i < graph.getNodeSize(); i++ ) {

if(result.isAccessible( i )){
System.out.printf("From node %d to %d  is accessible\n" ,result.getRoot() ,i  );
System.out.printf("Distance between node  %d -> %d  is %d\n" ,result.getRoot() , i , result.getDistance( i ) );
System.out.printf("Path     between node  %d -> %d  is:\t%s\n" ,result.getRoot() , i , result.getPathString( i ) );
}else{
System.out.printf("From node %d to %d  is not accessible!\n" ,result.getRoot() ,i );
}

System.out.println("\n ------------------------ \n");
}

}

}
``````

I run this algorithm for the graph by root 0: result is :

``````From node 0 to 0  is accessible
Distance between node  0 -> 0  is 0
Path     between node  0 -> 0  is:  0

------------------------

From node 0 to 1  is accessible
Distance between node  0 -> 1  is 1
Path     between node  0 -> 1  is:  0 -> 1

------------------------

From node 0 to 2  is accessible
Distance between node  0 -> 2  is 1
Path     between node  0 -> 2  is:  0 -> 2

------------------------

From node 0 to 3  is accessible
Distance between node  0 -> 3  is 2
Path     between node  0 -> 3  is:  0 -> 1 -> 3

------------------------

From node 0 to 4  is accessible
Distance between node  0 -> 4  is 2
Path     between node  0 -> 4  is:  0 -> 2 -> 4

------------------------

From node 0 to 5  is accessible
Distance between node  0 -> 5  is 3
Path     between node  0 -> 5  is:  0 -> 2 -> 4 -> 5

------------------------
``````