[手撕数据结构] 图的存储结构及遍历方式

图是一种较线性表和树更加复杂的class="superseo">数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。
关于图的基本概念之类知识请参考这篇文章 （属实详细的雅痞）

原文链接：https://blog.csdn.net/Real_Fool_/article/details/114141377 

本篇我们重心是代码实现图的两种存储结构（邻接矩阵法与邻接表法）以及两种遍历 *** 作

（深度优先搜索 DFS 广度优先搜索 BFS）图使用无向图（如下所示）

#include
#include
using namespace std;
#define MVNum 100      //最大顶点数
typedef struct Mgraph
{
	char vexs[MVNum];                     //顶点表 存结点信息
	int arcs[MVNum][MVNum];               //邻接矩阵
	int vexnum;               //图的当前点数
	int arcnum;               //图的当前边数
}AMGraph;//Adjacency Matrix Graph

int LocateVex(AMGraph* G, char v)//找到结点V在图G中的位置 即下标
{
	for (int i = 0; i < G->vexnum; i++)
	{
		if (G->vexs[i] == v)
		{
			return i;
		}
	}
	cout << "没找到" << endl;
	return 0;
}
void CreatAMG(AMGraph* G)//邻接矩阵表示法创建无向图
{
	cout << "请输入图的总顶点数与总边数: " ;
	cin >> G->vexnum >> G->arcnum;//输入总顶点数 总边数
	cout << "输入点的信息: " ;
	for (int i = 0; i < G->vexnum; i++)
	{
		cin >> G->vexs[i];
	}
	for (int i = 0; i < G->vexnum; i++)//初始化
	{
		for (int j = 0; j < G->vexnum; j++)
		{
			G->arcs[i][j] = 0;
		}
	}
	char v1, v2;
	cout << "输入相连结点" << endl;
	for (int k = 0; k < G->arcnum; k++)//构造邻接矩阵
	{
		cin >> v1 >> v2;//表示v1和v2相连接
		int i = LocateVex(G, v1);
		int j = LocateVex(G, v2);
		G->arcs[i][j] = G->arcs[j][i] = 1;
	}
	cout << "邻接矩阵如下" << endl;
	for (int i = 0; i < G->vexnum; i++)
	{
		for (int j = 0; j < G->vexnum; j++)
		{
			cout << G->arcs[i][j] << " ";
		}
		cout << "\n";
	}
	return;
}
int visited[MVNum] = { 0 };
void DFS(AMGraph* G, int v)//从第v个顶点开始深搜
{
	cout << G->vexs[v] << "->";
	visited[v] = 1;
	for (int i = 0; i < G->vexnum; i++)
	{
		if (G->arcs[v][i] != 0 && visited[i] == 0)
		{
			DFS(G, i);
		}
	}
}
int visitd[MVNum];          
int Queue[MVNum];           //辅助队列
int head = 0;
int tail = 0;
void BFS(AMGraph* G, int v)
{
	cout << G->vexs[v] << "->";
	visitd[v] = 1;
	if (visitd[v] == 0)
		Queue[head++] = v;
	for (int i = 0; i < G->vexnum; i++)
	{
		if (visitd[i] == 0)
		{
			if (G->arcs[v][i] == 1)//未被访问且俩结点连接
			{
				Queue[head++] = i;
				visitd[i] = 1;
			}
		}
	}

	if (tail != head) //如果队列不空
		BFS(G, Queue[tail++]);
}

int main()
{
	AMGraph* G = (AMGraph*)malloc(sizeof(AMGraph));
	if (G == NULL)
	{
		cout << "空间不足 创建失败" << endl;
		return 0;
	}
	CreatAMG(G);
	cout << "深搜结果如下" << endl;
	DFS(G, 0);
	cout <<"NULL"<< endl;
	cout << "广搜结果如下" << endl;
	BFS(G, 0);
	cout << "NULL" << endl;
	system("pause");
	return 0;
}

效果如下

#include
#include
using namespace std;
#define MVNum 100      //最大顶点数

typedef struct ArcNode  //边结点
{
	int adjvex;//该边所指向的顶点的位置
	struct ArcNode* next;
}ArcNode;//边结点

typedef struct VNode //顶点
{
	char data;
	ArcNode* firstarc;//指向第一条依附该顶点的边
}VNode;//顶点 

typedef struct
{
	VNode vertices[MVNum];     //邻接表
	int vexnum;                //图的当前顶点数
	int arcnum;                //图的当前边数
}ALGraph;//Adjacency List Graph

int LocateVex(ALGraph* G, char v)//找到结点V在图G中的位置 即下标
{
	for (int i = 0; i < G->vexnum; i++)
	{
		if (G->vertices[i].data == v)
			return i;
	}
	cout << "没找到" << endl;
	return 0;
}

void CreatALG(ALGraph* G)//邻接表表示法创建无向图
{
	cout << "请输入图的总顶点数与总边数: ";
	cin >> G->vexnum >> G->arcnum;//输入总顶点数 总边数
	cout << "输入顶点信息: ";
	for (int i = 0; i < G->vexnum; i++)//初始化
	{
		cin >> G->vertices[i].data;
		G->vertices[i].firstarc = NULL;
	}
	cout << "输入相连的结点" << endl;
	char v1, v2;
	for (int k = 0; k < G->arcnum; k++)//构造邻接表
	{
		cin >> v1 >> v2;
		int i = LocateVex(G, v1);
		int j = LocateVex(G, v2);

		ArcNode* p1 = new ArcNode;
		p1->adjvex = j;                       //邻接点序号
		p1->next = G->vertices[i].firstarc;
		G->vertices[i].firstarc = p1;         //前插
		ArcNode* p2 = new ArcNode;
		p2->adjvex = i;
		p2->next = G->vertices[j].firstarc;
		G->vertices[j].firstarc = p2;
	}
	cout << "邻接表如下" << endl;
	for (int i = 0; i < G->vexnum; i++)
	{
		cout << G->vertices[i].data << "->";
		ArcNode* p = G->vertices[i].firstarc;
		while (p != NULL)
		{
			cout << G->vertices[p->adjvex].data << "->";
			p = p->next;
		}
		cout << "->NULL" << endl;
	}
}
int visited[MVNum] = { 0 };
void DFS(ALGraph* G, int v)//从第V个结点开始深搜
{
	cout << G->vertices[v].data << "->";
	visited[v] = 1;
	ArcNode* p = G->vertices[v].firstarc;
	while (p != NULL)
	{
		int w = p->adjvex;
		if (visited[w] == 0)
			DFS(G, w);
		p = p->next;
	}
}
int visitd[MVNum] = { 0 };
int Queue[MVNum] = { 0 };        //辅助队列
int head = 0;
int tail = 0;
void BFS(ALGraph* G, int v)//从第v个结点开始广搜
{
	cout << G->vertices[v].data << "->";
	visitd[v] = 1;
	if (visitd[v] == 0)
		Queue[head++] = v;    //入队

	ArcNode* p = G->vertices[v].firstarc;
	while (p != NULL)
	{
		if (visitd[p->adjvex] == 0)
		{
			Queue[head++] = p->adjvex;
			visitd[p->adjvex] = 1;
		}

		p = p->next;
	}
	if (head != tail)//队列不空
		BFS(G, Queue[tail++]);
}
int main()
{
	ALGraph* G = new ALGraph;
	CreatALG(G);
	cout << "深搜结果如下" << endl;
	DFS(G, 0);
	cout << "NULL"<