图数据结构
什么是图？
图是一种抽象数据类型 (ADT)，由一组通过链接相互连接的对象组成。互连的对象用称为顶点的点表示，连接顶点的链接称为边。
形式上，图是一对集合(V, E)，其中V是顶点的集合，E是连接顶点对的边的集合。看一下下面的图 −
在上图中，
V = {a, b, c, d, e
E = {ab, ac, bd, cd, de
图的数据结构
数学图可以用数据结构来表示。我们可以使用一个顶点数组和一个二维边数组来表示图。在继续之前，让我们先熟悉一些重要的术语 −
顶点 − 图中的每个节点都表示为一个顶点。在下面的例子中，带标签的圆圈代表顶点。因此，A 到 G 是顶点。我们可以使用数组来表示它们，如下图所示。其中，A 可以用索引 0 标识。B 可以用索引 1 标识，依此类推。
边 − 边表示两个顶点之间的路径或线。在下面的例子中，从 A 到 B、从 B 到 C 等等的线表示边。我们可以使用二维数组来表示数组，如下图所示。其中，AB 可以在第 0 行第 1 列表示为 1，BC 在第 1 行第 2 列表示为 1，依此类推，其他组合保留为 0。
邻接 − 如果两个节点或顶点通过边相互连接，则它们是相邻的。在以下示例中，B 与 A 相邻，C 与 B 相邻，依此类推。
路径 − 路径表示两个顶点之间的一系列边。在以下示例中，ABCD 表示从 A 到 D 的路径。
图的操作
图的主要操作包括创建具有顶点和边的图，以及显示该图。然而，使用图执行的最常见和最流行的操作之一是遍历，即按特定顺序访问图中的每个顶点。
图中有两种类型的遍历 −
深度优先搜索遍历
深度优先搜索是一种遍历算法，它按图的深度递减顺序访问图的所有顶点。在该算法中，选择任意一个节点作为起点，通过标记未访问的相邻节点来回遍历图，直到所有顶点都标记完毕。
DFS 遍历使用堆栈数据结构来跟踪未访问的节点。
点击并查看深度优先搜索遍历
广度优先搜索遍历
广度优先搜索是一种遍历算法，它会先访问图中某一深度层级的所有顶点，然后再移动到下一层级。在该算法中，选择一个任意节点作为起点，通过访问同一深度级别的相邻顶点并标记它们来遍历图，直到没有剩余顶点。
DFS 遍历使用队列数据结构来跟踪未访问的节点。
点击并查看广度优先搜索遍历
图的表示
在表示图时，我们必须仔细描述图中存在的元素（顶点和边）及其之间的关系。从图形上讲，图是用一组有限的节点及其之间的连接线来表示的。但是，我们也可以用其他最常用的方式来表示图，例如 −
邻接矩阵
邻接表
邻接矩阵
邻接矩阵是一个 V x V 矩阵，其值填充为 0 或 1。如果 Vi 和 Vj 之间存在链接，则记录为 1；否则，为 0。
对于下图，我们构造一个邻接矩阵 −
邻接矩阵为 −
邻接表
邻接表是图中与其他顶点直接相连的顶点的列表。
邻接表为−
图的类型
图有两种基本类型 −
有向图
无向图
有向图，顾名思义，由指向顶点或远离顶点的边组成。无向图的边完全无向。
有向图
无向图
生成树
生成树是无向图的子集，它包含图中所有顶点，且这些顶点与图中的最小边数相连。确切地说，生成树的边是原始图中边的子集。
如果图中所有顶点都是连通的，则至少存在一棵生成树。一个图中可能存在多棵生成树。
属性
生成树不存在任何环路。
任何顶点都可以从任何其他顶点到达。
示例
下图中，突出显示的边构成一棵生成树。
最小生成树
最小生成树 (MST) 是连通加权无向图的边的子集，它将所有顶点以尽可能最小的总边权重连接在一起。要生成最小生成树 (MST)，可以使用 Prim 算法或 Kruskal 算法。因此，本章将讨论 Prim 算法。
正如我们所讨论的，一个图可能有多棵生成树。如果有 n 个顶点，则生成树应该有 n - l1 条边。在这种情况下，如果图的每条边都与一个权重相关联，并且存在多棵生成树，我们需要找到该图的最小生成树。
此外，如果存在任何重复的加权边，则该图可能有多棵最小生成树。
在上图中，我们展示了一棵生成树，尽管它不是最小生成树。这棵生成树的成本为 (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) ", i, ptr->end);
ptr = ptr->next;
}
printf ("
");
}
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 << ") ";
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;
}
}
// 图类
public class Graph {
// 邻接表节点
static class vertex {
int v;
vertex(int v) {
this.v = v;
}
};
// 定义邻接表来表示图
List<List<vertex>> adj_list = new ArrayList<>();
//图形构造器
public Graph(List<Edge> edges){
// 邻接表内存分配
for (int i = 0; i < edges.size(); i++)
adj_list.add(i, new ArrayList<>());
// 将边添加到图中
for (Edge e : edges){
// 在邻接表中从源节点到目标节点分配新节点
adj_list.get(e.src).add(new vertex(e.dest));
}
}
public static void main (String[] args) {
// 定义图的边
List<Edge> edge = 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 = new Graph(edges);
// 将图打印为邻接表
int src = 0;
int lsize = graph.adj_list.size();
System.out.println("创建的图为： ");
while (src < lsize) {
//遍历邻接表并打印边
for (vertex edge : graph.adj_list.get(src)) {
System.out.print(src + " -> " + edge.v + " ");
}
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 代码
V5
#图中的最大顶点数
#声明顶点
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=" ")
ptr = ptr.next
print()
输出
The graph created is: (0 -> 3) (0 -> 2) (0 -> 1) (1 -> 4) (1 -> 2) (2 -> 3) (2 -> 4) (3 -> 1)
