欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

数据结构之图的实现

程序员文章站 2024-02-29 21:56:58
...

图[graph]

目录

什么是图？

1. 图是数据关系是多对多情况下的一种数据结构，是线性结构(一对一)和树型(一对多)结构的组合

一、常见表示图的两种方法

1.用邻接矩阵表示图

[本质]

使用二维数组来表示点，以及边,再使用结构体将数据对象和操作集封装起来
数据结构之图的实现
适用情况(密集图)

[优点]

  1. 直观、简单、好理解
  2. 方便检查任意一对顶点间是否存在边
  3. 方便找任一顶点的所有“邻接点”（有边直接相连的顶点）
  4. 方便计算任一顶点的“度”（从该点发出的边数为“出度”，指向该点的边数为“入度”）

[缺点]

1.浪费空间 —— 存稀疏图（点很多而边很少）有大量无效元素，对稠密图（特别是完全图）还是很合算的
2.浪费时间 —— 统计稀疏图中一共有多少条边

邻接矩阵表示图的数据对象集

//定义指向此种类型的指针类型
typedef struct GNode *PtrToGNode;
//定义一些类型
typedef int WeightType;	//这么定义是方便实际使用的直接在这里修改，就可以改数据类型了(邻接矩阵里面的每个结点不一定存int型)
typedef int DataType;
//定义图的数据对象集
struct GNode
{
	int Nv;		//顶点数
	int Ne;		//边数
	WeightType G[MaxVertexNum][MaxVertexNum]; //邻接矩阵
	DataType Data[MaxVertexNum]; // 存顶点的数据(非必须)，将顶点的数据单独再存一个 
};				//;不能忘记
//以邻接矩阵存储的图类型指针
typedef PtrToGNode MGraph;

邻接矩阵表示图的操作集

[1]MGraph初始化

//MGraph初始化(初始化有VertexNum个顶点但没有边的图)
typedef int Vertex; // 用顶点下标表示顶点,为整型 
MGraph CreateGraph( int 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] = 0;
	return Graph; 
}

[2]MGraph插入边

//建立边的数据类型
typedef struct ENode *PtrToENode;
struct ENode 
{
	Vertex V1, V2; // 有向边<V1, V2> 
	WeightType Weight; // 权重 
};
//指向边类型的指针
typedef PtrToENode Edge;
//输入：指向图的指针、指向边的指针
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;
}

[3]完整建立一个图

输入格式：Nv Ne (V1 V2 Weight)循环

MGraph BuildGraph()
{ 
	MGraph Graph;
	Edge E;
	Vertex V;
	int Nv, i;
//MGraph点的初始化，声名点的个数
	scanf("%d", &Nv);
	Graph = CreateGraph(Nv);
//MGraph插入边，先声名边的条数，在一条一条插入 
	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); 
			InsertEdge( Graph, E );
		}
	} 
// 如果顶点有数据的话，读入数据 
for (V=0; V<Graph->Nv; V++) 
	scanf(" %c", &(Graph->Data[V]));
	return Graph;
}

2.用邻接表表示图

[本质]

使用链表嵌套链表来表示(一个链表结点可能又是另一个链表的起点)
邻接表：G[N]为指针数组，对应矩阵每行一个链表，只存非0元素
适用情况(稀疏图)

[优点]

1.方便找任一顶点的所有“邻接点”
2.节约稀疏图的空间(需要N个头指针 + 2E个结点（每个结点至少2个域）)
3.方便计算任一顶点的“度”？
【1】无向图：是
【2】有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”

[缺点]

1.不方便检查任意一对顶点是否存在边
数据结构之图的实现

邻接表表示图的数据对象集

//定义一些类型
typedef int WeightType;
//定义指向图类型的指针
typedef struct GNode *PtrToGNode
struct GNode
{
	int Nv;		//顶点数
	int Ne;		//边数
	AdjList G;	//邻接表
};				//;不能忘
//以邻接表方式存储的图类型
typedef PtrToGNode LGraph;
//定义邻接表类型(是一个数组类型)，是最外边的那个数组，这个数组的每个结点后面都根着一个链表
typedef struct Vnode
{
//边结点
	PtrToAdjVNode FirstEdge;
	DataType Data; 			// 存顶点的数据 
} AdjList[MaxVertexNum]; 	
//取了个别名为AdjList 
typedef struct AdjVNode *PtrToAdjVNode;
//定义AdjList单个结点后面连的链表结点
struct AdjVNode 
{
	Vertex AdjV; // 邻接点下标 
	WeightType Weight; // 边权重 
	PtrToAdjVNode Next; 
};

