数据结构基础：P6.5-图(一)---＞小白专场：如何建立图-C语言实现

数据结构基础：P6.5-图(一)---＞小白专场：如何建立图-C语言实现

本系列文章为浙江大学陈越、何钦铭数据结构学习笔记，前面的系列文章链接如下：
数据结构基础：P1-基本概念
数据结构基础：P2.1-线性结构—＞线性表
数据结构基础：P2.2-线性结构—＞堆栈
数据结构基础：P2.3-线性结构—＞队列
数据结构基础：P2.4-线性结构—＞应用实例：多项式加法运算
数据结构基础：P2.5-线性结构—＞应用实例：多项式乘法与加法运算-C实现
数据结构基础：P3.1-树(一)—＞树与树的表示
数据结构基础：P3.2-树(一)—＞二叉树及存储结构
数据结构基础：P3.3-树(一)—＞二叉树的遍历
数据结构基础：P3.4-树(一)—＞小白专场：树的同构-C语言实现
数据结构基础：P4.1-树(二)—＞二叉搜索树
数据结构基础：P4.2-树(二)—＞二叉平衡树
数据结构基础：P4.3-树(二)—＞小白专场：是否同一棵二叉搜索树-C实现
数据结构基础：P4.4-树(二)—＞线性结构之习题选讲：逆转链表
数据结构基础：P5.1-树(三)—＞堆
数据结构基础：P5.2-树(三)—＞哈夫曼树与哈夫曼编码
数据结构基础：P5.3-树(三)—＞集合及运算
数据结构基础：P5.4-树(三)—＞入门专场：堆中的路径
数据结构基础：P5.5-树(三)—＞入门专场：File Transfer
数据结构基础：P6.1-图(一)—＞什么是图
数据结构基础：P6.2-图(一)—＞图的遍历
数据结构基础：P6.3-图(一)—＞应用实例：拯救007
数据结构基础：P6.4-图(一)—＞应用实例：六度空间

文章目录

一、邻接矩阵表示的图结点的结构二、邻接矩阵表示的图-初始化三、邻接矩阵表示的图-插入边四、邻接矩阵表示的图-建立图五、邻接表表示的图结点的结构六、邻接表表示的图-建立图

---

一、邻接矩阵表示的图结点的结构

关于图的所有算法的实现都有一个前提，就是首先你得有一个图。我们前面讲到，图主要有两种表示方法，一种是邻接矩阵来表示图，一种是用邻接表来表示图。那我们先从简单的开始来考虑一下，用邻接矩阵表示的图在程序里面怎么写出来。

1、用邻接矩阵表示图非常简单，主要就是一个矩阵G[i][j]，在程序里对应一个二维的数组。对于无权图，如果结点 V i {{rm{V}}_{rm{i}}} Vi​和 V j rm{V_j} Vj​有一条边的话，那么对应第[i][j]这个元素就等于1，如果没有边的话就等于0。

2、这个数组的大小MaxVertaxNum由图里所有顶点的数量来决定的。这个二维数组的类型定义为WeightType，这是一个抽象的写法，大多数情况下他就是个整型的，这个根据具体的情况自己到前面去定义。

WeightType G[MaxVertexNum][MaxVertexNum];

3、还有两个很重要变量要定义，一个是它的顶点数，一个是它的边数。

int Nv; 
int Ne; 

4、有时候图中每个结点都有特定的意义，因此需要一个数组存放顶点数据。另外，在大型项目中都将图封装成一个结构。最后将MGraph定义成指向图的指针，因为函数传指针较方便。

typedef struct GNode *PtrToGNode;
struct GNode {
	WeightType G[MaxVertexNum][MaxVertexNum];
	int Nv; 
	int Ne; 
	DataType Data[MaxVertexNum]; 
};
typedef PtrToGNode MGraph; 

二、邻接矩阵表示的图-初始化

建立一个图的过程实际上是由两步组成的，第一步就是初始化一个有多个顶点但是没有边的图。我们知道一个图里面可以一条边都没有，但是不能一个顶点都没有。那么在给定了顶点的个数以后我们就可以实现这样一个函数，叫CreateGraph，初始化一个有VertexNum个顶点但没有边的图。

typedef int Vertex; 
MGraph CreateGraph( int VertexNum )
{ 
	//把这个 v 和 w 定义为是顶点类型
	Vertex V, W;
	MGraph Graph;
	Graph = (MGraph)malloc(sizeof(struct GNode));  //分配内存，创建一个图
	Graph->Nv = VertexNum;  //顶点数
	Graph->Ne = 0;    //边为0
	
	for (V=0; VNv; V++)  //初始化为0，代表两个点之间没关系
		for (W=0; WNv; W++) 
			Graph->G[V][W] = 0; 
	return Graph; 
}

三、邻接矩阵表示的图-插入边

接下来要做的动作就是每次向这个图里面插入一条边。那么现在我们的问题又来了，就是首先你得有一条边。这个边的类型可以模仿刚才那个图结点的定义，里面包含了连接的两个顶点与权重。在插入边时，直接对相应位置的元素赋值即可。

