java question and show step!Code! Digraph.java in is http://algs4.cs.princeton.e

Question

java question and show step!Code!

Digraph.java in is

http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Digraph.java.html

4.2.7 The indegree of a vertex in a digraph is the number of directed edges that point to that vertex. The outdegree of a vertex in a digraph is the number of directed edges that emanate from that vertex. No vertex is reachable from a vertex of outdegree 0, which is called a sink; a vertex of indegree 0, which is called a source, is not reachable from any other vertex. A digraph where self-loops are allowed and every vertex has outdegree 1 is called a map (a function from the set of integers from 0 to -1 onto itself). Write a program Degrees java that implements the following API: public class Degrees Degrees (Digraph G) constructor indegree of v int indegree (int v) int outdegree (int v) out degree of v Iterable. Integer> sources sources Iterable Intege sinks sinks boolean isMapC) is G a map?

Explanation / Answer

import java.io.*;
import java.util.*;
import java.util.LinkedList;
class Graph
{
private int V;   
private LinkedList<Integer> adj[];
private int in[];   
Graph(int v)
{
V = v;
adj = new LinkedList[v];
in = new int[V];
for (int i=0; i<v; ++i)
{
adj[i] = new LinkedList();
in[i] = 0;
}
}
void addEdge(int v,int w)
{
adj[v].add(w);
in[w]++;
}
void DFSUtil(int v,Boolean visited[])
{
visited[v] = true;
int n;
Iterator<Integer> i =adj[v].iterator();
while (i.hasNext())
{
n = i.next();
if (!visited[n])
DFSUtil(n,visited);
}
}

Graph getTranspose()
{
Graph g = new Graph(V);
for (int v = 0; v < V; v++)
{
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext())
{
g.adj[i.next()].add(v);
(g.in[v])++;
}
}
return g;
}
Boolean isSC()
{
Boolean visited[] = new Boolean[V];
for (int i = 0; i < V; i++)
visited[i] = false;
DFSUtil(0, visited);
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
for (int i = 0; i < V; i++)
visited[i] = false;
gr.DFSUtil(0, visited);
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;

return true;
}
Boolean isEulerianCycle()
{
if (isSC() == false)
return false;
for (int i = 0; i < V; i++)
if (adj[i].size() != in[i])
return false;

return true;
}
public static void main (String[] args) throws java.lang.Exception
{
Graph g = new Graph(2);
g.addEdge(1, 0);
g.addEdge(0, 2);
if (g.isEulerianCycle())
System.out.println("Given directed graph is eulerian ");
else
System.out.println("Given directed graph is NOT eulerian ");
}
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.