Graph Theory Basics and Representation
1. Concept and Introduction
Graph Theory is a branch of discrete mathematics, a discipline that studies graphs.
A graph is a mathematical structure used to model pairwise relationships between objects, composed of "nodes" or "vertices" (Vertex) and the "edges" (Edge) that connect these vertices.
It is worth noting that the vertex set of a graph cannot be empty, but the edge set can be empty. A graph may be undirected, meaning that the edges in the graph do not distinguish direction when connecting vertices. Otherwise, the graph is called directed. The left figure below is a typical undirected graph structure, while the right figure is a directed graph. The graphs introduced in this chapter are all undirected graphs.
Classification of graphs: unweighted graphs and weighted graphs. Whether the edges connecting nodes have numerical values associated with them; if so, it is a weighted graph; otherwise, it is an unweighted graph.
Graph Connectivity:In graph theory, the connected graph is based on the concept of connectivity. In an undirected graph G, if there is a path connecting vertex i to vertex j (of course there must also be a path from j to i), then i and j are said to be connected. If G is a directed graph, then all edges in the path connecting i and j must be in the same direction. If any two vertices in the graph are connected, the graph is called a connected graph. If the graph is directed, it is called a strongly connected graph (note: paths must exist in both directions). The connectivity of a graph is a fundamental property of graphs.
Complete graph:A complete graph is a simple undirected graph in which exactly one edge connects each pair of distinct vertices.
Self-loop edge:The start and end points of an edge are vertices.
Parallel edge:Multiple edges exist between two vertices.
II. Applicability Notes
Graphs can be used to model many types of relationships and processes in physical, biological, social, and information systems, and many practical problems can be represented by graphs. Therefore, graph theory has become a powerful mathematical tool for many disciplines such as operations research, cybernetics, information theory, network theory, game theory, physics, chemistry, biology, social sciences, linguistics, and computer science. When emphasizing its application to real-world systems, a network is sometimes defined as a graph in which relationships between attributes (such as names) are associated in the form of nodes and/or edges.
3. Graph Representation Forms
Adjacency matrix:1 indicates connected, 0 indicates not connected.
Adjacency list:Only represents information about vertices connected to a vertex
Adjacency list is suitable for representing sparse graphs.
Adjacency matrix is suitable for representing dense graphs.
Java Example Code
Source Code Package Download:Download
(1) Adjacency Matrix
src/example/graph/DenseGraph.java file code:
/**
* Adjacency matrix
*/
public class DenseGraph {
// Node count
private int n;
// Edge count
private int m;
// Whether it is a directed graph
private boolean directed;
// Specific data of the graph
private boolean[][] g;
// constructor
public DenseGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g is initialized as an n*n boolean matrix, each g[i][j] is false, indicating no edges
// false is the default value for boolean variables
g = new boolean[n][n];
}
// Return the number of nodes
public int V(){ return n;}
// Return the number of edges
public int E(){ return m;}
// Add an edge to the graph
public void addEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
if( hasEdge( v , w ) )
return;
g[v][w] = true;
if( !directed )
g[w][v] = true;
m ++;
}
// Verify whether there is an edge from v to w in the graph
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
return g[v][w];
}
}
(2) Adjacency List
src/example/graph/SparseGraph.java file code:
import java.util.Vector;
/**
* Adjacency list
*/
public class SparseGraph {
// Node count
private int n;
// Edge count
private int m;
// Whether it is a directed graph
private boolean directed;
// Specific data of the graph
private Vector<Integer>[] g;
// constructor
public SparseGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g is initialized as n empty vectors, meaning each g[i] is empty, i.e., no edges
g = (Vector<Integer>[])new Vector[n];
for(int i = 0 ; i < n ; i ++)
g[i] = new Vector<Integer>();
}
// Return the number of nodes
public int V(){ return n;}
// Return the number of edges
public int E(){ return m;}
// Add an edge to the graph
public void addEdge( int v, int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
g[v].add(w);
if( v != w && !directed )
g[w].add(v);
m ++;
}
// Verify whether there is an edge from v to w in the graph
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
for( int i = 0 ; i < g[v].size() ; i ++ )
if( g[v].elementAt(i) == w )
return true;
return false;
}
}