一、有关图的思维导图

二、图的相关知识点

1.图的基本概念

图的定义

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

图的相关概念和术语

无向边

若顶点vi到vj之间没有方向,则称这条边为无向边，有无序偶对(vi,vj)来表示。

无向图

如果图中任意两个顶点之间的边都是无向边，则称该图为无向图

有向边

若从顶点vi到vj的边有方向为有向边，也称为弧,用 有序偶< vi, vj> 来表示，vi称为弧尾，vj称为弧头。

有向图

如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。

简单图

在图中,如果不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。

无向完全图

在无向图，如果任意两个顶点之间都有存在边，则称该图为无向完全图。

有向完全图

在有向图中，如果任意两个顶点之间都存在互为相反的弧，则称该图为有向完全图

稀疏图&稠密图

有很少的边或弧的图称为稀疏图，反之称为稠密图

权:有些图的边或者弧具有与他相关的数字，这个相关的数称为权

网

这种边带权值的图叫网

2.图的存储结构和基本运算算法

图的存储结构

邻接矩阵

邻接矩阵用两个数组保存数据。一个一维数组存储图中顶点信息，一个二维数组存储图中边或弧的信息。

邻接矩阵的表示

其他存储结构

邻接表 十字链表 邻接多重表

图的算法实现

图的结构体创建

typedef struct {
  VexType vexs[MAXVEXNUM];//点的集合
  ArcCell arcs[MAXVEXNUM][MAXVEXNUM];//边的集合
  int vexNum, arcNum;
}MyGraph;