参考博文：数据结构之图的基本概念
参考书籍：数据结构（C语言版）清华大学出版社
图的基本概念
图的定义
- 图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
- 图相比线性表和树形结构
- 在线性表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继。
- 在树型结构中，数据元素之间有着明显的层关系，并且每个元素只有一个前驱，可能有多个后继。
- 而在图形结构中，节点之间的关系可以是任意的，图中任意两个元素都有可能有关。
- 线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，我们则称之为顶点（Vertex）。
- 线性表可以没有元素，称为空表；树中可以没有节点，称为空树；但是，在图中不允许没有顶点（有穷非空性）。
- 线性表中的各元素是线性关系，树中的各元素是层次关系，而图中各顶点的关系是用边来表示（边集可以为空），这里要强调对边集概念的重视。
图的分类
- 无向图
如果图中任何两个顶点之间都是无向边，则称为该图为无向图(Undirected graphs)。 - 有向图
如果图中任意两个顶点之间的边都是有向边（简而言之就是有方向的边），则称该图为有向图（Directed graphs）。 - 完全图
①无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。（含有n个顶点的无向完全图有(n×(n-1))/2条边）
②有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。（含有n个顶点的有向完全图有n×(n-1)条边） - 稀疏图/稠密图
有很少的边或弧的图成为稀疏图，反之接近完全图的图则称为稠密图。
图相关的概念
- 顶点的度
顶点Vi的度（Degree）是指在图中与Vi相关联的边的条数。对于有向图来说，有入度（In-degree）和出度（Out-degree）之分，有向图顶点的度等于该顶点的入度和出度之和。 - 邻接（Adjacent）
- 若无向图中的两个顶点V1和V2存在一条边(V1,V2)，则称顶点V1和V2邻接。
- 若有向图中存在一条边<V3,V2>，则称顶点V3与顶点V2邻接，且是V3邻接到V2或V2邻接直V3
- 无向图中的边使用小括号“()”表示，而有向图中的边使用尖括号“<>”表示。
- 路径（Path）
- 在无向图中，若从顶点Vi出发有一组边可到达顶点Vj，则称顶点Vi到顶点Vj的顶点序列为从顶点Vi到顶点Vj的路径。
- 序列中顶点不重复出现的路径称为简单路径。
- 回路/环（Cycle/Loop）
在路径概念的基础上，第一个顶点和最后一个顶点相同的路径称为一个回路或环。 - 权（Weight）
- 有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权（Weight）。
- 权的数值储存在邻接表的弧节点内。
- 有向网/无向网
即为有权值属性的有向图/无向图
图的存储
数组表示法（邻接矩阵表示法）
图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。
- 结构体声明：
#define MAX_VERTEX_NUM 20
//图的邻接矩阵表示方式
typedef enum {DG,DN,UDG,UDN} GraphKind;
typedef struct ArcCell{
int weight; //该项对于无权图，用0或1来表示连接与否
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
int vex[MAX_VERTEX_NUM]; //构造顶点向量
AdjMatrix arcs; //图的邻接矩阵
int vexnum,arcnum; // 图当前顶点数和边数
GraphKind kind; //图的种类类型
}MGraph;
- 只声明边结构体和图结构体，无需声明顶点结构体。
- 邻接矩阵表示的是一个n个顶点与n个顶点之间n2个边情况的矩阵
- weight值
在有权图中有连接代表权值，两顶点间无连接为0，有连接表示为权值
在无权图中该位置存储边的关系，默认无连接为0，有连接为1
- 图的建立
void CreateGraph(MGraph G){
scanf("%d %d",&G.vexnum,&G.arcnum);
for(int i = 0; i < G.vexnum; i++) scanf("%d",&G.vex[i]); //构造顶点向量
for(int i = 0; i < G.vexnum; i++)
for(int j = 0; j < G.vexnum; j++) {
G.arcs[i][j].weight = 0; //初始化邻接矩阵
}
for(int k = 0; k < G.arcnum; k++){
int vex1,vex2,weight;
scanf("%d %d %d",&vex1,&vex2,&weight);
int v1,v2;
for(int i = 0; i < G.vexnum; i++){ //找到顶点在图中的下标
if(G.vex[i] == vex1){
v1 = i;
}
if(G.vex[i] == vex2){
v2 = i;
}
}
G.arcs[v1][v2].weight = weight;
G.arcs[v2][v1].weight = weight; //有向图省略此部，
}
}
邻接表（Adjacency List）
邻接表是一种图的链式存储结构。图中存储了每个表的头节点，也就是所有顶点信息，我们可以通过顶点访问到与其邻接的每条边的信息。
- 结构体声明
#define MAX_VERTEX_NUM 20
//图的邻接矩阵表示方式
typedef enum {DG,DN,UDG,UDN} GraphKind;
typedef struct ArcNode{
int adjvexNum; //该弧所指向的顶点在图的定点结构体组中的下角标
struct ArcNode *nextarc;
int weight; //该项对于无权图,可删除此项
}ArcNode;
typedef struct VexNode{
ArcNode *firstarc;
}VexNode,AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertice;
int vexnum,arcnum; // 图当前顶点数和边数
GraphKind kind; //图的种类类型
}MGraph;
- 图的建立
void CreateGraph(MGraph G){
scanf("%d %d\n",&G.vexnum,&G.arcnum);
for(int i = 0; i < G.vexnum; i++) {
G.vertice[i].firstarc = NULL;
}
for(int k = 0; k < G.arcnum; k++){
int vex1,vex2,weight;
scanf("%d %d %d\n",&vex1,&vex2,&weight);
ArcNode *arcNode = (ArcNode*)malloc(sizeof(ArcNode));
arcNode->nextarc = NULL;
arcNode->adjvexNum = vex2;
arcNode->weight = weight;
if(G.vertice[vex1].firstarc == NULL){
G.vertice[vex1].firstarc = arcNode;
}
else{
ArcNode *t = (ArcNode*)malloc(sizeof(ArcNode));
for(t = G.vertice[vex1].firstarc;t;t = t->nextarc){
}
t->nextarc = arcNode;
}
}
}
