Prerequisite: Generic Class
We can also use them to code for Graph in Java. The Graph class is implemented using HashMap in Java. As we know HashMap contains a key and a value, we represent nodes as keys and their adjacency list in values in the graph.
Illustration: An undirected and unweighted graph with 5 vertices.
Adjacency Matrix is as follows:
Adjacency List is as follows:
Tóm Tắt
Approach:
Just unlikely in C++, we use <> to specify parameter types in generic class creation.
Syntax: To create objects of a generic class
BaseType <Type> obj = new BaseType <Type>()
Note: In Parameter type, we cannot use primitives like ‘int’, ‘char’, or ‘double’.
Example
Java
import
java.util.*;
class
Graph<T> {
private
Map<T, List<T> > map =
new
HashMap<>();
public
void
addVertex(T s)
{
map.put(s,
new
LinkedList<T>());
}
public
void
addEdge(T source,
T destination,
boolean
bidirectional)
{
if
(!map.containsKey(source))
addVertex(source);
if
(!map.containsKey(destination))
addVertex(destination);
map.get(source).add(destination);
if
(bidirectional ==
true
) {
map.get(destination).add(source);
}
}
public
void
getVertexCount()
{
System.out.println(
"The graph has "
+ map.keySet().size()
+
" vertex"
);
}
public
void
getEdgesCount(
boolean
bidirection)
{
int
count =
0
;
for
(T v : map.keySet()) {
count += map.get(v).size();
}
if
(bidirection ==
true
) {
count = count /
2
;
}
System.out.println(
"The graph has "
+ count
+
" edges."
);
}
public
void
hasVertex(T s)
{
if
(map.containsKey(s)) {
System.out.println(
"The graph contains "
+ s +
" as a vertex."
);
}
else
{
System.out.println(
"The graph does not contain "
+ s +
" as a vertex."
);
}
}
public
void
hasEdge(T s, T d)
{
if
(map.get(s).contains(d)) {
System.out.println(
"The graph has an edge between "
+ s +
" and "
+ d +
"."
);
}
else
{
System.out.println(
"The graph has no edge between "
+ s +
" and "
+ d +
"."
);
}
}
@Override
public
String toString()
{
StringBuilder builder =
new
StringBuilder();
for
(T v : map.keySet()) {
builder.append(v.toString() +
": "
);
for
(T w : map.get(v)) {
builder.append(w.toString() +
" "
);
}
builder.append(
"\n"
);
}
return
(builder.toString());
}
}
public
class
Main {
public
static
void
main(String args[])
{
Graph<Integer> g =
new
Graph<Integer>();
g.addEdge(
0
,
1
,
true
);
g.addEdge(
0
,
4
,
true
);
g.addEdge(
1
,
2
,
true
);
g.addEdge(
1
,
3
,
true
);
g.addEdge(
1
,
4
,
true
);
g.addEdge(
2
,
3
,
true
);
g.addEdge(
3
,
4
,
true
);
System.out.println(
"Graph:\n"
+ g.toString());
g.getVertexCount();
g.getEdgesCount(
true
);
g.hasEdge(
3
,
4
);
g.hasVertex(
5
);
}
}
Output:
Graph: 0: 1 4 1: 0 2 3 4 2: 1 3 3: 1 2 4 4: 0 1 3 The graph has 5 vertex The graph has 7 edges. The graph has an edge between 3 and 4. The graph does not contain 5 as a vertex.
My Personal Notes
arrow_drop_up