Article directory
- 1. Code warehouse
- 2. Comparison of basic representations of graphs
- 3. Adjacency matrix: Array and TreeSet
-
- 3.1 Illustration
- 3.2 Array main code analysis
- 3.3 Test output
- 3.4 Code using TreeSet
- 4. Adjacency list: LinkedList
-
- 4.1 Illustration
- 4.2 LinkedList main code analysis
- 4.3 Test output
- 5. Complete code
-
- 5.1 Adjacency list – Array
- 5.2 Adjacency list-TreeSet
- 5.3 Adjacency matrix-LinkedList
- 5.4 Input files
1. Code warehouse
https://github.com/Chufeng-Jiang/Graph-Theory/tree/main/src/Chapt01_Adjacency
2. Comparison of basic representations of graphs
3. Adjacency matrix: Array and TreeSet
3.1 Illustration
3.2 Array main code analysis
The code has been deleted
public AdjMatrix(String filename){<!-- -->
File file = new File(filename);
try(Scanner scanner = new Scanner(file)){<!-- -->
V = scanner.nextInt(); //Read the first number in the first line, which represents the number of vertices in the graph
//Construct adjacency matrix
adj = new int[V][V];
E = scanner.nextInt(); //Read the second number in the first line, which represents the number of edges in the graph
// E is the number of edges, expressed as the E line starting from the second line in g.txt
for (int i = 0; i < E; i + + ) {<!-- -->
int a = scanner.nextInt(); //Read a vertex of the edge
int b = scanner.nextInt(); //Read another vertex of the edge
adj[a][b] = 1; //If there is an edge, set it to 1
adj[b][a] = 1;
}
}
}
3.3 Test output
3.4 Code using TreeSet
The code has been deleted
Only one line needs to be changed
adj = new TreeSet[V]; //Construct adjacency list, V rows, V LinkedLists
4. Adjacency list: LinkedList
4.1 Illustration
4.2 LinkedList main code analysis
The code has been deleted
public class AdjList {<!-- -->
private int V;
private int E;
private LinkedList<Integer>[] adj;
public AdjList(String filename){<!-- -->
File file = new File(filename);
try(Scanner scanner = new Scanner(file)){<!-- -->
V = scanner.nextInt();
/*Construct an adjacency list, V rows, V LinkedLists*/
adj = new LinkedList[V];
for (int i = 0; i < V; i + + ) {<!-- -->
adj[i] = new LinkedList<Integer>();
}
E = scanner.nextInt(); //Read the second number in the first line
// E is the number of edges, expressed as the E line starting from the second line in g.txt
for (int i = 0; i < E; i + + ) {<!-- -->
int a = scanner.nextInt(); //Read a vertex of the edge
int b = scanner.nextInt(); //Read another vertex of the edge
adj[a].add(b);
adj[b].add(a);
}
}
}
4.3 Test output
5. Complete code
5.1 Adjacency List – Array
package Chapt01_Adjacency;
import java.io.File;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Scanner;
public class AdjList {<!-- -->
private int V;
private int E;
private LinkedList<Integer>[] adj;
public AdjList(String filename){<!-- -->
File file = new File(filename);
try(Scanner scanner = new Scanner(file)){<!-- -->
V = scanner.nextInt();
if(V < 0) throw new IllegalArgumentException("V must be non-negative");
adj = new LinkedList[V]; //Construct adjacency list, V rows, V LinkedLists
for (int i = 0; i < V; i + + ) {<!-- -->
adj[i] = new LinkedList<Integer>();
}
E = scanner.nextInt(); //Read the second number in the first line
if(E < 0) throw new IllegalArgumentException("E must be non-negative");
// E is the number of edges, expressed as the E line starting from the second line in g.txt
for (int i = 0; i < E; i + + ) {<!-- -->
int a = scanner.nextInt(); //Read a vertex of the edge
validateVertex(a);
int b = scanner.nextInt(); //Read another vertex of the edge
validateVertex(b);
if(a == b) throw new IllegalArgumentException("Self Loop is Detected"); //Determine whether there is a self-loop edge
if(adj[a].contains(b)) throw new IllegalArgumentException("Parallel Edges are Detected"); //Determine whether parallel l edges exist
adj[a].add(b);
adj[b].add(a);
}
}
catch (IOException e){<!-- -->
e.printStackTrace();
}
}
private void validateVertex(int v){<!-- -->
if(v < 0 || v >= V)
throw new IllegalArgumentException("vertex" + v + "is invalid");
}
public int V(){<!-- -->
return V;
}
public int E(){<!-- -->
return E;
}
public boolean hasEdge(int v, int w){<!-- -->
validateVertex(v);
validateVertex(w);
return adj[v].contains(w);
}
public LinkedList<Integer> adj(int v){<!-- -->
validateVertex(v);
return adj[v];
}
public int degree(int v){<!-- -->
return adj(v).size();
}
@Override
public String toString(){<!-- -->
StringBuilder sb = new StringBuilder();
sb.append(String.format("V = %d, E = %d\
", V, E));
for (int i = 0; i < V; i + + ) {<!-- -->
sb.append(String.format("%d:",i));
for (int w: adj[i]) {<!-- -->
sb.append(String.format("%d ",w));
}
sb.append('\
');
}
return sb.toString();
}
public static void main(String[] args){<!-- -->
AdjList adjList = new AdjList("g1.txt"); //Create a new adjacency matrix and initialize it from the file content
System.out.println(adjList);
}
}
5.2 Adjacency list-TreeSet
package Chapt01_Adjacency;
import java.io.File;
import java.io.IOException;
import java.util.Scanner;
import java.util.TreeSet;
public class AdjSet {<!-- -->
private int V;
private int E;
private TreeSet<Integer>[] adj;
public AdjSet(String filename){<!-- -->
File file = new File(filename);
try(Scanner scanner = new Scanner(file)){<!-- -->
V = scanner.nextInt();
if(V < 0) throw new IllegalArgumentException("V must be non-negative");
adj = new TreeSet[V]; //Construct adjacency list, V rows, V LinkedLists
for (int i = 0; i < V; i + + ) {<!-- -->
adj[i] = new TreeSet<Integer>();
}
E = scanner.nextInt(); //Read the second number in the first line
if(E < 0) throw new IllegalArgumentException("E must be non-negative");
// E is the number of edges, expressed as the E line starting from the second line in g.txt
for (int i = 0; i < E; i + + ) {<!-- -->
int a = scanner.nextInt(); //Read a vertex of the edge
validateVertex(a);
int b = scanner.nextInt(); //Read another vertex of the edge
validateVertex(b);
if(a == b) throw new IllegalArgumentException("Self Loop is Detected"); //Determine whether there is a self-loop edge
if(adj[a].contains(b)) throw new IllegalArgumentException("Parallel Edges are Detected"); //Determine whether parallel l edges exist
adj[a].add(b);
adj[b].add(a);
}
}
catch (IOException e){<!-- -->
e.printStackTrace();
}
}
private void validateVertex(int v){<!-- -->
if(v < 0 || v >= V)
throw new IllegalArgumentException("vertex" + v + "is invalid");
}
public int V(){<!-- -->
return V;
}
public int E(){<!-- -->
return E;
}
public boolean hasEdge(int v, int w){<!-- -->
validateVertex(v);
validateVertex(w);
return adj[v].contains(w);
}
public Iterable<Integer> adj(int v){<!-- --> // It can be a TreeSet, but arrays, linked lists, and red-black trees all implement the Iterable interface, so they can be written uniformly like this
validateVertex(v);
return adj[v];
}
public int degree(int v){<!-- -->
validateVertex(v);
return adj[v].size(); // Iterable has no size() method
}
@Override
public String toString(){<!-- -->
StringBuilder sb = new StringBuilder();
sb.append(String.format("V = %d, E = %d\
", V, E));
for (int i = 0; i < V; i + + ) {<!-- -->
sb.append(String.format("%d:",i));
for (int w: adj[i]) {<!-- -->
sb.append(String.format("%d ",w));
}
sb.append('\
');
}
return sb.toString();
}
public static void main(String[] args){<!-- -->
AdjSet adjSet = new AdjSet("g1.txt"); //Create a new adjacency matrix and initialize it from the file content
System.out.println(adjSet);
}
}
5.3 Adjacency Matrix-LinkedList
package Chapt01_Adjacency;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
public class AdjMatrix {<!-- -->
private int V;
private int E;
private int[][] adj;
//Constructor, initialize the adjacency matrix from the file content
public AdjMatrix(String filename){<!-- -->
File file = new File(filename);
try(Scanner scanner = new Scanner(file)){<!-- -->
V = scanner.nextInt(); //Read the first number in the first line, which represents the number of vertices in the graph
if(V < 0) throw new IllegalArgumentException("V must be non-negative");
adj = new int[V][V]; //Construct adjacency matrix
E = scanner.nextInt(); //Read the second number in the first line, which represents the number of edges in the graph
if(E < 0) throw new IllegalArgumentException("E must be non-negative");
// E is the number of edges, expressed as the E line starting from the second line in g.txt
for (int i = 0; i < E; i + + ) {<!-- -->
int a = scanner.nextInt(); //Read a vertex of the edge
validateVertex(a);
int b = scanner.nextInt(); //Read another vertex of the edge
validateVertex(b);
if(a == b) throw new IllegalArgumentException("Self Loop is Detected"); //Determine whether there is a self-loop edge
if(adj[a][b] == 1) throw new IllegalArgumentException("Parallel Edges are Detected"); //Determine whether there are parallel l edges
adj[a][b] = 1; //If there is an edge, set it to 1
adj[b][a] = 1;
}
}
catch (IOException e){<!-- -->
e.printStackTrace();
}
}
private void validateVertex(int v){<!-- -->
if(v < 0 || v >= V)
throw new IllegalArgumentException("vertex" + v + "is invalid");
}
public int V(){<!-- -->
return V;
}
public int E(){<!-- -->
return E;
}
public boolean hasEdge(int v, int w){<!-- -->
validateVertex(v);
validateVertex(w);
return adj[v][w] == 1;
}
public ArrayList<Integer> adj(int v){<!-- -->
validateVertex(v);
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i < V; i + + ) {<!-- -->
if(adj[v][i] == 1) res.add(i);
}
return res;
}
public int degree(int v){<!-- -->
return adj(v).size(); //adj(v) is the adj method above, size() is the interface of ArrayList
}
// Used to print the adjacency matrix on the console
@Override
public String toString(){<!-- -->
StringBuilder sb = new StringBuilder();
sb.append(String.format("V = %d, E = %d\
", V, E)); //Print the number of vertices and edges
for (int i = 0; i < V; i + + ) {<!-- --> //line
for (int j = 0; j < V; j + + ) {<!-- --> //Column
sb.append(String.format("%d",adj[i][j])); //Read the value of the matrix
}
sb.append('\
'); //Newline at end of line
}
return sb.toString(); //Return the adjacency matrix
}
public static void main(String[] args){<!-- -->
AdjMatrix adjMatrix = new AdjMatrix("g1.txt"); //Create a new adjacency matrix and initialize it from the file content
System.out.println(adjMatrix);
}
}
5.4 Input files
7 9 0 1 0 3 1 2 1 6 twenty three 2 5 3 4 4 5 5 6