图的基本运算算法（基于邻接表）——C/C++

一时失言乱红尘 2021-12-22 06:59 484阅读 0赞

## 一、概念 ##

图（Graph）结构是一种非线性的数据结构，图在实际生活中有很多例子，比如交通运输网，地铁网络，社交网络，计算机中的状态执行（自动机）等等都可以抽象成图结构。图结构比树结构复杂的非线性结构。

**图结构构成**  
1.顶点（vertex）：图中的数据元素。  
2.边（edge）：图中连接这些顶点的线。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]

所有的顶点构成一个顶点集合，所有的边构成边的集合，一个完整的图结构就是由顶点集合和边集合组成。图结构在数学上记为以下形式：  
G=（V,E） 或者 G=（V（G），E（G））  
其中 V（G）表示图结构所有顶点的集合，顶点可以用不同的数字或者字母来表示。E（G）是图结构中所有边的集合，每条边由所连接的两个顶点来表示。  
图结构中顶点集合V（G）不能为空，必须包含一个顶点，而图结构边集合可以为空，表示没有边。

## 二、图的类型 ##

（1）不带权的有0、1：

1.  0表示自己或与自己不相连的。
2.  1表示相连的。

（2）带权的有0、weight、∞ ：

1.  0表示自己。
2.  weight表示权值。
3.  ∞ 表示不相连的。

（3）无向：表示双方都有联系，都会显示权值。  
（4）有向：单方面显示权值（只有箭头指向方显示，被指向方不会）。

**1、不带权无向图**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

int array1[MAXV][MAXV] = {			//不带权无向图 
    		{0,1,0,1,1},
    		{1,0,1,1,0},
    		{0,1,0,1,1},
    		{1,1,1,0,1},
    		{1,0,1,1,0}
    	};

**2、不带权有向图**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 2]

int array2[MAXV][MAXV] = {			//不带权有向图 
    		{0,1,0,1,0},
    		{0,0,1,1,0},
    		{0,0,0,1,1},
    		{0,0,0,0,0},
    		{1,0,0,1,0}
    	};

**3、带权无向图**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 3]

int array3[MAXV][MAXV] = {			//带权无向图 
    		{  0,  8,INF,  5,INF},
    		{  8,  0,  3,INF,INF},
    		{INF,  3,  0,  9,  6},
    		{  5,INF,  9,  0,INF},
    		{INF,INF,  6,INF,  0}
    	};

**4、带权有向图**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 4]

int array4[MAXV][MAXV] = {			//带权有向图 
    		{  0,  8,INF,  5,INF},
    		{INF,  0,  3,INF,INF},
    		{INF,INF,  0,INF,  6},
    		{INF,INF,  9,  0,INF},
    		{INF,INF,INF,INF,  0}
    	};

## 三、基本运算算法 ##

**1、基本信息**

#define MAXV 5					//最大顶点个数 
    #define INF 32767				//定义 ∞ 
    //∞ == INF ,int 型的最大范围（2位）= 2^(2*8-1)，TC告诉我们int占用2个字节，而VC和GCC告诉我们int占用4个字节
    //图：Graph
    //顶点：Vertex
    //邻接：Adjacency
    //矩阵：Matrix
    //表：List
    //边：Edge

**2、基本函数**

//创建图的邻接表 
    void createAdjListGraph(ListGraph*& LG, int A[MAXV][MAXV], int n, int e) 
    //输出邻接表 
    void displayAdjList(ListGraph* LG)
    //输出邻接矩阵
    void displayAdjMat(MatGraph MG) 
    //邻接表转换为邻接矩阵
    void ListToMat(ListGraph* LG, MatGraph &MG)
    //邻接表转换为邻接矩阵
    void MatToList(MatGraph MG, ListGraph* &LG)
    //销毁图
    void destroyAdjListGraph(ListGraph* LG)

**3、结构体类型**  
**3.1、邻接矩阵**

