图——“多对多”的逻辑结构

1.什么是图？

图包含：

2.图的基本术语

无向图：

有向图：

权重：边上的数字

度：

邻接点：

完全图：

3.图的抽象数据类型定义

4.怎么在程序中表示一个图？

邻接矩阵表示法（稠密图）

邻接表表示法（稀疏图）

5.图的建立C语言实现

邻接矩阵式

邻接表式

1.什么是图？

表示“多对多”的关系。

其实线性表和树可以看作简化的图。

图包含：

一组顶点：通常用V（Vertex）表示顶点集合

一组边：通常用E（Edge）表示边的集合

●边是顶点对：( v , w )∈ E ，其中 v , w ∈ V

●有向边< v , w >表示从v指向w的边（单行线）

●不考虑重边和自回路

2.图的基本术语

无向图：

有向图：

权重：边上的数字

网络：带权重的有向/无向图

度：

对于无向图：一个点所有的边数。

对于有向图：从该点出发的边数叫“出度”，指向该点的边数叫“入度”

邻接点：

有边直接相连的顶点

完全图：

完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。

3.图的抽象数据类型定义

名字：图（Graph）

数据对象集：G( V, E )由一个非空的有限顶点集合V和一个有限边集合E组成。

操作集合：对于任意图G∈Graph，以及v∈V，e∈E 。

Graph Create()：建立并返回空图；

Graph InsertVertex(Graph G , Vertex v)：将v插入G;

Graph InsertEdge（Graph G , Edge e）：将e挿入G;

void DES( Graph G , Vertex v )：从顶点v出发深度优先遍历图G;

void BES( Graph G , Vertex v )：从顶点v出发宽度优先遍历图G;

void ShortestPath( Graph G, Vertex v ,int Dist [ ] ): 计算图G中顶点v到任意其他顶点的最短距离；

void MST( GraphG )：计算图G的最小生成树；

…

4.怎么在程序中表示一个图？

“并不是只有以下两种方法，而是取决于图的特点来选取表示方法。”

邻接矩阵表示法（稠密图）

图的邻接矩阵表示法就是开一个二维数组G[ i ][ j ]，凡是两个顶点(v1,v2)之间有边时就将G[v1][v2]的值置为1。否则为0。

注：对于无向图 G[v1][v2]=1 且 G[v2][v1]=1

对于有向图 G[v1][v2]=1 但 G[v2][v1]=0

图示：

结构体定义：

typedef struct GNode *PtrToGNode;
struct GNode {WeightType G[MaxVertexNum][MaxVertexNum];int Nv; /* 顶点数 */int Ne; /* 边数 */DataType Data[MaxVertexNum]; /* 存顶点的数据 */
}
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */

优点：

直观、简单、好理解

方便检查任意一对顶点间是否存在边

方便找任一顶点的所有“邻接点”（有边直接相连的顶点）

方便计算任一顶点的“度”（从该点发出的边数为“出度”，指向该点的边数为“入度”）

-无向图：对应行（或列）非 0元素的个数

-有向图：对应行非 0元素的个数是“出度”；对应列非 0元素的个数是“入度”

缺点：

浪费空间 —— 存稀疏图（点很多而边很少）有大量无效元素

对稠密图（特别是完全图）还是很合算的

浪费时间 —— 统计稀疏图中一共有多少条边

邻接表表示法（稀疏图）

邻接表：G[N]为指针数组，对应矩阵每行一个链表，只存非 0元素

图示：就是把邻接矩阵表示的每一行抽出来做链表，去掉0元素。

结构体定义：

typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode {Vertex AdjV; /* 邻接点下标 */WeightType Weight; /* 边权重 */PtrToAdjVNode Next;
};
/* AdjVNode是邻接表中结点类型 */typedef struct Vnode{PtrToAdjVNode FirstEdge;DataType Data; /* 存顶点的数据 */
} AdjList[MaxVertexNum];
/* AdjList是邻接表类型 */typedef struct GNode *PtrToGNode;
struct GNode {int Nv; /* 顶点数 */int Ne; /* 边数 */AdjList G; /* 邻接表 */
};
typedef PtrToGNode LGraph;
/* 以邻接表方式存储的图类型 */

优点：

方便找任一顶点的所有“邻接点”

节约稀疏图的空间

需要 N个头指针 + 2E个结点（每个结点至少 2个域）

方便计算任一顶点的“度”？

对无向图：是的

对有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”

缺点：

不方便检查任意一对顶点存在边。

5.图的建立C语言实现

邻接矩阵式