邻接表表示图的操作集

[1]LGraph初始化

//初始化一个有VertexNum个顶点但没有边的图
typedef int Vertex; // 用顶点下标表示顶点,为整型
LGraph CreateGraph( int VertexNum )
{ 
	Vertex V, W;
	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;
//其实这里相当于将AdjList的所有结点后面接的第一个都为空
	return Graph; 
}

[2]向LGraph中插入边

数据结构之图的实现

//建立边的数据类型
typedef struct ENode *PtrToENode;
struct ENode 
{
	Vertex V1, V2; // 有向边<V1, V2> 
	WeightType Weight; // 权重 
};
//指向边类型的指针
typedef PtrToENode Edge;
/***************** 插入边 <V1, V2> ****************/ 
void InsertEdge( LGraph Graph, Edge E )
{ 
//中间结点
	PtrToAdjVNode NewNode;
// 为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;
}

[3]完整地建立LGraph

本质其实和MGraph建立是一样的(只需要将MGraph改为LGraph就行)

LGraph BuildGraph()
{ 
	LGraph Graph;
	Edge E;
	Vertex V;
	int Nv, i;
//MGraph点的初始化，声名点的个数
	scanf("%d", &Nv);
	Graph = CreateGraph(Nv);
//MGraph插入边，先声名边的条数，在一条一条插入 
	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); 
			InsertEdge( Graph, E );
		}
	} 
// 如果顶点有数据的话，读入数据 
for (V=0; V<Graph->Nv; V++) 
	scanf(" %c", &(Graph->Data[V]));
	return Graph;
}

二、图的遍历(都需要具体问题具体分析)

DFS(深度遍历)(常用于邻接表图的遍历)

1.本质：树的先序遍历推广；每调用一次DFS(V)，就是把V所在的连通分量遍历了一遍

2.伪码：借助栈

数据结构之图的实现

3.如何使用栈实现？

【1】其实就是树的中序遍历扩展
【2】实例：
数据结构之图的实现

  • 创建一个数组visited表示是否访问过
  • 将函数传递进来的结点标记为已访问，且将这个结点入栈
  • 如果栈非空，则出栈一个元素，随后将此结点未访问过的邻接点，递归调用DFS。
  • 例如此图：
  • 1标记为已访问，1入栈
  • 栈非空，1出栈，遍历所有邻接点，2，3，4，5，6，7，标记为已访问，入栈
  • 栈非空，7出栈，遍历所有邻接点，17，18，19，标记，入栈
  • 栈非空，19出栈，无邻接点，18、17同理
  • 栈非空，7出栈，邻接点全部已访问
  • 栈非空，6出栈，遍历所有邻接点……递归实现
  • 最后出栈顺序DFS为，1、7、19、18、17、6、16、15、5、14、4、13、12、11、3、10、9、2、8

4.时间复杂度分析：

【1】用邻接表存储图，有O(N+E)
【2】用邻接矩阵存储图，有O(N^2)

5.代码实现

/* 邻接表存储的图 - DFS */
 