#define MAXV 5					//最大顶点个数 
    #define INF 32767				//定义 ∞ 
    
    typedef struct vertex {
    	int number;					//顶点的编号 	
    }VertexType; 					//别名，顶点的类型 
    
    typedef struct matrix {
    	int n;						//顶点个数
    	int e;						//边数 
    	int adjMat[MAXV][MAXV];		//邻接矩阵数组			
    	VertexType ver[MAXV];		//存放顶点信息 
    }MatGraph;						//别名，完整的图邻接矩阵类型

**3.2、邻接表**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 5]

typedef struct eNode {
    	int adjVer;					//该边的邻接点编号 
    	int weight;					//该边的的信息，如权值 
    	struct eNode* nextEdge;		//指向下一条边的指针 
    }EdgeNode; 						//别名，边结点的类型 
    
    typedef struct vNode {
    	EdgeNode* firstEdge;		//指向第一个边结点 
    }VNode; 						//别名，邻接表的头结点类型 
    
    typedef struct list {
    	int n;						//顶点个数
    	int e;						//边数
    	VNode adjList[MAXV];		//邻接表的头结点数组 
    }ListGraph;						//别名，完整的图邻接表类型

## 四、算法实现 ##

**1、创建图的运算算法**  
根据邻接矩阵数组A、顶点个数n、边数e来建立图的邻接表 LG（采用邻接表指针方式）。  
（1）为邻接表分配LG的存储空间，并将所有头结点的firstEdge指针置为空（NULL）。  
（2）扫描数组A查找不为0的元素，若找到这样的元素A\[i\]\[j\],创建一个adjVer域为 j、weight域为A\[i\]\[j\]的边结点。  
（3）采用头插法将他插入到第 i 个单链表中。

//创建图的邻接表 
    void createAdjListGraph(ListGraph*& LG, int A[MAXV][MAXV], int n, int e) {
    	int i, j;
    	EdgeNode* p;
    	LG = (ListGraph*)malloc(sizeof(ListGraph));
    	for (i = 0; i < n; i++) {
    		LG->adjList[i].firstEdge = NULL;						//给邻接表中所有头结点指针域置初值 
    	}
    	for (i = 0; i < n; i++) {									//检查邻接矩阵中的每个元素 
    		for (j = n - 1; j >= 0; j--) {
    			if (A[i][j] != 0) {									//存在一条边 
    				p = (EdgeNode*)malloc(sizeof(EdgeNode));		//申请一个结点内存
    				p->adjVer = j;									//存放邻接点 
    				p->weight = A[i][j];							//存放权值
    				p->nextEdge = NULL;
    
    				p->nextEdge = LG->adjList[i].firstEdge;			//头插法 
    				LG->adjList[i].firstEdge = p;
    			}
    		}
    	}
    	LG->n = n;
    	LG->e = e;
    }

**2、输出邻接表**  
（1）扫描邻接表LG的头结点数组adjList.  
（2）对于每个单链表，先输出头结点的顶点信息（这里输出编号）.  
（3）然后逐一输出单链表中的所有结点的信息。

//输出邻接表 
    void displayAdjList(ListGraph* LG) {
    	int i;
    	EdgeNode* p;
    	for (i = 0; i < MAXV; i++) {
    		p = LG->adjList[i].firstEdge;
    		printf("%d:", i);
    		while (p != NULL) {
    			if (p->weight != INF) {
    				printf("%2d[%d]->", p->adjVer, p->weight);
    			}
    			p = p->nextEdge;
    		}
    		printf(" NULL\n");
    	}
    }

**3、输出邻接矩阵**  
这个就和数组的输出一样，只是要判断临界条件

//输出邻接矩阵
    void displayAdjMat(MatGraph MG) {
    	int i, j;
    	for (i = 0; i < MAXV; i++) {
    		for (j = 0; j < MAXV; j++) {
    			if (MG.adjMat[i][j] == 0) {
    				printf("%4s", "0");
    			}
    			else if (MG.adjMat[i][j] == INF) {
    				printf("%4s", "∞");
    			}
    			else {
    				printf("%4d", MG.adjMat[i][j]);
    			}
    		}
    		printf("\n");
    	}
    }