#include <stdio.h>
#include <stdlib.h>#define MaxVertexNum 100typedef int WeightType;
typedef int DataType;typedef struct GNode {WeightType G[MaxVertexNum][MaxVertexNum];int Nv; /* 顶点数 */int Ne; /* 边数 */DataType Data[MaxVertexNum]; /* 存顶点的数据 */
} *PtrToGNode;typedef PtrToGNode MGraph;typedef int Vertex;
typedef struct {Vertex V1, V2;WeightType Weight;
} Edge;// 创建并返回一个空图
MGraph Create() {MGraph graph = (MGraph)malloc(sizeof(struct GNode));if (graph == NULL) {printf("无法分配内存！\n");exit(1);}graph->Nv = 0;graph->Ne = 0;int i; for (i = 0; i < MaxVertexNum; i++) {int j;for (j = 0; j < MaxVertexNum; j++) {graph->G[i][j] = 0;}}return graph;
}// 将顶点v插入图G
MGraph InsertVertex(MGraph G, Vertex v) {if (G->Nv >= MaxVertexNum) {printf("顶点数已达到最大值！\n");return G;}G->Data[G->Nv] = v;G->Nv++;return G;
}// 将边e插入图G
MGraph InsertEdge(MGraph G, Edge e) {if (e.V1 >= G->Nv || e.V2 >= G->Nv) {printf("边的顶点超出范围！\n");return G;}G->G[e.V1][e.V2] = e.Weight;G->G[e.V2][e.V1] = e.Weight; // 无向图的边，需对称赋值G->Ne++;return G;
}int main() {MGraph G = Create();G = InsertVertex(G, 1);G = InsertVertex(G, 2);G = InsertVertex(G, 3);Edge e1 = {0, 1, 10};Edge e2 = {1, 2, 20};G = InsertEdge(G, e1);G = InsertEdge(G, e2);printf("图的顶点数：%d， 边数：%d\n", G->Nv, G->Ne);int i;for (i = 0; i < G->Nv; i++) {int j;for (j = 0; j < G->Nv; j++) {if (G->G[i][j] != 0) {printf("边(%d, %d) 权重: %d\n", i, j, G->G[i][j]);}}}free(G);return 0;
}

邻接表式

#include <stdio.h>
#include <stdlib.h>#define MaxVertexNum 100typedef int WeightType;
typedef int DataType;
typedef int Vertex;typedef struct AdjVNode {Vertex AdjV;       // 邻接点下标WeightType Weight; // 边权重struct AdjVNode *Next;
} *PtrToAdjVNode;typedef struct Vnode {PtrToAdjVNode FirstEdge;DataType Data; // 存顶点的数据
} AdjList[MaxVertexNum];typedef struct GNode {int Nv; // 顶点数int Ne; // 边数AdjList G; // 邻接表
} *PtrToGNode;typedef PtrToGNode LGraph;typedef struct {Vertex V1, V2; // 边的两个顶点WeightType Weight; // 边的权重
} Edge;// 创建并返回一个空图
LGraph Create() {LGraph graph = (LGraph)malloc(sizeof(struct GNode));if (graph == NULL) {printf("无法分配内存！\n");exit(1);}graph->Nv = 0;graph->Ne = 0;int i;for (i = 0; i < MaxVertexNum; i++) {graph->G[i].FirstEdge = NULL;}return graph;
}// 将顶点v插入图G
LGraph InsertVertex(LGraph G, DataType v) {if (G->Nv >= MaxVertexNum) {printf("顶点数已达到最大值！\n");return G;}G->G[G->Nv].Data = v;G->Nv++;return G;
}// 将边e插入图G
LGraph InsertEdge(LGraph G, Edge e) {if (e.V1 >= G->Nv || e.V2 >= G->Nv) {printf("边的顶点超出范围！\n");return G;}PtrToAdjVNode newNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));if (newNode == NULL) {printf("无法分配内存！\n");exit(1);}newNode->AdjV = e.V2;newNode->Weight = e.Weight;newNode->Next = G->G[e.V1].FirstEdge;G->G[e.V1].FirstEdge = newNode;// 如果是无向图，也需要添加对称的边PtrToAdjVNode newNode2 = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));if (newNode2 == NULL) {printf("无法分配内存！\n");exit(1);}newNode2->AdjV = e.V1;newNode2->Weight = e.Weight;newNode2->Next = G->G[e.V2].FirstEdge;G->G[e.V2].FirstEdge = newNode2;G->Ne++;return G;
}int main() {LGraph G = Create();G = InsertVertex(G, 1);G = InsertVertex(G, 2);G = InsertVertex(G, 3);Edge e1 = {0, 1, 10};Edge e2 = {1, 2, 20};G = InsertEdge(G, e1);G = InsertEdge(G, e2);printf("图的顶点数：%d， 边数：%d\n", G->Nv, G->Ne);int i;for (i = 0; i < G->Nv; i++) {printf("顶点 %d 的邻接点：", i);PtrToAdjVNode node = G->G[i].FirstEdge;while (node != NULL) {printf(" (%d, %d)", node->AdjV, node->Weight);node = node->Next;}printf("\n");}// 释放内存int j;for (j = 0; j < G->Nv; j++) {PtrToAdjVNode node = G->G[j].FirstEdge;while (node != NULL) {PtrToAdjVNode temp = node;node = node->Next;free(temp);}}free(G);return 0;
}