[数据结构与算法]图 (chart）

说实话图数据结构的实现在看源码的时候还花费了我不少时间，花了不少精力才一步步将图拿下，回想看源码的过程无比痛苦，但是想想又感觉还是挺值得的毕竟学会了一种数据结构，图这种数据结构比起以往学的数据结构要复杂得多，但是如果你学会了其实也就那样。现在就给大家分享我对图的理解，如果有什么错误请大家指正，现在就从以下三个方面给大家讲解图。

1：什么是图？2：图是怎样创建的？3：图的广度遍历和图的深度遍历？

图的图像效果：

?

上面就是一张简单的图 很显然根据图像我们可以看出图由顶点和顶点上的数据以及由连接两个顶点之间的边和边上的数据组成，边上的数据我们称之为权重。?

?

因为图由边和顶点组成所以我们就定义两个结构体用来表示顶点和边，再定义一个结构体用来保存图中顶点的个数和边的条数。

//表示图的边用来连接图的节点
typedef struct _Edge {
	int weight;//表示权重
	int adjNode;//连接下一个顶点
	struct _Edge* next;//连接下一条边节点
}Edge;

//表示图中的顶点
typedef struct _chartNode {
	char date;//保存节点中的数据
	Edge* first;//指向邻接的第一个顶点
}chartNode;

//表示图
typedef struct _Chart {
	int numberSides;//表示边树
	int numberNode;//表示图中的点数
	chartNode* adjNodes;
}Chart;

据体代码的含义已经在代码后面注释

结构体定义完要做的是初始化图

void initChart(Chart& chart) {
	chart.adjNodes = new chartNode[MAX_SIZE];//动态申请一块内存表示数组保存图中的顶点
	chart.numberNode = 0; //初始化图中节点为0
	chart.numberSides = 0; //初始化图中边为0
	for (int i = 0;i < chart.numberNode;i++) { //将全局数组中的值全部赋值为false
		visitNode[i] = false;
	}
}

图初始化完下一步就是建立一个图

void buildChart(Chart& chart) {
	int numberNode;//顶点数
	int numberSide;//边数
	cout << "请输入图中的顶点数:";
	cin >> numberNode;
	cout << "请输入图中的边数:";
	cin >> numberSide;
	if (numberNode <= 0 || numberSide <= 0) {
		cout << "输入的边数或顶点数不符合要求!";
		return;
	}
	chart.numberNode = numberNode;
	chart.numberSides = numberSide;
	char date;
	cout << "输入有哪些顶点:";
	for (int i = 0;i < chart.numberNode;i++) { //输入图中顶点保存的数据
		cin >> date;
		chart.adjNodes[i].date = date;//为图中每个顶点数据域赋值
		chart.adjNodes[i].first = NULL;//将每个顶点的指向设置为空
	}

	cout << "输入依次连接的两个节点以及边的权重:";
	char ch1, ch2;//记录输入顶点中的数据
	int c1, c2;//记录输入的顶点保存在数组中哪个位置
	int weight;//表示权重

	for (int i = 0;i < chart.numberSides;i++) {
		cin >> ch1 >> ch2 >> weight;//输入相连两个顶点和两个顶点之间的权重
		c1 = findNode(chart, ch1);//跟据输入的值找到图中顶点在数组中的位置并返回顶点位置
		c2 = findNode(chart, ch2);
		if (c1 >= 0 && c2 >= 0) {
			Edge* tmp = new Edge;//申请一块内存用来表示边
			tmp->adjNode = c2;
			tmp->weight = weight;
			tmp->next = chart.adjNodes[c1].first;//将边和顶点相连
			chart.adjNodes[c1].first = tmp;
		}
	}
}

重要的代码已经注释。

如果单看代码是很难懂的用图像看就可以简单一些，我们创建的表是用邻接表的形式当然创建表的形式还有邻接矩阵但是邻接矩阵一般用的不多（最主要的是本人没有研究过邻接矩阵如果有研究过的伙伴可以和我分享）

在创建表时我们将与 A 相连的B，C，D顶点连成一个链表同理与B，C，D，E?相连的顶点我们也将其连成一个链表，左右两个图对比看再结合代码的执行顺序就可以看懂创建表的过程，至于为什么要这样创建表我也不知但是看了表的两种遍历方式也就了然于心了。

表的深度遍历

void deepErgodicChart(Chart& chart, int now) {
	if (visitNode[now] == false) {//判断是否已访问
		cout << chart.adjNodes[now].date << " ";
		visitNode[now] = true;//设置为以访问
	}
	Edge* tmp = chart.adjNodes[now].first;//定义一个临时变量指向于顶点相连的下一个顶点
	while (tmp) {
		int index = tmp->adjNode;
		tmp = tmp->next;
		if (visitNode[index] == false) {
			deepErgodicChart(chart, index);//用递归访问下一个顶点
		}
	}
}

结合图像就可知什么叫深度遍历

思路：就是先遍历与A相连的第一个顶点D再遍历与D相连的顶点E一步一步深入遍历，最后遍历到E但是没有与E相连的顶点就一步一步返回，返回到D再判断有没有与D相连的另外顶点如果有再深入遍历否则继续返回到A（每遍历了一个顶点就会将该节点标记为已遍历以防再此遍历该节点）返回A后继续遍历C再深入遍历与C相连的节点E但是前面已经标记E已经遍历过所以就不再遍历E，继续重复以上操作就可以完成图的遍历。

图的广度遍历

void spanErgodicChart(Chart& chart, int now) {
	queue<int>q;
	q.push(now);//将数组的第一个元素入队
	cout << "图中的顶点有:";
	while (!q.empty()) {
		int index = q.front();
		if (visitNode[index] == false) {
			cout << chart.adjNodes[index].date << " ";
			visitNode[index] = true;
		}
		q.pop();//将元素出队
		Edge* tmp = chart.adjNodes[index].first;//定位到出队顶点的位置
		while (tmp) {//将与出队顶点相连顶点全部入队
			int tmp1 = tmp->adjNode;
			q.push(tmp1);
			tmp = tmp->next;
		}
	}
}

同样结合图像

思路：在这我们将另外一中数据结构队列加入用来保存顶点，我们先将A入队并打印里面的数据，后将其出队出队以后将与?A相连的B，C，D入队，根据队列的特性B是最先出队的因为B最先入队打印B的值以后再将B出队，B出队以后将与B相连的顶点再入队，依次将入队的顶点出队并将与出队顶点相连的顶点入队，（每遍历了一个顶点就将其设置为已遍历以防再次遍历）这样就可以做到全部顶点入队和出队并能打印所有的顶点。

具体代码

#pragma once
#include<iostream>
#include<queue>

using namespace std;

#define MAX_SIZE 28
bool visitNode[MAX_SIZE];

//表示图的边用来连接图的节点
typedef struct _Edge {
	int weight;//表示权重
	int adjNode;//连接下一个顶点
	struct _Edge* next;//连接下一条边节点
}Edge;

//表示图中的顶点
typedef struct _chartNode {
	char date;//保存节点中的数据
	Edge* first;//指向邻接的第一个顶点
}chartNode;

//表示图
typedef struct _Chart {
	int numberSides;//表示边树
	int numberNode;//表示图中的点数
	chartNode* adjNodes;
}Chart;

//初始化图
void initChart(Chart& chart);

//创建图
void buildChart(Chart& chart);

//深度遍历图
void deepErgodicChart(Chart& chart, int now);

//广度遍历图
void spanErgodicChart(Chart& chart, int now);

//依次遍历图中的节点
void spanNode(Chart& chart);

//找到图中的节点
int findNode(Chart& chart, char ch);

//广度遍历图
void deepNode(Chart& chart);

void initChart(Chart& chart) {
	chart.adjNodes = new chartNode[MAX_SIZE];
	chart.numberNode = 0; //初始化图中节点为0
	chart.numberSides = 0; //初始化图中边为0
	for (int i = 0;i < chart.numberNode;i++) { //将全局数组中的值全部赋值为false
		visitNode[i] = false;
	}
}

void buildChart(Chart& chart) {
	int numberNode;//顶点数
	int numberSide;//边数
	cout << "请输入图中的顶点数:";
	cin >> numberNode;
	cout << "请输入图中的边数:";
	cin >> numberSide;
	if (numberNode <= 0 || numberSide <= 0) {
		cout << "输入的边数或顶点数不符合要求!";
		return;
	}
	chart.numberNode = numberNode;
	chart.numberSides = numberSide;
	char date;
	cout << "输入有哪些顶点:";
	for (int i = 0;i < chart.numberNode;i++) { //输入图中顶点保存的数据
		cin >> date;
		chart.adjNodes[i].date = date;//为图中每个顶点数据域赋值
		chart.adjNodes[i].first = NULL;//将每个顶点的指向设置为空
	}

	cout << "输入依次连接的两个节点以及边的权重:";
	char ch1, ch2;//记录输入顶点中的数据
	int c1, c2;//记录输入的顶点保存在数组中哪个位置
	int weight;//表示权重

	for (int i = 0;i < chart.numberSides;i++) {
		cin >> ch1 >> ch2 >> weight;//输入相连两个顶点和两个顶点之间的权重
		c1 = findNode(chart, ch1);//跟据输入的值找到图中顶点在数组中的位置并返回顶点位置
		c2 = findNode(chart, ch2);
		if (c1 >= 0 && c2 >= 0) {
			Edge* tmp = new Edge;//申请一块内存用来表示边
			tmp->adjNode = c2;
			tmp->weight = weight;
			tmp->next = chart.adjNodes[c1].first;//将边和顶点相连
			chart.adjNodes[c1].first = tmp;
		}
	}
}

int findNode(Chart& chart, char ch) {
	for (int i = 0;i < chart.numberNode;i++) {
		if (chart.adjNodes[i].date == ch) {
			return i;
		}
	}
	return -1;
}

void deepErgodicChart(Chart& chart, int now) {
	if (visitNode[now] == false) {//判断是否已访问
		cout << chart.adjNodes[now].date << " ";
		visitNode[now] = true;//设置为以访问
	}
	Edge* tmp = chart.adjNodes[now].first;//定义一个临时变量指向于顶点相连的下一个顶点
	while (tmp) {
		int index = tmp->adjNode;
		tmp = tmp->next;
		if (visitNode[index] == false) {
			deepErgodicChart(chart, index);//用递归访问下一个顶点
		}
	}
}

void deepNode(Chart& chart) {
	for (int i = 0;i < chart.numberNode;i++) {
		if (visitNode[i] == false) {//如果数组中的类型为false则表明没有访问过
			deepErgodicChart(chart, i);
		}
	}
}

void spanNode(Chart& chart) {
	for (int i = 0;i < chart.numberNode;i++) {
		if (visitNode[i] == false) {//如果数组中的类型为false则表明没有访问过
			spanErgodicChart(chart, i);
		}
	}
}

void spanErgodicChart(Chart& chart, int now) {
	queue<int>q;
	q.push(now);//将数组的第一个元素入队
	cout << "图中的顶点有:";
	while (!q.empty()) {
		int index = q.front();
		if (visitNode[index] == false) {
			cout << chart.adjNodes[index].date << " ";
			visitNode[index] = true;
		}
		q.pop();//将元素出队
		Edge* tmp = chart.adjNodes[index].first;//定位到出队顶点的位置
		while (tmp) {//将与出队顶点相连顶点全部入队
			int tmp1 = tmp->adjNode;
			q.push(tmp1);
			tmp = tmp->next;
		}
	}
}

mian函数

#include<stdlib.h>
#include"chart.h"

int main(void) {
	Chart chart;

	//初始化图
	initChart(chart);

	//创建图
	buildChart(chart);

	//广度遍历图
	spanNode(chart);

	//深度遍历图
	deepNode(chart);

	system("pause");
	return 0;
}