**4、邻接表转换为邻接矩阵**  
（1）初始时将邻接矩阵MG中所有对应的元素值置0.  
（2）扫描邻接表LG的所有单链表，通过第 i 个单链表查找顶点 i 的相邻节点p。  
（3）将邻接矩阵MG元素 MG.adjMat\[i\]\[p->adjVer\] 修改为该边的权 p->weight。

//邻接表转换为邻接矩阵
    void ListToMat(ListGraph* LG, MatGraph &MG) {
    	int i, j;
    	EdgeNode* p;
    	for (i = 0; i < MAXV; i++) {					//初始化置 0
    		for (j = 0; j < MAXV; j++) {
    			MG.adjMat[i][j] = 0;
    		}
    	}
    	for (i = 0; i < LG->n; i++) {					//扫描所有单链表
    		p = LG->adjList[i].firstEdge;				//p 指向第 i 个单链表的头结点
    		while (p != NULL) {							//遍历单链表
    			MG.adjMat[i][p->adjVer] = p->weight;
    			p = p->nextEdge;
    		}
    	}
    	MG.n = LG->n;
    	MG.e = LG->e;
    }

**5、邻接矩阵转换为邻接表**  
（1）在图的邻接矩阵MG查找不为0、不为 ∞ 的元素。  
（2）若找到这样的元素MG.adjMat\[i\]\[j\],创建一个adjVer域为 j、weight域为MG.adjMat\[i\]\[j\]的边结点。  
（3）采用头插法将他插入到第 i 个单链表中。

//邻接矩阵转换为邻接表 
    void MatToList(MatGraph MG, ListGraph* &LG) {
    	int i, j;
    	EdgeNode* p;
    	LG = (ListGraph*)malloc(sizeof(ListGraph));
    	for (i = 0; i < MG.n; i++) {
    		LG->adjList[i].firstEdge = NULL;						//给邻接表中所有头结点指针域置初值 
    	}
    	for (i = 0; i < MG.n; i++) {								//检查邻接矩阵中的每个元素 
    		for (j = MG.n - 1; j >= 0; j--) {
    			if (MG.adjMat[i][j] != 0) {							//存在一条边 
    				p = (EdgeNode*)malloc(sizeof(EdgeNode));		//申请一个结点内存
    				p->adjVer = j;									//存放邻接点 
    				p->weight = MG.adjMat[i][j];					//存放权值
    				p->nextEdge = NULL;
    
    				p->nextEdge = LG->adjList[i].firstEdge;			//头插法 
    				LG->adjList[i].firstEdge = p;
    			}
    		}
    	}
    	LG->n = MG.n;
    	LG->e = MG.e;
    }

**6、销毁图**  
对于邻接表LG，扫描其头结点数组adjList指向的所有单链表，逐个释放单链表中的边结点，最后释放头结点数组。

//销毁图
    void destroyAdjListGraph(ListGraph* LG) {
    	int i;
    	EdgeNode* pre, * p;
    	for (i = 0; i < LG->n; i++) {
    		pre = LG->adjList[i].firstEdge;				//挨个释放内存 
    		if (pre != NULL) {
    			p = pre->nextEdge;
    			while (p != NULL) {
    				free(pre);
    				pre = p;
    				p = p->nextEdge;
    			}
    			free(pre);
    		}
    	}
    	free(LG);
    }

## 五、结果展示 ##

**1、整体框架**

