class Graph {
int [][] adjacencyMatrix;
int numVertices;
}
public class AdjacencyMatrixGraph implements Graph {
private int [][] adjacencyMatrix;
private GraphType graphType = GraphType.DIRECTED;
private int numVertices = 0;
public AdjacencyMatrixGraph(int numVertices, GraphType graphType) {
this.numVertices = numVertices;
this.graphType = graphType;
adjacencyMatrix = new int[numVertices][numVertices];
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
adjacencyMatrix[i][j] = 0;
}
}
}
public void addEdge(int v1, int v2) {
if (v1 >= numVertices || V1 < 0 || v2 >= numVertices || v2 < 0) {
throw new IllegalArgumentException("Vertex number is not valid");
}
adjacencyMatrix[v1][v2] = 1;
if (graphType == GraphType.UNDIRECTED) {
adjacencyMatrix[v2][v1] = 1;
}
}
public List<Integar> getAdjacentVertices(int v) {
if (v >= numVertices || v < 0) {
throw new IllegalArgumentException("Vertex number is not valid");
}
List<Integar> adjacencyVerticesList = new ArrayList<>();
for (int i = 0; i < numVertices; i++) {
if (adjacencyMatrix[v][i] == 1) {
adjacencyVerticesList.add(i);
}
}
Collections.sort(adjacencyVerticesList);
return adjacencyVerticesList;
}
}
Adjacency list
Each vertex has a pointer to a linked list
Downside: The same graph can have multiple representations
class Node {
int vertexId;
Node* next;
}
class Gragh {
List<Node> vertices;
}
Adjacency set
class Node {
int vertexId;
Set<Node> nodes;
}
class Gragh {
List<Node> vertices;
}
public class AdjacencySetGraph implement Graph {
private List<Node> vertexList = new ArrayList<>();
private GaraphType = GaraphType.DIRECTED;
private int numVertices = 0;
public AdjacencyMatrixGraph(int numVertices, GraphType graphType) {
this.numVertices = numVertices;
for (int i = 0; i < numVertices; i++) {
vertexList.add(new Node(i));
}
this.graphType = graphType;
}
public void addEdge(int v1, int v2) {
if (v1 >= numVertices || V1 < 0 || v2 >= numVertices || v2 < 0) {
throw new IllegalArgumentException("Vertex number is not valid");
}
vertexList.get(v1).addEdge(v2);
if (graphType == GaraphType.UNDIRECTED) {
vertexList.get(v2).addEdge(v1);
}
}
public List<Integar> getAdjacentVertices(int v) {
if (v >= numVertices || v < 0) {
throw new IllegalArgumentException("Vertex number is not valid");
}
return vertexList.get(v).getAdjacentVertices();
}
}
2.Compares
3.Traversal
This is very similar to tree traversal
In a graph multiple paths can lead from one to another
Graph has circle, so the same node can be visited multiple times
Keep track of the nodes previously visited
Depth-first traversal (post order)
Use a visited list to keep track of nodes already visited
e.g., boolean array
public static void depthFirstTraversal(Gragh graph, int[] visited, int currentVertex) {
if (visited[currentVertex] == 1) {
return;
}
visited[currentVertex] = 1;
List<Integar> list = new gragh.getAdjacentVertices(currentVertex);
for (int vertex : list) {
depthFirstTraversal(graph, visited, vertex);
}
}
