Introduction
In graph theory, a directed graph is a graph structure with directional relationships between nodes. In practical applications, we often need to represent and operate directed graphs. In order to improve efficiency, we can dynamically select appropriate data structures for representation based on the size of the graph and the frequency of operations.
Adjacency list vs adjacency matrix
Adjacency list
An adjacency list is a data structure used to represent graphs by maintaining a list of adjacent nodes for each node. This representation is suitable for sparse graphs, which can save a lot of memory space while efficiently traversing the neighboring nodes of each node.
Advantages:
- It is space efficient and suitable for representing sparse graphs.
- Efficiently traverse each node’s neighboring nodes.
Disadvantages:
- Finding a specific edge is less efficient and requires traversing a list of adjacent nodes.
Adjacency matrix
The adjacency matrix is another data structure used to represent graphs. It describes the connection relationships between nodes through a two-dimensional matrix. This representation is suitable for dense graphs and can efficiently find the presence or absence of specific edges.
Advantages:
- Efficiently find the presence or absence of a specific edge.
- Suitable for representing dense graphs.
Disadvantages:
- It is less space efficient and consumes a lot of memory space.
Design advantages of the AdaptiveGraph class
The AdaptiveGraph class is a graph class that dynamically chooses to use an adjacency matrix or an adjacency list based on the number of nodes and the number of edges added. It makes full use of the advantages of adjacency lists and adjacency matrices and can dynamically switch between the two according to actual needs.
Advantages
-
Dynamic selection algorithm: Dynamically selects an appropriate representation based on the number of nodes and the number of edges added, taking into account space and time efficiency.
-
Save memory: When the number of nodes is small, the adjacency matrix representation is automatically selected to save memory space. When the number of nodes increases, switching to adjacency list representation avoids memory waste.
-
Efficient operation: According to the current representation, efficiency is guaranteed in operations such as adding edges and finding adjacent nodes.
Example code
//Create an AdaptiveGraph object
AdaptiveGraph graph = new AdaptiveGraph(10);
//Add directed edge
graph.addEdge(0, 1);
graph.addEdge(0, 3);
graph.addEdge(1, 2);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(4, 5);
graph.addEdge(5, 4);
graph.addEdge(5, 6);
List<Integer> adjacentNodes = graph.getAdjacentNodes(0);
// Get all non-adjacent edges
List<Edge> nonAdjacentEdges = graph.getAllNonAdjacentEdges();
//Print all non-adjacent edges
System.out.println("All non-adjacent edges:");
for (Edge edge : nonAdjacentEdges) {<!-- -->
System.out.println(edge);
}
//Print the representation of the graph
graph.printGraph();
// Perform a depth-first search
List<List<Integer>> paths = graph.depthFirstSearch(0, 6);
System.out.println("Depth first search path from 0 to 6:");
for (List<Integer> path : paths) {<!-- -->
System.out.println(path);
}
for (Edge nonAdjacentEdge : nonAdjacentEdges) {<!-- -->
List<List<Integer>> paths2 = graph.depthFirstSearch(nonAdjacentEdge.source, nonAdjacentEdge.destination);
if (!paths2.isEmpty()) {<!-- -->
System.out.println("Depth first search path from " + nonAdjacentEdge.source + " to " + nonAdjacentEdge.destination + ":");
for (List<Integer> path : paths2) {<!-- -->
System.out.println(path);
}
}
}
Conclusion
The AdaptiveGraph class provides a flexible and efficient solution for representing and operating directed graphs. By dynamically selecting appropriate data structures, it not only saves memory, but also ensures the efficiency of operations. In actual applications, the most appropriate representation method can be selected according to specific scenarios and requirements to achieve the best performance.
Okay, here is a simple documentation example, including class introduction, constructor, method description and example usage:
AdaptiveGraph documentation
AdaptiveGraph is a class used to represent a directed graph, which dynamically chooses to use an adjacency matrix or an adjacency list based on the number of nodes and the number of edges added. This class can dynamically switch between the two representations according to actual needs to ensure optimal utilization of memory and performance.
Constructor
public AdaptiveGraph(int initialCapacity)
- Description: Construct an AdaptiveGraph object.
- Parameters:
initialCapacity: The initial capacity of the graph, used to initialize the size of the adjacency matrix or adjacency list.
- Example:
AdaptiveGraph graph = new AdaptiveGraph(10);
Method
public void addEdge(int source, int destination)
- Description: Add directed edges to the graph.
- Parameters:
source: The starting node of the edge.destination: The destination node of the edge.
- Example:
graph.addEdge(0, 1);
public List getAdjacentNodes(int node)
- Description: Get the neighbor node list of the specified node.
- Parameters:
node: node index.
- Return value: List of adjacent nodes.
- Example:
List<Integer> adjacentNodes = graph.getAdjacentNodes(0);
public void printGraph()
- Description: Prints a representation of the graph, including an adjacency matrix or adjacency list.
- Example:
graph.printGraph();
Example usage
//Create an AdaptiveGraph object AdaptiveGraph graph = new AdaptiveGraph(10); //Add directed edge graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 3); graph.addEdge(2, 4); // Get the list of adjacent nodes List<Integer> adjacentNodes = graph.getAdjacentNodes(0); //Print the representation of the graph graph.printGraph();
Complete code
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* The representation class of the graph is dynamically selected to use adjacency matrix or adjacency list representation based on the number of nodes and the number of edges added.
*/
public class AdaptiveGraph {
private final int numVertices; // Number of nodes in the graph
private boolean useAdjacencyMatrix; // Mark whether to use adjacency matrix
private int[][] adjacencyMatrix; // Adjacency matrix representation
private List> adjacencyList; // Adjacency list representation
private int edgeCount; // counter for the number of times added edges
private final Set vertices; // Save all vertices in the graph
/**
* Constructor, automatically chooses to use adjacency matrix or adjacency list representation based on the number of nodes.
*
* @param numVertices The number of nodes in the graph
*/
public AdaptiveGraph(int numVertices) {
this.numVertices = numVertices;
this.useAdjacencyMatrix = numVertices <= 10; // Use adjacency matrix representation by default
this.edgeCount = 0;
this.vertices = new HashSet<>();
if (useAdjacencyMatrix) {
adjacencyMatrix = new int[numVertices][numVertices]; // Initialize the adjacency matrix
} else {
adjacencyList = new ArrayList<>(numVertices); // Initialize the adjacency list
for (int i = 0; i < numVertices; i + + ) {
adjacencyList.add(new ArrayList<>());
}
}
}
/**
* Add directed edges to the graph.
*
* @param source the starting node of the edge
* @param destination The target node of the edge
*/
public void addEdge(int source, int destination) {
vertices.add(source);
vertices.add(destination);
if (edgeCount > 100 & amp; & amp; useAdjacencyMatrix) {
switchToAdjacencyList(); // If the number of edges added exceeds 100 times and the adjacency matrix is currently used, switch to the adjacency list representation.
}
if (useAdjacencyMatrix) {
adjacencyMatrix[source][destination] = 1; // Mark directed edges in the adjacency matrix
} else {
adjacencyList.get(source).add(destination); // Add a directed edge to the adjacency list
}
edgeCount + + ;
}
/**
* Switch to adjacency list representation.
*/
private void switchToAdjacencyList() {
useAdjacencyMatrix = false;
adjacencyList = new ArrayList<>(numVertices);
for (int i = 0; i < numVertices; i + + ) {
adjacencyList.add(new ArrayList<>());
for (int j = 0; j < numVertices; j + + ) {
if (adjacencyMatrix[i][j] == 1) {
adjacencyList.get(i).add(j); // Add edges in the original adjacency matrix to the adjacency list
}
}
}
adjacencyMatrix = null; // Release the memory of the adjacency matrix
}
/**
* Get the list of adjacent nodes of the specified node.
*
* @param node node index
* @return adjacent node list
*/
public List getAdjacentNodes(int node) {
if (useAdjacencyMatrix) {
List adjacentNodes = new ArrayList<>();
for (int i = 0; i < numVertices; i + + ) {
if (adjacencyMatrix[node][i] == 1) {
adjacentNodes.add(i); // Find adjacent nodes in the adjacency matrix
}
}
return adjacentNodes;
} else {
return adjacencyList.get(node); // Return the list of adjacent nodes in the adjacency list
}
}
/**
* Print the representation of the graph.
*/
public void printGraph() {
if (useAdjacencyMatrix) {
System.out.println("Adjacency Matrix:");
for (int[] row : adjacencyMatrix) {
for (int value : row) {
System.out.print(value + " ");
}
System.out.println();
}
} else {
System.out.println("Adjacency List:");
for (int i = 0; i < adjacencyList.size(); i + + ) {
System.out.print(i + " -> ");
for (int neighbor : adjacencyList.get(i)) {
System.out.print(neighbor + " ");
}
System.out.println();
}
}
}
public static void main(String[] args) {
//Create an AdaptiveGraph object
AdaptiveGraph graph = new AdaptiveGraph(10);
//Add directed edge
graph.addEdge(0, 1);
graph.addEdge(0, 3);
graph.addEdge(1, 2);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(4, 5);
graph.addEdge(5, 4);
graph.addEdge(5, 6);
List<Integer> adjacentNodes = graph.getAdjacentNodes(0);
// Get all non-adjacent edges
List nonAdjacentEdges = graph.getAllNonAdjacentEdges();
//Print all non-adjacent edges
System.out.println("All non-adjacent edges:");
for (Edge edge : nonAdjacentEdges) {
System.out.println(edge);
}
//Print the representation of the graph
graph.printGraph();
// Perform depth first search
List> paths = graph.depthFirstSearch(0, 6);
System.out.println("Depth first search path from 0 to 6:");
for (List path : paths) {
System.out.println(path);
}
for (Edge nonAdjacentEdge : nonAdjacentEdges) {
List> paths2 = graph.depthFirstSearch(nonAdjacentEdge.source, nonAdjacentEdge.destination);
if (!paths2.isEmpty()) {
System.out.println("Depth first search path from " + nonAdjacentEdge.source + " to " + nonAdjacentEdge.destination + ":");
for (List path : paths2) {
System.out.println(path);
}
}
}
}
/**
* Get all non-adjacent edges.
*
* @return non-adjacent edge list
*/
public List getAllNonAdjacentEdges() {
List nonAdjacentEdges = new ArrayList<>();
for (int i = 0; i < vertices.size() - 1; i + + ) {
for (int j = i + 1; j < vertices.size(); j + + ) {
// Check if the source node and target node exist in the graph and they are not adjacent
if (areVerticesInGraph(i, j) & amp; & amp; !areVerticesAdjacent(i, j)) {
nonAdjacentEdges.add(new Edge(i, j));
}
}
}
return nonAdjacentEdges;
}
private boolean areVerticesInGraph(int vertex1, int vertex2) {
return vertex1 >= 0 & amp; & amp; vertex1 < vertices.size() & amp; & amp; vertex2 >= 0 & amp; & amp; vertex2 < vertices.size();
}
private boolean areVerticesAdjacent(int vertex1, int vertex2) {
if (useAdjacencyMatrix) {
return adjacencyMatrix[vertex1][vertex2] == 1;
} else {
return adjacencyList.get(vertex1).contains(vertex2) || adjacencyList.get(vertex2).contains(vertex1);
}
}
// Depth first search
public List> depthFirstSearch(int start, int end) {
List path = new ArrayList<>();
List> allPath = new ArrayList<>();
// Hash table, used to record the vertices that have been visited
Set visited = new HashSet<>();
dfs(start, end, visited, path, allPath);
return allPath;
}
private void dfs(int start, int end, Set visited, List path, List> allPath) {
visited.add(start); // Mark the current node as visited
path.add(start); // Add the current node to the path
// If the current node is the end point, add the path to the results list
if (start == end) {
// Note: A new ArrayList object needs to be created here, otherwise the path variable in subsequent recursive calls will be modified.
allPath.add(new ArrayList<>(path));
} else {
//Get the adjacent nodes of the current node
List adjacentNodes = getAdjacentNodes(start);
for (Integer adjacentNode : adjacentNodes) {
// If the adjacent node has not been visited, call dfs recursively
if (!visited.contains(adjacentNode)) {
dfs(adjacentNode, end, visited, path, allPath);
}
}
}
// During the backtracking process, restore the status of the current node so that it can correctly return to the previous layer.
// If the access status of the node is not restored during the backtracking process, the node will be regarded as visited in subsequent searches, resulting in the inability to access the node's neighbor nodes again.
visited.remove(start);
path.remove(path.size() - 1);
}
/**
* Edge class, used to represent edges in the graph.
*/
public static class Edge {
int source;
int destination;
public Edge(int source, int destination) {
this.source = source;
this.destination = destination;
}
@Override
public String toString() {
return source + " - " + destination;
}
}
}