Java Program to Find the Arboricity of a Graph
import
java.util.*;
public
class
Arboricity {
static
int
V, E;
static
LinkedList<Integer> adj[];
Arboricity(
int
v)
{
V = v;
adj =
new
LinkedList[v];
for
(
int
i =
0
; i < v; ++i)
adj[i] =
new
LinkedList();
}
void
addEdge(
int
v,
int
w)
{
adj[v].add(w);
adj[w].add(v);
}
int
degree(
int
v)
{
return
adj[v].size();
}
int
arboricity()
{
int
maxDegree =
0
;
for
(
int
i =
0
; i < V; i++)
maxDegree = Math.max(maxDegree, degree(i));
return
(
int
)Math.ceil((
double
)E
/ (
double
)maxDegree);
}
public
static
void
main(String args[])
{
Arboricity g =
new
Arboricity(
4
);
g.E =
5
;
g.addEdge(
0
,
1
);
g.addEdge(
0
,
2
);
g.addEdge(
1
,
2
);
g.addEdge(
2
,
3
);
g.addEdge(
3
,
3
);
System.out.println(
"Arboricity of the given graph: "
+ g.arboricity());
}
}
import
java.util.*;
public
class
Arboricity {
static
int
V, E;
static
LinkedList<Integer> adj[];
Arboricity(
int
v)
{
V = v;
adj =
new
LinkedList[v];
for
(
int
i =
0
; i < v; ++i)
adj[i] =
new
LinkedList();
}
void
addEdge(
int
v,
int
w)
{
adj[v].add(w);
adj[w].add(v);
}
int
degree(
int
v)
{
return
adj[v].size();
}
int
arboricity()
{
int
maxDegree =
0
;
for
(
int
i =
0
; i < V; i++)
maxDegree = Math.max(maxDegree, degree(i));
return
(
int
)Math.ceil((
double
)E
/ (
double
)maxDegree);
}
public
static
void
main(String args[])
{
Arboricity g =
new
Arboricity(
4
);
g.E =
5
;
g.addEdge(
0
,
1
);
g.addEdge(
0
,
2
);
g.addEdge(
1
,
2
);
g.addEdge(
2
,
3
);
g.addEdge(
3
,
3
);
System.out.println(
"Arboricity of the given graph: "
+ g.arboricity());
}
}