Graph Theory Basics: Concepts, Storage, and Traversal (DFS & BFS)

1. Graph Concepts

A graph consists of a finite non‑empty set of vertices and a set of edges connecting them. A vertex represents a data element, while an edge represents a logical relationship, which may be directed or undirected and can carry a weight (e.g., distance or cost).

Undirected Graph

In an undirected graph, every edge has no direction, meaning traversal is possible in both directions between the two incident vertices.

Directed Graph

In a directed graph, each edge has a direction, indicating that traversal follows the arrow; a directed edge from vi to vj cannot be traversed from vj to vi unless a separate edge is defined.

2. Graph Storage

Common storage schemes are adjacency matrices and adjacency lists. An adjacency matrix offers simple lookup but wastes space for sparse graphs, while an adjacency list saves space for sparse graphs but is less straightforward for dense graphs.

Adjacency Matrix

Implemented as a two‑dimensional array where entry (i, j) indicates connectivity (0 for no edge, non‑zero for an edge, possibly storing weight).

Undirected Graph Storage

Each undirected edge is stored as two directed edges: one from vertex 1 to vertex 2 and another from vertex 2 to vertex 1.

Directed Graph Storage

Edges are stored directly as directed connections in the matrix.

Adjacency List

Each vertex maintains a list of outgoing edges. The following Java classes illustrate the representation:

// Vertex
class POS{
    public POS(int head){
        this.head = head;
    }
    public int head; // points to the first edge
}
// Edge
class Edge{
    public int v;      // target vertex
    public int next;   // index of next edge in the list
}

// Graph initialization
int top = 0; // edge counter
List
posList = new ArrayList<>();
List
edgeList = new ArrayList<>();
for(int i = 0; i <= posSize; i++){
    posList.add(new POS(-1));
    hadVisited[i] = false;
}

// Add an edge (u -> v) to the adjacency list
public void Add_Edge(int u, int v){
    Edge edge = new Edge();
    edge.v = v;
    edge.next = posList.get(u).head;
    posList.get(u).head = top;
    edgeList.add(edge);
    top++;
}

3. Graph Traversal

Depth‑First Search (DFS)

DFS explores as far as possible along each branch before backtracking, typically implemented recursively.

// DFS
public void dfsVisit(int u){
    for(int i = posList.get(u).head; i != -1; i = edgeList.get(i).next){
        Edge edge = edgeList.get(i);
        if(!hadVisited[edge.v]){
            System.out.println("Visit node:" + edge.v);
            hadVisited[edge.v] = true;
            dfsVisit(edge.v);
        }
    }
}

Breadth‑First Search (BFS)

BFS uses a queue to explore vertices level by level, starting from a given source vertex.

public void bfsVisit(int u){
    Queue
queue = new LinkedList<>();
    queue.add(u);
    System.out.println("Visit node=" + u);
    while(!queue.isEmpty()){
        int p = queue.poll();
        for(int i = posList.get(p).head; i != -1; i = edgeList.get(i).next){
            Edge edge = edgeList.get(i);
            if(!hadVisited[edge.v]){
                hadVisited[edge.v] = true;
                System.out.println("Visit node=" + edge.v);
                queue.add(edge.v);
            }
        }
    }
}