目录
一, 图引入
二, 什么是图(Graph)
三, 抽象数据类型定义
四, 常见术语
五, 怎么在程序中表示一个图
六, 邻接矩阵
6.1 邻接矩阵的优点
6.2 邻接矩阵的缺点
6.3 邻接矩阵的代码表示
6.3.1 c 表示
6.3.2 Python 表示
七, 邻接表
7.1 邻接表的优点
7.2 邻接表的缺点
7.3 邻接表的代码表示
7.2.1 c 表示
7.3.2 Python 表示
更新, 更全的《数据结构与算法》的更新网站, 更有 python,go, 人工智能教学等着你: https://www.cnblogs.com/nickchen121/p/11407287.html
一, 图引入
相信很多同学都听说过六度空间理论(SixDegress of Separation): 只要通过 6 个人的关系网, 你就能够认识全世界所有的人. 这个理论和我们接下来要讲的图非常相似.
从上图中, 我们可以看出, 如果你认识 6 个人, 是很有可能认识其他所有人的.
但是, 对于全球的 30 亿的互联网人来说, 你真的可以全部认识吗? 大多数同学此刻一定是定神一想, 这还用问? 你是傻子吗? 这一定不可能呀. 但是对于这个问题, 我们可以用我们未来学习的图的知识解决, 啪啪打脸可真不好受, 哈哈哈!
除了上述问题, 对于下图, 我再来提出两个问题:
从陈家庄到张家村, 怎么走最快呢?
怎么修公路使得村村通的花费最少呢?
有些同学说了, 这还不简单, 让我用我的火眼金睛数一数. 但是对于下述这张图呢?
算了, 我还是街边喊 666(溜)吧!!!
二, 什么是图(Graph)
对于上述提出的几个问题, 只要你耐下性子和我修习 "图法", 相信不久之后, 你就不是路边那个只会喊 "666" 的同志, 而是挥手说 "同志们好". 那么到底什么是图呢? 记住 nick 心法: 图就是下面我讲的这个小东西. 废话~, 还不如看下图 -- 我 (灵魂画师) 手绘图:
以前我们学习的链表表示的是一对一的关系; 学的树表示一对多的关系; 而我们此次的主角, 冠勇三军的图却是大有来头, 从上图可以看出, 图表示的是多对多的关系, 通常, 它包含如下 "小弟":
一组顶点: 通常用 V(Vertex)表示顶点集合
一组边: 通常用 E(Edge)表示边的集合
边是顶点对: 即 \((v,w)\in{E}\), 其中 \(v,w\in{V}\)
无向边 \((v,w)\)表示从 v 指向 w 的边, 无箭头, 如下图所示:
有向边 \(<v,w>\)也表示从 v 指向 w 的边(单行线), 但是它有个该死的箭头, 如下图所示:
牢记: 图的边不考虑重边和自回路, 记不住现场扇自己两巴掌, 没人看的见, 如下图所示是错误的:
三, 抽象数据类型定义
我也知道枯燥, 但是你逼着自己读一遍都做不到, 大江大河等着你逛?
类型名称: 图(Graph)
数据对象集: G(V, E), 由一个非空的有限顶点集合 V 和一个有限边集合 E 组成.
操作集: 对于任意图 \(G\in{Graph}\), 以及 \(v\in{V},e\in{E}\)
Graph Create(): 建立并返回空图;
Graph InsertVertex(Graph G, Vertex v)
: 将 v 插入 G
Graph InsertEdge(Graph G, Edge e)
: 将 e 插入 G;
Void DFS(Graph G, Vertex v)
: 从顶点 v 出发深度优先 (别好奇, 继续往下看) 遍历图 G;
Void BFS(Graph G, Vertex v)
: 从顶点 v 出发宽度优先遍历图 G;
Void ShortestPath(Graph G, Vertex v, int Dist[])
: 计算图 G 中顶点 v 到任意其他顶点的最短距离;
Void MST(Graph G): 计算图 G 的最小生成树;
......, 以后都会讲到的, 别急, 现在不想弄死你, 否则你醉生梦死 (秃头) 走不动了怎么办???
四, 常见术语
你随便找一本图论的书, 图的常见术语随随便便几十页, 为了再次不让你醉生梦死, 我就例举出几个, 你看着记下就好了:
对, 你没有看错, 就这几个, 还有很多, 等以后我慢慢道来......, 弄不死你!
五, 怎么在程序中表示一个图
理论这东西怎么能符合我大 nick 的智商, 那就来一点实践的吧!
逼逼叨叨一大堆, 你倒是讲讲我们怎么在程序中表示一个图呀?
既然你选择了死亡, 那我就告诉你吧. 在程序中, 我们一般有以下两种方式表示图(这并不意味着只有两个, 多着呢!), 分别为邻接矩阵和邻接表, 下面重点戏来了, 你个戏精, 不是你想要来点实践的吗?
六, 邻接矩阵
别听到矩阵就慌了阵脚, 有我这个冠勇三军的大 nick 在, 怕啥怕, 来吧!
你可以把邻接矩阵看成一个正方形, 也可以看成一个二维平面直角坐标轴, 也可以混在一起看. 我们先来看看它长啥挫样:
不可否认的是, 这张图是有点难理解的, 但是你要重视接下来我讲的这两句话:
邻接矩阵 G[N][N]--N 个顶点从 0 到 N-1 编号
\[ G[i][j] = \begin{cases} 1\quad\text{若 $<v_i,v_j>$ 是 G 中的边} \\ 0\quad\text{否则} \\ \end{cases} \]
不理解, 私信我, 微信: a1171958281, 喷不死你!
对于上图的邻接矩阵, 其实存在一个很大的 bug, 上图的邻接矩阵是沿红线对称的, 也就是说, 我们是否可以做到如下图所示, 只要红色区域的部分呢? 这样就可以节省一半空间了, 好开心呀!
为了解决存储占用问题, 我们可以用一个长度为 \(N(N+1)/2\)的 1 维数组 A 存储,\(\{G_{00},G_{10},G_{11},\cdots,G_{n-1,0},\cdots,G_{n-1,n-1}\}\),\(G_{ij}\)在数组 A 中的下标是(一行一行数过去, 然后计算它的位置):
\[ (i*(i+1)/2+j) \]
对于边具有权重的网络 (不理解就算了), 只要把 G[i][j] 的值定义为边 \(<v_i,v_j>\)的权重即可.
6.1 邻接矩阵的优点
上面逼逼了一大堆邻接矩阵的理论, 实在让人痛苦, 那么使用邻接矩阵有啥好处呢? 好处大大的有, 有以下四点好处:
直观, 简单, 好理解, 这难道不是优点吗?/ 偷笑
方便检查任意一对顶间是否存在边
方便找任一顶点的所有邻接点(有边直接相连的顶点)
方便计算任一顶点的度(从该点触发的边数为出度, 指向该点的边数为入度)
无向图: 对应行 (或列) 非 0 元素的个数(出度就是入度呀!!!)
有向图: 对应行非 0 元素的个数是出度; 对应列非 0 元素的个数是入度
6.2 邻接矩阵的缺点
作为一个一个冠勇三军的大 nick, 不能总鼓励, 也得给点打压!
那么邻接矩阵有什么缺点呢? 缺点其实不多, 就以下两点:
浪费空间 -- 存稀疏图(点很多而便很少, 其实就是 0 很多的意思, 有大量无效元素)
对稠密图(特别是完全图 )
6.3 邻接矩阵的代码表示
逼逼了一大堆, 直接上代码吧! 为师毕生功力传给你了, 你慢慢参悟, c 和 python 版本我都给你准备好了, 但是我推荐你先看完理论再去研究代码.
6.3.1 c 表示
- /* c 语言实现 */
- /* 图的邻接矩阵表示法 */
- #define MaxVertexNum 100 /* 最大顶点数设为 100 */
- #define INFINITY 65535 /* ∞设为双字节无符号整数的最大值 65535*/
- typedef int Vertex; /* 用顶点下标表示顶点, 为整型 */
- typedef int WeightType; /* 边的权值设为整型 */
- typedef char DataType; /* 顶点存储的数据类型设为字符型 */
- /* 边的定义 */
- typedef struct ENode *PtrToENode;
- struct ENode{
- Vertex V1, V2; /* 有向边 < V1, V2> */
- WeightType Weight; /* 权重 */
- };
- typedef PtrToENode Edge;
- /* 图结点的定义 */
- typedef struct GNode *PtrToGNode;
- struct GNode{
- int Nv; /* 顶点数 */
- int Ne; /* 边数 */
- WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
- DataType Data[MaxVertexNum]; /* 存顶点的数据 */
- /* 注意: 很多情况下, 顶点无数据, 此时 Data[]可以不用出现 */
- };
- typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
- MGraph CreateGraph( int VertexNum )
- { /* 初始化一个有 VertexNum 个顶点但没有边的图 */
- Vertex V, W;
- MGraph Graph;
- Graph = (MGraph)malloc(sizeof(struct GNode)); /* 建立图 */
- Graph->Nv = VertexNum;
- Graph->Ne = 0;
- /* 初始化邻接矩阵 */
- /* 注意: 这里默认顶点编号从 0 开始, 到(Graph->Nv - 1) */
- for (V=0; V<Graph->Nv; V++)
- for (W=0; W<Graph->Nv; W++)
- Graph->G[V][W] = INFINITY;
- return Graph;
- }
- void InsertEdge( MGraph Graph, Edge E )
- {
- /* 插入边 <V1, V2> */
- Graph->G[E->V1][E->V2] = E->Weight;
- /* 若是无向图, 还要插入边 < V2, V1> */
- Graph->G[E->V2][E->V1] = E->Weight;
- }
- MGraph BuildGraph()
- {
- MGraph Graph;
- Edge E;
- Vertex V;
- int Nv, i;
- scanf("%d", &Nv); /* 读入顶点个数 */
- Graph = CreateGraph(Nv); /* 初始化有 Nv 个顶点但没有边的图 */
- scanf("%d", &(Graph->Ne)); /* 读入边数 */
- if ( Graph->Ne != 0 ) { /* 如果有边 */
- E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */
- /* 读入边, 格式为 "起点 终点 权重", 插入邻接矩阵 */
- for (i=0; i<Graph->Ne; i++) {
- scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
- /* 注意: 如果权重不是整型, Weight 的读入格式要改 */
- InsertEdge( Graph, E );
- }
- }
- /* 如果顶点有数据的话, 读入数据 */
- for (V=0; V<Graph->Nv; V++)
- scanf("%c", &(Graph->Data[V]));
- return Graph;
- }
6.3.2 Python 表示
- # python 语言实现
- # python 闭门造车版本, 没有一定实力, 你就别为难自己了
- class Graph_Matrix:
- """
- Adjacency Matrix
- """
- def __init__(self, vertices=[], matrix=[]):
- """
- :param vertices:a dict with vertex id and index of matrix , such as {vertex:index}
- :param matrix: a matrix
- """
- self.matrix = matrix
- self.edges_dict = {} # {(tail, head):weight}
- self.edges_array = [] # (tail, head, weight)
- self.vertices = vertices
- self.num_edges = 0
- # if provide adjacency matrix then create the edges list
- if len(matrix)> 0:
- if len(vertices) != len(matrix):
- raise IndexError
- self.edges = self.getAllEdges()
- self.num_edges = len(self.edges)
- # if do not provide a adjacency matrix, but provide the vertices list, build a matrix with 0
- elif len(vertices)> 0:
- self.matrix = [[0 for col in range(len(vertices))] for row in range(len(vertices))]
- self.num_vertices = len(self.matrix)
- def isOutRange(self, x):
- try:
- if x>= self.num_vertices or x <= 0:
- raise IndexError
- except IndexError:
- print("节点下标出界")
- def isEmpty(self):
- if self.num_vertices == 0:
- self.num_vertices = len(self.matrix)
- return self.num_vertices == 0
- def add_vertex(self, key):
- if key not in self.vertices:
- self.vertices[key] = len(self.vertices) + 1
- # add a vertex mean add a row and a column
- # add a column for every row
- for i in range(self.getVerticesNumbers()):
- self.matrix[i].append(0)
- self.num_vertices += 1
- nRow = [0] * self.num_vertices
- self.matrix.append(nRow)
- def getVertex(self, key):
- pass
- def add_edges_from_list(self, edges_list): # edges_list : [(tail, head, weight),()]
- for i in range(len(edges_list)):
- self.add_edge(edges_list[i][0], edges_list[i][1], edges_list[i][2], )
- def add_edge(self, tail, head, cost=0):
- # if self.vertices.index(tail)>= 0:
- # self.addVertex(tail)
- if tail not in self.vertices:
- self.add_vertex(tail)
- # if self.vertices.index(head)>= 0:
- # self.addVertex(head)
- if head not in self.vertices:
- self.add_vertex(head)
- # for directory matrix
- self.matrix[self.vertices.index(tail)][self.vertices.index(head)] = cost
- # for non-directory matrix
- # self.matrix[self.vertices.index(fromV)][self.vertices.index(toV)] = \
- # self.matrix[self.vertices.index(toV)][self.vertices.index(fromV)] = cost
- self.edges_dict[(tail, head)] = cost
- self.edges_array.append((tail, head, cost))
- self.num_edges = len(self.edges_dict)
- def getEdges(self, V):
- pass
- def getVerticesNumbers(self):
- if self.num_vertices == 0:
- self.num_vertices = len(self.matrix)
- return self.num_vertices
- def getAllVertices(self):
- return self.vertices
- def getAllEdges(self):
- for i in range(len(self.matrix)):
- for j in range(len(self.matrix)):
- if 0 <self.matrix[i][j] < float('inf'):
- self.edges_dict[self.vertices[i], self.vertices[j]] = self.matrix[i][j]
- self.edges_array.append([self.vertices[i], self.vertices[j], self.matrix[i][j]])
- return self.edges_array
- def __repr__(self):
- return str(''.join(str(i) for i in self.matrix))
- def to_do_vertex(self, i):
- print('vertex: %s' % (self.vertices[i]))
- def to_do_edge(self, w, k):
- print('edge tail: %s, edge head: %s, weight: %s' % (self.vertices[w], self.vertices[k], str(self.matrix[w][k])))
- import networkx as nx
- import matplotlib.pyplot as plt
- def draw_undircted_graph(my_graph):
- G = nx.Graph() # 建立一个空的无向图 G
- for node in my_graph.vertices:
- G.add_node(str(node))
- for edge in my_graph.edges:
- G.add_edge(str(edge[0]), str(edge[1]))
- print("nodes:", G.nodes()) # 输出全部的节点: [1, 2, 3]
- print("edges:", G.edges()) # 输出全部的边:[(2, 3)]
- print("number of edges:", G.number_of_edges()) # 输出边的数量: 1
- nx.draw(G, with_labels=True)
- plt.savefig("undirected_graph.png")
- plt.show()
- # python 语言实现
- # python 导入模块
- import networkx as nx
- import matplotlib.pyplot as plt
- import numpy as np
- G = nx.Graph()
- Matrix = np.array(
- [
- [0, 1, 1, 1, 1, 1, 0, 0], # a
- [0, 0, 1, 0, 1, 0, 0, 0], # b
- [0, 0, 0, 1, 0, 0, 0, 0], # c
- [0, 0, 0, 0, 1, 0, 0, 0], # d
- [0, 0, 0, 0, 0, 1, 0, 0], # e
- [0, 0, 1, 0, 0, 0, 1, 1], # f
- [0, 0, 0, 0, 0, 1, 0, 1], # g
- [0, 0, 0, 0, 0, 1, 1, 0] # h
- ]
- )
- # 建立一个空的无向图
- for i in range(len(Matrix)):
- for j in range(len(Matrix)):
- G.add_edge(i, j)
- nx.draw(G)
- plt.show()
七, 邻接表
好了, 吃完饭了! 可以来第二个邻接表了, 如下图所示:
对于上图的邻接表, 其中 G[N]为指针数组, 对应矩阵每行一个链表只存非 0 元素, 对于有权重的网络(以后就知道了), 结构中增加关于权重的域(多一个权重相关的值).
但是同志们, 一定要注意: 图中的顶点之间 (邻接矩阵) 一定要足够稀疏才合算呀! 否则你不就是傻子了吗?
7.1 邻接表的优点
好了, 长话短说, 邻接表就以下四个优点:
方便找任一顶点的所有邻接点
节约稀疏图的空间
需要 N 个头指针 + 2E 个结点(每个结点至少两个域, 头指针 5, 结点 9; 也有可能头指针 9, 结点 5)
方便计算任一顶点的度
无向图: 是的
有向图: 只能计算出度; 需要构造逆邻接表 (存指向自己的边) 来方便计算入度
7.2 邻接表的缺点
就一点, 不废话, 自己考虑为什么:
不方便检查任意一对顶点间是否存在边
7.3 邻接表的代码表示
逼逼了一大堆, 直接上代码吧! 为师毕生功力传给你了, 你慢慢参悟, c 和 python 版本我都给你准备好了, 但是我推荐你先看完理论再去研究代码.
7.2.1 c 表示
- /* c 语言实现 */
- /* 图的邻接表表示法 */
- #define MaxVertexNum 100 /* 最大顶点数设为 100 */
- typedef int Vertex; /* 用顶点下标表示顶点, 为整型 */
- typedef int WeightType; /* 边的权值设为整型 */
- typedef char DataType; /* 顶点存储的数据类型设为字符型 */
- /* 边的定义 */
- typedef struct ENode *PtrToENode;
- struct ENode{
- Vertex V1, V2; /* 有向边 < V1, V2> */
- WeightType Weight; /* 权重 */
- };
- typedef PtrToENode Edge;
- /* 邻接点的定义 */
- typedef struct AdjVNode *PtrToAdjVNode;
- struct AdjVNode{
- Vertex AdjV; /* 邻接点下标 */
- WeightType Weight; /* 边权重 */
- PtrToAdjVNode Next; /* 指向下一个邻接点的指针 */
- };
- /* 顶点表头结点的定义 */
- typedef struct Vnode{
- PtrToAdjVNode FirstEdge;/* 边表头指针 */
- DataType Data; /* 存顶点的数据 */
- /* 注意: 很多情况下, 顶点无数据, 此时 Data 可以不用出现 */
- } AdjList[MaxVertexNum]; /* AdjList 是邻接表类型 */
- /* 图结点的定义 */
- typedef struct GNode *PtrToGNode;
- struct GNode{
- int Nv; /* 顶点数 */
- int Ne; /* 边数 */
- AdjList G; /* 邻接表 */
- };
- typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */
- LGraph CreateGraph( int VertexNum )
- { /* 初始化一个有 VertexNum 个顶点但没有边的图 */
- Vertex V;
- LGraph Graph;
- Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立图 */
- Graph->Nv = VertexNum;
- Graph->Ne = 0;
- /* 初始化邻接表头指针 */
- /* 注意: 这里默认顶点编号从 0 开始, 到(Graph->Nv - 1) */
- for (V=0; V<Graph->Nv; V++)
- Graph->G[V].FirstEdge = NULL;
- return Graph;
- }
- void InsertEdge( LGraph Graph, Edge E )
- {
- PtrToAdjVNode NewNode;
- /* 插入边 <V1, V2> */
- /* 为 V2 建立新的邻接点 */
- NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
- NewNode->AdjV = E->V2;
- NewNode->Weight = E->Weight;
- /* 将 V2 插入 V1 的表头 */
- NewNode->Next = Graph->G[E->V1].FirstEdge;
- Graph->G[E->V1].FirstEdge = NewNode;
- /* 若是无向图, 还要插入边 <V2, V1> */
- /* 为 V1 建立新的邻接点 */
- NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
- NewNode->AdjV = E->V1;
- NewNode->Weight = E->Weight;
- /* 将 V1 插入 V2 的表头 */
- NewNode->Next = Graph->G[E->V2].FirstEdge;
- Graph->G[E->V2].FirstEdge = NewNode;
- }
- LGraph BuildGraph()
- {
- LGraph Graph;
- Edge E;
- Vertex V;
- int Nv, i;
- scanf("%d", &Nv); /* 读入顶点个数 */
- Graph = CreateGraph(Nv); /* 初始化有 Nv 个顶点但没有边的图 */
- scanf("%d", &(Graph->Ne)); /* 读入边数 */
- if ( Graph->Ne != 0 ) { /* 如果有边 */
- E = (Edge)malloc( sizeof(struct ENode) ); /* 建立边结点 */
- /* 读入边, 格式为 "起点 终点 权重", 插入邻接矩阵 */
- for (i=0; i<Graph->Ne; i++) {
- scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
- /* 注意: 如果权重不是整型, Weight 的读入格式要改 */
- InsertEdge( Graph, E );
- }
- }
- /* 如果顶点有数据的话, 读入数据 */
- for (V=0; V<Graph->Nv; V++)
- scanf("%c", &(Graph->G[V].Data));
- return Graph;
- }
7.3.2 Python 表示
- # python 语言实现
- class Vertex(object):
- # 初始化顶点
- def __init__(self, key):
- self.id = key # 初始化顶点的键
- self.connectedTo = {} # 初始化顶点的值
- # 添加邻居顶点, 参数 nbr 是邻居顶点的键, 默认权重为 0
- def addNeighbor(self, nbr, weight=0):
- self.connectedTo[nbr] = weight
- def __str__(self):
- return str(self.id) + 'connectedTo:' + str([x.id for x in self.connectedTo])
- # 获取该顶点所有邻居顶点的键
- def getConnections(self):
- return self.connectedTo.keys()
- # 获取顶点的键
- def getId(self):
- return self.id
- # 获取到某邻居顶点的权重
- def getWeight(self, nbr):
- return self.connectedTo[nbr]
- # 自定义图类
- class Graph(object):
- # 初始化图
- def __init__(self):
- self.vertList = {} # 初始化邻接表
- self.numVertices = 0 # 初始化顶点数
- # 添加顶点
- def addVertex(self, key):
- newVertex = Vertex(key) # 创建顶点
- self.vertList[key] = newVertex # 将新顶点添加到邻接表中
- self.numVertices = self.numVertices + 1 # 邻接表中顶点数 + 1
- return newVertex
- # 获取顶点
- def getVertex(self, n):
- if n in self.vertList: # 若待查询顶点在邻接表中, 则
- return self.vertList[n] # 返回该顶点
- else:
- return None
- # 使之可用 in 方法
- def __contains__(self, n):
- return n in self.vertList
- # 添加边, 参数 f 为起始顶点的键, t 为目标顶点的键, cost 为权重
- def addEdge(self, f, t, cost=0):
- if f not in self.vertList: # 起始顶点不在邻接表中, 则
- self.addVertex(f) # 添加起始顶点
- if t not in self.vertList: # 目标顶点不在邻接表中, 则
- self.addVertex(t) # 添加目标顶点
- self.vertList[f].addNeighbor(self.vertList[t], cost) # 在邻接表中添加起始点的目标点及权重
- # 获取邻接表中所有顶点的键
- def getVertices(self):
- return self.vertList.keys()
- # 迭代显示邻接表的每个顶点的邻居节点
- def __iter__(self):
- return iter(self.vertList.values())
- if __name__ == '__main__':
- g = Graph() # 实例化图类
- for i in range(6):
- g.addVertex(i) # 给邻接表添加节点
- print(g.vertList) # 打印邻接表
- g.addEdge(0, 1, 5) # 给邻接表添加边及权重
- g.addEdge(0, 5, 2)
- g.addEdge(1, 2, 4)
- g.addEdge(2, 3, 9)
- g.addEdge(3, 4, 7)
- g.addEdge(3, 5, 3)
- g.addEdge(4, 0, 1)
- g.addEdge(5, 4, 8)
- g.addEdge(5, 2, 1)
- for v in g: # 循环每个顶点
- for w in v.getConnections(): # 循环每个顶点的所有邻居节点
- print("(%s, %s)" % (v.getId(), w.getId())) # 打印顶点和其邻居节点的键
来源: https://www.cnblogs.com/nickchen121/p/11593550.html