void Visit( Vertex V )
{
    printf("正在访问顶点%d\n", V);
}
/* Visited[]为全局变量，已经初始化为false */
void DFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) )
{   /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */
    PtrToAdjVNode W;
     
    Visit( V ); /* 访问第V个顶点 */
    Visited[V] = true; /* 标记V已访问 */
 
    for( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
        if ( !Visited[W->AdjV] )    /* 若W->AdjV未被访问 */
            DFS( Graph, W->AdjV, Visit );    /* 则递归访问之 */
}

BFS(深度遍历)(常用于邻接矩阵图的遍历)

1. 本质：树的层序遍历推广；每调用一次BFS(V)，就把V所在的连通分量遍历了一遍

2.伪码：借助队列

队列：只能头部删除，尾部增加(想想排队时)
Enqueue()压入队列
Dequeue()挤出队列
数据结构之图的实现

3.如何使用队列实现？

【1】其实就和树的层序遍历一样
【2】实例：数据结构之图的实现

  • 建立数组visited数组，来存是否访问的属性
  • 判断：如果一个结点被访问过，则压入队列
  • 当队列非空时，弹出队头元素，然后将此顶点的所有(未被访问的)邻接点入队，并且标记为已访问
  • 如此图：
  • 将结点1标记为已访问，1入队(这个起始节点需要传递给函数)
  • 队列非空，1出队，判断2，3，4，5，6，7邻接点均为被访问，将其标记为已访问，且入队
  • 队列非空，2出队，判断8，9邻接点未访问，标记为已访问，且入队
  • 队列非空，3出队……等(不断重复)
  • 最后按照出队顺序打印出来就是一个BFS顺序：1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19

4.时间复杂度分析：

【1】用邻接表存储图，有O(N+E)
【2】用邻接矩阵存储图，有O(N^2)

5.代码实现

/* 邻接矩阵存储的图 - BFS */
 
/* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边，即W是否V的邻接点。  */
/* 此函数根据图的不同类型要做不同的实现，关键取决于对不存在的边的表示方法。*/
/* 例如对有权图, 如果不存在的边被初始化为INFINITY, 则函数实现如下:         */
bool IsEdge( MGraph Graph, Vertex V, Vertex W )
{
    return Graph->G[V][W]<INFINITY ? true : false;
}
 
/* Visited[]为全局变量，已经初始化为false */
void BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) )
{   /* 以S为出发点对邻接矩阵存储的图Graph进行BFS搜索 */
    Queue Q;     
    Vertex V, W;
 
    Q = CreateQueue( MaxSize ); /* 创建空队列, MaxSize为外部定义的常数 */
    /* 访问顶点S：此处可根据具体访问需要改写 */
    Visit( S );
    Visited[S] = true; /* 标记S已访问 */
    AddQ(Q, S); /* S入队列 */
     
    while ( !IsEmpty(Q) ) {
        V = DeleteQ(Q);  /* 弹出V */
        for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            /* 若W是V的邻接点并且未访问过 */
            if ( !Visited[W] && IsEdge(Graph, V, W) ) {
                /* 访问顶点W */
                Visit( W );
                Visited[W] = true; /* 标记W已访问 */
                AddQ(Q, W); /* W入队列 */
            }

两种方法比较

【DFS】(递归实现)
优点
1、能找出所有解决方案
2、优先搜索一棵子树，然后是另一棵，所以和广搜对比，有着内存需要相对较少的优点
缺点
1、要多次遍历，搜索所有可能路径，标识做了之后还要取消。
【BFS】(非递归实现)
优点
1、对于解决最短或最少问题特别有效，而且寻找深度小
2、每个结点只访问一遍，结点总是以最短路径被访问，所以第二次路径确定不会比第一次短
缺点
1、内存耗费量大（需要开大量的数组单元用来存储状态）
DFS本质上使用的栈结构，而BFS使用的是队列。
当问题解离初始结点越近，这样的问题使用BFS效率较高，反之用DFS可能较好

三、与图相关的经典问题

【1】最短路径问题

【问题抽象】

在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。这条路径有起点和终点

【问题分类】

1.无权图单源最短路径(起点定，终点不定)

【1】BFS变形解决

[伪代码]

数据结构之图的实现

  • 按照递增(非递减)的顺序找出各个顶点的最短路

2.有权图的单源最短路算法

【2】Dijkstra算法

[伪代码]

数据结构之图的实现

[Dijkstra算法]
  • 令S={源点s + 已经确定了最短路径的顶点vi}
  • 对任一未收录的顶点v，定义dist[v]为s到v的最
    短路径长度，但该路径仅经过S中的顶点。即路径
    {s->(vi∈S)->v}的最小长度
    若路径是按照递增（非递减）的顺序生成的，则
  • 真正的最短路必须只经过S中的顶点
  • 每次从未收录的顶点中选一个dist最小的收录（贪心）
  • 增加一个v进入S，可能影响另外一个w的dist值！
  • dist[w] = min{dist[w], dist[v] + <v,w>的权重}
2.多源最短路径(起点，终点都不定)

【2】最小生成树

【3】拓扑排序

相关标签： 数据结构

上一篇： node的超时timeout

下一篇： 浅析Android手机卫士sim卡绑定

推荐阅读