typedef struct ENode *PtrToENode;
struct ENode {
	Vertex V1, V2; 
	WeightType Weight; 
};
typedef PtrToENode Edge

void InsertEdge( MGraph Graph, Edge E )
{
	
	Graph->G[E->V1][E->V2] = E->Weight; 
	
	Graph->G[E->V2][E->V1] = E->Weight;
}

四、邻接矩阵表示的图-建立图

在实现完了前面两个函数之后，我们就准备好完整地建立一个用邻接矩阵表示的图了。

MGraph BuildGraph()
{ 
	MGraph Graph; //声明一个图
	Edge E;       //声明一条边
	Vertex V;     //声明顶点数据
	int Nv, i;    //Nv为定点数，iwei控制循环地遍历
	scanf("%d", &Nv);
	Graph = CreateGraph(Nv);   //创建一个有Nv个结点的图
	scanf("%d", &(Graph->Ne)); //读入边数，如果不为0，则开始创建便
	if ( Graph->Ne != 0 ) {
		E = (Edge)malloc(sizeof(struct ENode)); 
		for (i=0; iNe; i++) {
			//读入一条边的信息
			scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); 
			//插入边
			InsertEdge( Graph, E );
		}
	} 
	
	for (V=0; VNv; V++) 
		scanf(" %c", &(Graph->Data[V]));
	return Graph;
} 

看到这里我们便想：真的有必要这么麻烦吗？如果是在考试的状态下，你只有非常短的时间去建立一个图的话，其实只要这么一小段代码就可以了。

int G[MAXN][MAXN], Nv, Ne;
void BuildGraph()
{ 
	int i, j, v1, v2, w;
	scanf("%d", &Nv);
	
	for (i=0; i 

 
五、邻接表表示的图结点的结构 
当我们在使用邻接表定义图的结点的时候，其实大部分内容都跟前面是一样的。就是它也得有顶点数、边数，然后把这个邻接表方式存储的图类型定义为指向这个结点的指针。在前面，结点中含有邻接矩阵，而这里就是邻接表。
 
typedef struct GNode *PtrToGNode;
struct GNode { 
	int Nv; 
	int Ne; 
	AdjList G; 
};
 
这个邻接表其实是个数组，数字大小就是我们的顶点数。数组中每一个元素都是一个结点，我们取个名字叫VNode。结点里头首先要包含一个指针，表示指向第一个结点的边。有的情况下每一个顶点还要存一堆乱七八糟的东西的话，那么我们再定义一个Data。
 
typedef struct Vnode{
	PtrToAdjVNode FirstEdge;
	DataType Data; 
} AdjList[MaxVertexNum]; 

 
接下来我们再来看这个链表里头代表每一条边的PtrToAdjVNode。虽然说它代表的是一条边，但是它不需要存两个顶点，因为它必定是放在某一个顶点的链表里，所以我们只需要存它的邻接点。
 
typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode {
	Vertex AdjV; 
	WeightType Weight; 
	PtrToAdjVNode Next; 
};
 

 
六、邻接表表示的图-建立图 
1、初始化一个有VertexNum个顶点但没有边的图
 建立LGraph过程跟建立MGraph的过程从原理上来讲是一样的，都是先初始化一个包含了所有的顶点但是一条边都没有的一个图，然后再一条边一条边地插到这个图里面，只不过细节略微有点区别。对于LGraph来说，没有边代表每一个顶点跟着那个链表都是空的，对于这个Graph里的邻接表的每一个顶点V来说，它的指向第一条边的指针FirstEdge都是空的。
 
typedef int Vertex; 
LGraph CreateGraph( int VertexNum )
{ 
	Vertex V, W;
	LGraph Graph;
	Graph = (LGraph)malloc(sizeof(struct GNode)); 
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
	
	for ( V=0; VNv; V++ )
	Graph->G[V].FirstEdge = NULL;
	return Graph; 
}
 

 
2、 向LGraph中插入边
 插入边的过程就是把一个顶点插到一个链表里面去的过程。如下图所示，现在我要插入V1到V2这条边，从实现的角度讲显然是插在这个链表的头部是最简单的。先建立一个新的结点V2，然后让其Next指向G[V1]的FirstEdge，最后让G[V1]的FirstEdge指向V2。
 
 对应代码如下：
 
void InsertEdge( LGraph Graph, Edge E )
{ 
	PtrToAdjVNode NewNode;
	
	
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode->AdjV = E->V2;
	NewNode->Weight = E->Weight;
	
	NewNode->Next = Graph->G[E->V1].FirstEdge;
	Graph->G[E->V1].FirstEdge = NewNode;
	
	
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode->AdjV = E->V1;
	NewNode->Weight = E->Weight;
	
	NewNode->Next = Graph->G[E->V2].FirstEdge;
	Graph->G[E->V2].FirstEdge = NewNode;
}
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5702682.html