数据结构----结构--非线性结构--图-CSDN博客

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

数据结构----结构–非线性结构–图

一.图Graph

1.图的结构

图是多对多的结构

2.图的基本概念

图的基本概念为G=(V,E)

V是顶点的集合

E是边的集合

G是图

一个图其实是顶点和边的二元组合

观察下图,思考V和E集合中的元素分别都是什么

在这里插入图片描述

V={V1,V2,V3,V4,V5}

E={(V1,V2),(V1,V3),(V1,V5),(V2,V3),(V2,V5),(V3,V4),(V3,V5),(V4,V5)}

G是V和E的二元组合

注意图中更重要的是边顶点与顶点之间的关系

3.图的一些相关概念

这里将无向图和有向图进行对比说明如果有相同的概念那么不会在有向图中重复书写

无向图

1.边的表示方法为V1V2

了解

依附V1到V2这条边就是依附于V1和V2这两个顶点的

2.完全图图中所有可能存在的边都存在

关于完全图的一个知识点

n个节点的无向完全图边有Cn2个n在C的右下角2在n的左上角

3.路径一个点到另外一个点所经过的边的总数

4.简单路径除起点和终点可能相同以外不允许顶点重复出现

5.连通一个点到另一个点可通

6.连通图图中任意两点均有路径可通

7.子图如果G1是G的子图那么V1∈VE1∈E

8.度图中的度指当前节点关联的边的长度

极大连通子图也叫连通分量对于一个连通图来讲它的极大连通子图就是1再看下面的一张图进行理解

在这里插入图片描述

此图中的极大连通子图为2

有向图

1.边的表示方法为 <V1V2>

2.完全图图中所有可能存在的边都存在

关于完全图的一个知识点

n个节点的无向完全图边有An2个n在C的右下角2在n的左上角

3.强连通一个点到另一个点双向可通

4.连通图图中任意两点均有路径双向可通

5.有向图的边也叫弧箭头的那一端叫弧首另一端叫弧尾

8.度有向图中指出去的边的总数叫入度指进来的边的总数叫入度出度入度之和就是度

3.图的存储方式

1.图的存储方式有两种一种是用邻接矩阵二维数组进行存储一种是用邻接链表进行存储

将下图分别用邻接矩阵和邻接链表进行存储

在这里插入图片描述

1.邻接矩阵二维数组

如下图

在这里插入图片描述

顶点之间没有边的正常应该是无穷这里用0来进行代替

行代表指向谁如第一行代表V1指向V2,V3,V5

列代表被谁指向如第一列代表V1被V2,V3,V5指向

注意如果一个图的邻接矩阵沿对角线对称且无特殊声明那这个图就是无向图

2.邻接链表

如下图

在这里插入图片描述

2.两种存储方式应用场合的不同

邻接矩阵适用于边多的图

邻接链表适用于边少的图

3.两种存储方式的区别

邻接矩阵是唯一的

邻接链表不唯一

4.用邻接矩阵二维数组实现图的存储代码实现

操作步骤

1.创建一个结构体此结构体中的属性有顶点的个数边的个数指向邻接矩阵的指针

1.得到顶点的个数边的个数

2.申请一个邻接矩阵动态申请空间记得要赋初值

3.添加边

代码如下

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Node {
	int nVertex;
	int nEdge;
	int* pMatrix;
}Graph;

Graph* CreateGraph() {
	//申请一个结构体类型的变量
	Graph * pGraph= (Graph*)malloc(sizeof(Graph));
	int nV;
	int nE;
	printf("请输入点数\n");
	scanf_s("%d", &nV);

	printf("请输入边数\n");
	scanf_s("%d", &nE);

	pGraph->nVertex = nV;
	pGraph->nEdge = nE;

	//申请矩阵
	pGraph->pMatrix= (int*)malloc(sizeof(int) * nV * nE);
	memset(pGraph->pMatrix, 0, sizeof(int) * nV * nE);

	//添加边
	int v1, v2;
	int i;
	for (int i = 0; i < nE; i++) {
		printf("输入两个顶点确定一条边\n");
		scanf_s("%d%d", &v1, &v2);
		if (v1 != v2 && v1 >= 1 && v1 <= nV && v2 >= 1 && v2 <= nV && pGraph->pMatrix[(v1 - 1) * nV + (v2 - 1)] == 0) {//如果符合创建边的条件那么创建这条边
			pGraph->pMatrix[(v1 - 1) * nV + (v2 - 1)] = 1;
			pGraph->pMatrix[(v2 - 1) * nV + (v1 - 1)] = 1;
		}
		else {//如果输入的两个顶点不符合这个图创建边的条件那么这里的i变量的值不会增大以此保证边的总数不变
			i--;
		}
	}

	

	return pGraph;
}
int main() {
	Graph* pGraph = CreateGraph();
	for (int i = 0; i < pGraph->nVertex * pGraph->nVertex; i++) {
		if (i % pGraph->nVertex == 0) printf("\n");
		printf("%d ", pGraph->pMatrix[i]);
	}
	return 0;
}

二.BFS和DFS

图的广度优先遍历就是BFS

图的深度优先遍历就是DFS

1.深度/深度优先的底层算法–回溯法BackTracking

1.回溯法解决的问题

1.求子集的问题

2.求排列的问题

3.求集合的问题

4.求棋盘的问题

2.回溯常见的写法

循环嵌套递归

3.用回溯法解决一道全排列的问题此题的网址为https://.cn/problems/permutations/

题目

给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