#include<stdio.h>
    #include<malloc.h>
    
    #define MAXV 5					//最大顶点个数 
    #define INF 32767				//定义 ∞ 
    
    typedef struct vertex {
    	int number;					//顶点的编号 	
    }VertexType; 					//别名，顶点的类型 
    
    typedef struct matrix {
    	int n;						//顶点个数
    	int e;						//边数 
    	int adjMat[MAXV][MAXV];		//邻接矩阵数组			
    	VertexType ver[MAXV];		//存放顶点信息 
    }MatGraph;						//别名，完整的图邻接矩阵类型
    
    typedef struct eNode {
    	int adjVer;					//该边的邻接点编号 
    	int weight;					//该边的的信息，如权值 
    	struct eNode* nextEdge;		//指向下一条边的指针 
    }EdgeNode; 						//别名，边结点的类型 
    
    typedef struct vNode {
    	EdgeNode* firstEdge;		//指向第一个边结点 
    }VNode; 						//别名，邻接表的头结点类型 
    
    typedef struct list {
    	int n;						//顶点个数
    	int e;						//边数
    	VNode adjList[MAXV];		//邻接表的头结点数组 
    }ListGraph;						//别名，完整的图邻接表类型 
    
    //创建图的邻接表 
    void createAdjListGraph(ListGraph*& LG, int A[MAXV][MAXV], int n, int e) {
    	
    }
    
    //输出邻接表 
    void displayAdjList(ListGraph* LG) {
    	
    }
    
    //输出邻接矩阵
    void displayAdjMat(MatGraph MG) {
    	
    }
    
    //邻接表转换为邻接矩阵
    void ListToMat(ListGraph* LG, MatGraph &MG) {
    	
    }
    
    //邻接矩阵转换为邻接表 
    void MatToList(MatGraph MG, ListGraph* &LG) {
    	
    }
    
    //销毁图
    void destroyAdjListGraph(ListGraph* LG) {
    
    }
    
    int main() {
    	ListGraph* LG;						//邻接表 
    	MatGraph MG;						//邻接矩阵 
    	int array1[MAXV][MAXV] = {			//不带权无向图 
    		{0,1,0,1,1},
    		{1,0,1,1,0},
    		{0,1,0,1,1},
    		{1,1,1,0,1},
    		{1,0,1,1,0}
    	};
    	int array2[MAXV][MAXV] = {			//不带权有向图 
    		{0,1,0,1,0},
    		{0,0,1,1,0},
    		{0,0,0,1,1},
    		{0,0,0,0,0},
    		{1,0,0,1,0}
    	};
    	int array3[MAXV][MAXV] = {			//带权无向图 
    		{  0,  8,INF,  5,INF},
    		{  8,  0,  3,INF,INF},
    		{INF,  3,  0,  9,  6},
    		{  5,INF,  9,  0,INF},
    		{INF,INF,  6,INF,  0}
    	};
    	int array4[MAXV][MAXV] = {			//带权有向图 
    		{  0,  8,INF,  5,INF},
    		{INF,  0,  3,INF,INF},
    		{INF,INF,  0,INF,  6},
    		{INF,INF,  9,  0,INF},
    		{INF,INF,INF,INF,  0}
    	};
    	int e = 5;
    	createAdjListGraph(LG, array1, MAXV, e);		//创建邻接表图 
    	displayAdjList(LG);								//输出邻接表 
    	printf("\n");
    
    	ListToMat(LG, MG);								//邻接表转换为邻接矩阵 
    	displayAdjMat(MG);								//输出邻接矩阵 
    	printf("\n");
    
    	MatToList(MG, LG);								//邻接矩阵转换为邻接表 
    	displayAdjList(LG);								//输出邻接表 
    	printf("\n");
    
    	return 0;
    }

2、结果图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 6]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 7]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 8]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 9]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: /images/20211220/88b200de7b7b4670a59d97fad0c410f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: /images/20211220/55167d18417d475d89b69a7ae6aa35f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 2]: /images/20211220/28c342971ea24e3eb59906af1d19a285.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 3]: /images/20211220/c5cedd892a19464baf6a34b40c54659d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 4]: /images/20211220/71fecafe317c4015a7fa0cb101a03250.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 5]: /images/20211220/0d576528fa1747d9b3eecb5544ef241b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20190629132444345.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20190629132502892.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20190629132517118.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 9]: /images/20211220/e43c01195d7e475bb6e134afeae3cc09.png