Data Structures - Graph
A graph is a more general nonlinear data structure used to represent complex "many-to-many" relationships between elements, consisting of vertices and edges connecting the vertices.
Basic Concepts of Graphs
Graph TypesGraph Types — Undirected Graph, Directed Graph, Weighted Graph
Undirected Graph
0
—1
Edges have no direction; connections are reciprocal.
Example: Social network friend relationships
Example: Social network friend relationships
Directed Graph
0
→1
Edges have direction; connections are one-way.
Example: Following relationships, web page links
Example: Following relationships, web page links
Weighted Graph
0
51
Edges carry weights (distance/cost)
Example: Map navigation, network latency
Example: Map navigation, network latency
Graph Storage Methods
Comparison of Storage MethodsAdjacency Matrix vs Adjacency List
Adjacency Matrix
Space ComplexityO(V²)
Check if two vertices are connectedO(1)
Traverse adjacent verticesO(V)
Suitable for: Dense graphs · int graph[V][V]
Adjacency List
Space ComplexityO(V+E)
Check if two vertices are connectedO(degree)
Traverse adjacent verticesO(degree)
Suitable for: Sparse graphs · Array of linked lists
Graph Traversal
DFS vs BFS — Traversal Starting from Vertex 0
DFS Depth-First
0→
1→
3→
4→
2→
5
Go along one path to the end and then backtrack
Implementation: Recursion / Stack | Suitable for path search, topological sorting
BFS Breadth-First
0→
1→
2→
3→
4→
5
Expand layer by layer; nodes at the same level are visited first
Implementation: Queue | Naturally suited for shortest paths in unweighted graphs
Examples
#include <stdio.h>
#include <stdbool.h>
#define V 6 /* number of vertices */
/* Graph represented by adjacency matrix */
int graph[V][V] = {
{0,1,1,0,0,0}, /* Adjacency relations of vertex 0 */
{1,0,0,1,1,0}, /* Vertex 1 */
{1,0,0,0,1,0}, /* Vertex 2 */
{0,1,0,0,0,1}, /* Vertex 3 */
{0,1,1,0,0,1}, /* Vertex 4 */
{0,0,0,1,1,0} /* Vertex 5 */
};
bool visited[V];
/* DFS: Depth-First Search, recursive implementation Features: Goes along one path to the end and backtracks, suitable for path search and connectivity checking */
/* Visit current vertex */
void DFS(int v) {
visited[v] = true;
printf("%d ", v); /* Recursively visit unvisited adjacent vertices */
for (int i = 0; i < V; i++) {
if (graph[v][i] && !visited[i]) {
DFS(i); /* BFS: Breadth-First Search, implemented using a queue Features: Expands layer by layer, naturally suitable for finding shortest paths */
}
}
}
/* Enqueue starting vertex */
/* Dequeue */
void BFS(int start) {
bool visited[V] = {false};
int queue[V];
int front = 0, rear = 0;
visited[start] = true;
queue[rear++] = start; /* Enqueue adjacent vertices */
while (front < rear) {
int v = queue[front++]; /* Initialize visited flags */
printf("%d ", v);
for (int i = 0; i < V; i++) {
if (graph[v][i] && !visited[i]) {
visited[i] = true;
queue[rear++] = i; "DFS (starting from vertex 0): "
}
}
}
}
int main() {
/* Output: 0 1 3 5 4 2 */
for (int i = 0; i < V; i++) visited[i] = false;
printf("BFS (starting from vertex 0): ");
DFS(0); /* Output: 0 1 2 3 4 5 */
printf("\n");
printf(Graph Application Scenarios);
BFS(0); Scenarios
printf("\n");
return 0;
}
#include <stdbool.h>
#define V 6 /* number of vertices */
/* Graph represented by adjacency matrix */
int graph[V][V] = {
{0,1,1,0,0,0}, /* Adjacency relations of vertex 0 */
{1,0,0,1,1,0}, /* Vertex 1 */
{1,0,0,0,1,0}, /* Vertex 2 */
{0,1,0,0,0,1}, /* Vertex 3 */
{0,1,1,0,0,1}, /* Vertex 4 */
{0,0,0,1,1,0} /* Vertex 5 */
};
bool visited[V];
/* DFS: Depth-First Search, recursive implementation Features: Goes along one path to the end and backtracks, suitable for path search and connectivity checking */
/* Visit current vertex */
void DFS(int v) {
visited[v] = true;
printf("%d ", v); /* Recursively visit unvisited adjacent vertices */
for (int i = 0; i < V; i++) {
if (graph[v][i] && !visited[i]) {
DFS(i); /* BFS: Breadth-First Search, implemented using a queue Features: Expands layer by layer, naturally suitable for finding shortest paths */
}
}
}
/* Enqueue starting vertex */
/* Dequeue */
void BFS(int start) {
bool visited[V] = {false};
int queue[V];
int front = 0, rear = 0;
visited[start] = true;
queue[rear++] = start; /* Enqueue adjacent vertices */
while (front < rear) {
int v = queue[front++]; /* Initialize visited flags */
printf("%d ", v);
for (int i = 0; i < V; i++) {
if (graph[v][i] && !visited[i]) {
visited[i] = true;
queue[rear++] = i; "DFS (starting from vertex 0): "
}
}
}
}
int main() {
/* Output: 0 1 3 5 4 2 */
for (int i = 0; i < V; i++) visited[i] = false;
printf("BFS (starting from vertex 0): ");
DFS(0); /* Output: 0 1 2 3 4 5 */
printf("\n");
printf(Graph Application Scenarios);
BFS(0); Scenarios
printf("\n");
return 0;
}
Graph Application Scenarios
| Shortest Path | Dijkstra, Bellman-Ford (map navigation) |
|---|---|
| Minimum Spanning Tree | Prim, Kruskal (network cabling optimization) |
| Topological Sorting | Kahn's algorithm (task dependency analysis) |
| Social Network Analysis | PageRank, community detection |
| Other Extensions | AI thinking... |