方法一标记法

方法二交换法

用方法一来解决此问题

代码如下

//下面代码不是明显的标记写法但是和标记的思路相同
class Solution {
public:
    void BT(vector<vector<int>>& result, vector<int> nums, vector<int> temp, int x) {
        //如果这个排列是全排列的一个答案这里是以是否达到答案排列的长度进行判断的 
        if (temp.size() == x) {
            result.push_back(temp);
            return;
        }
        //对可能的元素进行选择每次选择一个元素放到排列的当前位置上
        for (int i = 0; i < nums.size(); i++) {
            temp.push_back(nums[i]);
            vector<int>::iterator ite = nums.begin();
            ite += i;
            ite = nums.erase(ite);
            //继续看当前排列的下一个位置
            BT(result, nums, temp, x);
		   //为了当前排列当前位置下一个元素的正常判断进行还原
            ite = temp.end()-1;
            vector<int>::iterator ite2 = nums.begin();
            nums.insert(ite2, *ite);
            temp.pop_back();
            
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
         vector<vector<int>> result;
         vector<int> temp;
         BT(result,nums,temp,nums.size());
         return result;
    }
};

2.DFS深度优先遍历

操作步骤

1.申请一个标记数组赋初值

2.从给出的顶点开始遍历

1打印当前顶点

2对当前顶点进行标记就是给标记数组相应的位置进行值的修改

3找当前顶点邻接的且未标记的顶点进行处理重复2

代码如下

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Node {
	int nVertex;
	int nEdge;
	int* pMatrix;
}Graph;

Graph* CreateGraph() {
	//申请一个结构体类型的变量
	Graph* pGraph = (Graph*)malloc(sizeof(Graph));
	int nV;
	int nE;
	printf("请输入点数\n");
	scanf_s("%d", &nV);

	printf("请输入边数\n");
	scanf_s("%d", &nE);

	pGraph->nVertex = nV;
	pGraph->nEdge = nE;

	//申请矩阵
	pGraph->pMatrix = (int*)malloc(sizeof(int) * nV * nE);
	memset(pGraph->pMatrix, 0, sizeof(int) * nV * nE);

	//添加边
	int v1, v2;
	int i;
	for (int i = 0; i < nE; i++) {
		printf("输入两个顶点确定一条边\n");
		scanf_s("%d%d", &v1, &v2);
		if (v1 != v2 && v1 >= 1 && v1 <= nV && v2 >= 1 && v2 <= nV && pGraph->pMatrix[(v1 - 1) * nV + (v2 - 1)] == 0) {//如果符合创建边的条件那么创建这条边
			pGraph->pMatrix[(v1 - 1) * nV + (v2 - 1)] = 1;
			pGraph->pMatrix[(v2 - 1) * nV + (v1 - 1)] = 1;
		}
		else {//如果输入的两个顶点不符合这个图创建边的条件那么这里的i变量的值不会增大以此保证边的总数不变
			i--;
		}
	}



	return pGraph;
}

void MyDFS(Graph* pGraph, int begin, char* flagArr) {
	//打印
	printf("%d ", begin);
	//标记
	flagArr[begin - 1] = 1;
	//遍历当前顶点的邻接点
	for (int i = 0; i < pGraph->nVertex; i++) {
		if (pGraph->pMatrix[(begin - 1) * pGraph->nVertex + i] == 1 && flagArr[i] != 1) {//如果是邻接且未处理的顶点那么就遍历此顶点
			MyDFS(pGraph, i + 1, flagArr);
		}
	}
}

void DFS(Graph* pGraph,int begin) {
	//申请一个标记数组
	char* flagArr = (char*)malloc(sizeof(char) * pGraph->nVertex);
	memset(flagArr, 0, sizeof(char) * pGraph->nVertex);
	MyDFS(pGraph, begin, flagArr);
}



int main() {
	Graph* pGraph = CreateGraph();
	//进行DFS遍历
	DFS(pGraph, 2);
	return 0;
}

3.BFS广度优先遍历

操作步骤

1.申请一个标记数组和一个队列给标记数组赋初值

2.将遍历的第一个顶点放入到队列中并对此顶点进行标记就是给标记数组相应的位置进行值的修改

3.将队列中的首元素弹出输出将弹出顶点的邻接的且未标记的顶点入队并对此顶点进行标记然后重复3直到队列为空此操作结束

代码如下

void BFS(Graph* pGraph, int begin) {
	if (pGraph == NULL || begin<1 || begin > pGraph->nVertex)return;
	//申请一个标记数组
	char* flagArr = (char*)malloc(sizeof(char) * pGraph->nVertex);
	memset(flagArr, 0, sizeof(char) * pGraph->nVertex);

	//申请一个队列
	queue<int> qe;

	//起点入队
	qe.push(begin);
	flagArr[begin - 1] = 1;
	
	//对队列进行处理
	while (!qe.empty()) {
		//弹出 打印
		int x = qe.front();
		cout<<x;
		qe.pop();

		//邻接点
		for (int i = 0; i < pGraph->nVertex; i++) {
			if (pGraph->pMatrix[(x - 1) * pGraph->nVertex + i] == 1 && flagArr[i] != 1) {
				//入队 标记
				qe.push(i + 1);
				flagArr[i] = 1;
				
			}
		}
	}
	//释放空间
	free(flagArr);
	flagArr = NULL;
}

int main() {
	Graph* pGraph = CreateGraph();
	//进行BFS遍历
	BFS(pGraph, 1);
	return 0;
}