图数据结构
什么是图？
图是一种抽象数据类型 (ADT)，它由一组通过链接相互连接的对象组成。这些相互连接的对象由称为 vertices 的点表示，连接这些顶点的链接称为 edges。
形式上，图是由一对集合 (V, E) 组成的，其中 V 是顶点集合，E 是连接顶点对的边集合。请看下面的图 −
在上面的图中，
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
图数据结构
数学图可以用数据结构表示。我们可以使用顶点数组和二维边数组来表示图。在继续之前，让我们熟悉一些重要术语 −
Vertex − 图的每个节点都表示为一个顶点。在下面的示例中，带标签的圆圈表示顶点。因此，A 到 G 是顶点。我们可以使用数组来表示它们，如下图所示。这里 A 可以通过索引 0 识别，B 可以通过索引 1 识别，以此类推。
Edge − 边表示两个顶点之间的路径或两个顶点之间的线。在下面的示例中，从 A 到 B、B 到 C 等线表示边。我们可以使用二维数组来表示数组，如下图所示。这里 AB 可以表示为行 0、列 1 处的 1，BC 表示为行 1、列 2 处的 1，以此类推，其他组合保持为 0。
Adjacency − 如果两个节点或顶点通过边连接，则它们是相邻的。在下面的示例中，B 与 A 相邻，C 与 B 相邻，以此类推。
Path − 路径表示两个顶点之间的一系列边。在下面的示例中，ABCD 表示从 A 到 D 的路径。
图的操作
图的主要操作包括创建带有顶点和边的图，以及显示该图。然而，使用图执行的最常见和最流行的操作之一是 Traversal，即按照特定顺序访问图的每个顶点。
图中有两种遍历类型 −
深度优先搜索遍历
广度优先搜索遍历
深度优先搜索遍历
深度优先搜索是一种遍历算法，它按照深度递减的顺序访问图的所有顶点。在该算法中，选择一个任意节点作为起点，并通过标记未访问的相邻节点来来回遍历图，直到所有顶点都被标记。
DFS 遍历使用 stack 数据结构来跟踪未访问的节点。
点击查看深度优先搜索遍历
广度优先搜索遍历
广度优先搜索是一种遍历算法，它在移动到下一个深度级别之前，先访问当前深度级别的所有顶点。在该算法中，选择一个任意节点作为起点，并通过访问同一深度级别的相邻顶点并标记它们来遍历图，直到没有顶点剩下。
BFS 遍历使用 queue 数据结构来跟踪未访问的节点。
点击查看广度优先搜索遍历
图的表示
在表示图时，我们必须仔细描绘图中存在的元素（顶点和边）及其之间的关系。从图像上讲，图由一组有限的节点及其之间的连接链路表示。然而，我们也可以用其他最常用的方式来表示图，例如 −
邻接矩阵
邻接表
邻接矩阵
邻接矩阵是一个 V x V 的矩阵，其值填充为 0 或 1。如果 Vi 和 Vj 之间存在链路，则记录为 1；否则为 0。
对于下面的给定图，让我们构造一个邻接矩阵 −
邻接矩阵为 −
邻接表
邻接表是图中直接连接到其他顶点的顶点列表。
邻接表为 −
图的类型
图有两种基本类型 −
有向图
无向图
有向图，正如其名称所示，由具有方向的边组成，该方向要么从顶点出发，要么指向顶点。无向图的边则完全没有方向。
有向图
无向图
生成树
生成树是无向图的一个子集，它包含图的所有顶点，并使用图中最少的边数将它们连接起来。精确地说，生成树的边是原始图中边的子集。
如果图中的所有顶点都连通，则至少存在一个生成树。在一个图中，可能存在多个生成树。
性质
生成树不包含任何环。
可以从任意顶点到达其他任意顶点。
示例
在下面的图中，高亮的边形成了一个生成树。
最小生成树
最小生成树 (MST) 是连通加权无向图的边的一个子集，它将所有顶点连接在一起，并具有可能的最小总边权重。要推导 MST，可以使用 Prim 算法或 Kruskal 算法。因此，本章将讨论 Prim 算法。
正如我们所讨论的，一个图可能有多个生成树。如果有 n 个顶点，则生成树应有 n − 1 条边。在这种情况下，如果图的每条边都关联有一个权重，并且存在多个生成树，我们需要找到图的最小生成树。
此外，如果存在任何重复加权的边，则图可能有多个最小生成树。
在上面的图中，我们展示了一个生成树，尽管它不是最小生成树。该生成树的成本为 (5+7+3+3+5+8+3+4)=38。
最短路径
图中的最短路径定义为从一个顶点到另一个顶点的成本最小路线。这在加权有向图中最常见，但也适用于无向图。
图中最短路径的一个流行现实世界应用是地图。导航通过各种最短路径算法变得更容易和更简单，其中目的地被视为图的顶点，路线则是边。两种常见的最短路径算法是 −
Dijkstra 最短路径算法
Bellman Ford 最短路径算法
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <stdlib.h>
#include <stdlib.h>
#define V 5
// 图中顶点最大数量
struct graph {
// 声明图数据结构
struct vertex *point[V];
};
struct vertex {
// 声明顶点
int end;
struct vertex *next;
};
struct Edge {
// 声明边
int end, start;
};
struct graph *create_graph (struct Edge edges[], int x){
int i;
struct graph *graph = (struct graph *) malloc (sizeof (struct graph));
for (i = 0; i < V; i++) {
graph->point[i] = NULL;
}
for (i = 0; i < x; i++) {
int start = edges[i].start;
int end = edges[i].end;
struct vertex *v = (struct vertex *) malloc (sizeof (struct vertex));
v->end = end;
v->next = graph->point[start];
graph->point[start] = v;
}
return graph;
}
int main (){
struct Edge edges[] = { {0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 4}, {2, 4}, {2, 3}, {3, 1} };
int n = sizeof (edges) / sizeof (edges[0]);
struct graph *graph = create_graph (edges, n);
printf("The graph created is: ");
for (int i = 0; i < V; i++) {
struct vertex *ptr = graph->point[i];
while (ptr != NULL) {
printf ("(%d -> %d)\t", i, ptr->end);
ptr = ptr->next;
}
printf ("\n");
}
return 0;
}
输出
The graph created is: (1 -> 3) (1 -> 0) (2 -> 1) (2 -> 0) (3 -> 2) (3 -> 0) (4 -> 2) (4 -> 1)
#include <bits/stdc++.h>
using namespace std;
#define V 5
// 图中顶点最大数量
struct graph {
// 声明图数据结构
struct vertex *point[V];
};
struct vertex {
// 声明顶点
int end;
struct vertex *next;
};
struct Edge {
// 声明边
int end, start;
};
struct graph *create_graph (struct Edge edges[], int x){
int i;
struct graph *graph = (struct graph *) malloc (sizeof (struct graph));
for (i = 0; i < V; i++) {
graph->point[i] = NULL;
}
for (i = 0; i < x; i++) {
int start = edges[i].start;
int end = edges[i].end;
struct vertex *v = (struct vertex *) malloc (sizeof (struct vertex));
v->end = end;
v->next = graph->point[start];
graph->point[start] = v;
}
return graph;
}
int main (){
struct Edge edges[] = { {0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 4}, {2, 4}, {2, 3}, {3, 1} };
int n = sizeof (edges) / sizeof (edges[0]);
struct graph *graph = create_graph (edges, n);
int i;
cout<<"The graph created is: ";
for (i = 0; i < V; i++) {
struct vertex *ptr = graph->point[i];
while (ptr != NULL) {
cout << "(" << i << " -> " << ptr->end << ")\t";
ptr = ptr->next;
}
cout << endl;
}
return 0;
}
输出
The graph created is: (1 -> 3) (1 -> 0) (2 -> 1) (2 -> 0) (3 -> 2) (3 -> 0) (4 -> 2) (4 -> 1)
import java.util.*;
// 用于存储图的边的类
class Edge {
int src, dest;
Edge(int src, int dest) {
this.src = src;
this.dest = dest;
}
}
// Graph 类
public class Graph {
// 邻接表中的节点
static class vertex {
int v;
vertex(int v) {
this.v = v;
}
};
// 定义邻接表来表示图
List<List<vertex>> adj_list = new ArrayList<>();
// Graph 构造函数
public Graph(List<Edge> edges){
// 邻接表内存分配
for (int i = 0; i < edges.size(); i++)
adj_list.add(i, new ArrayList<>());
// 将边添加到图中
for (Edge e : edges){
// 在邻接表中从 src 到 dest 分配新节点
adj_list.get(e.src).add(new vertex(e.dest));
}
}
public static void main (String[] args) {
// 定义图的边
List<Edge> edges = Arrays.asList(new Edge(0, 1),new Edge(0, 2),
new Edge(0, 3),new Edge(1, 2), new Edge(1, 4),
new Edge(2, 4), new Edge(2, 3),new Edge(3, 1));
// 调用 Graph 类构造函数来构建图
Graph graph = new Graph(edges);
// 以邻接表形式打印图
int src = 0;
int lsize = graph.adj_list.size();
System.out.println("The graph created is: ");
while (src < lsize) {
// 遍历邻接表并打印边
for (vertex edge : graph.adj_list.get(src)) {
System.out.print(src + " -> " + edge.v + "\t");
}
System.out.println();
src++;
}
}
}
输出
The graph created is: 0 -> 1 0 -> 2 0 -> 3 1 -> 2 1 -> 4 2 -> 4 2 -> 3 3 -> 1
#Python 图数据结构的代码
V = 5
#图中顶点最大数量
#声明顶点
class Vertex:
def __init__(self, end):
self.end = end
self.next = None
#声明边
class Edge:
def __init__(self, start, end):
self.start = start
self.end = end
#声明图数据结构
class Graph:
def __init__(self):
self.point = [None] * V
def create_graph(edges, x):
graph = Graph()
for i in range(V):
graph.point[i] = None
for i in range(x):
start = edges[i].start
end = edges[i].end
v = Vertex(end)
v.next = graph.point[start]
graph.point[start] = v
return graph
edges = [Edge(0, 1), Edge(0, 2), Edge(0, 3), Edge(1, 2), Edge(1, 4), Edge(2, 4), Edge(2, 3), Edge(3, 1)]
n = len(edges)
graph = create_graph(edges, n)
#Range
print("The graph created is: ")
for i in range(V):
ptr = graph.point[i]
while ptr is not None:
print("({} -> {})".format(i, ptr.end), end="\t")
ptr = ptr.next
print()
输出
The graph created is: (0 -> 3) (0 -> 2) (0 -> 1) (1 -> 4) (1 -> 2) (2 -> 3) (2 -> 4) (3 -> 1)