数据结构实践教程-图

博主：酱油瓶
发布时间：2021 年 11 月 15 日
3600 次浏览
暂无评论
2098字数
分类：学习软件工程

# 试验8.1 存储结构转换问题

## 1.问题描述

以图的邻接矩阵方式创建一有向图，然后根据此存储，求图的邻接表的存储方式，并输出邻接表。

## 2.数据结构设计

分为图的邻接矩阵存储和图的邻接表存储

### 2.1 存储设计

* 图的邻接矩阵`AdjMatrix.h`
  ```c++
  #define MAX_VERTEX_NUM 20
  const int infinity = INT_MAX;

struct ArcCell {
  	int adj;//边权
  };

template<class T>
  struct _MGraph {
  	T vexs[MAX_VERTEX_NUM];//顶点表
  	ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
  	int vexnum;//顶点数
  	int arcnum;//边数
  };
  ```
* 图的邻接表`AdjList.h`
  ```c++
  #define MAX_VERTEX_NUM 20

struct ArcNode
  {
  	int adjvex;//该弧所指向的顶点的位置
  	struct ArcNode* nextarc;//指向下一条弧的指针
  	//int* info;//该弧相关信息的指针,有向图不使用
  };

template<class T>
  struct VNode {
  	T data;//顶点信息
  	ArcNode* firstarc;//指向第一条依附该顶点的指针
  };

template<class T>
  struct _ALGraph
  {
  	VNode<T>vertices[MAX_VERTEX_NUM];
  	int vexnum;//顶点数
  	int arcnum;//边数
  };
  ```

### 2.2 函数设计

* 图的邻接矩阵：构造有向图、定位顶点、输出邻接矩阵
  ```c++
  template<class T>
  class MGraph {
  public:
  	_MGraph<T>mgraph;
  	bool visited[MAX_VERTEX_NUM];
  	void CreateDG();//构造有向图
  	int LocateVex(T u);//图存在，途中存在顶点u，则返回该顶点在图中的位置
  	void DisPlay();//输出邻接矩阵
  };

```
* 图的邻接表：邻接矩转换、输出邻接表
  ```c++
  template<class T>
  class ALGraph 
  {
  	_ALGraph<T>algraph;
  	bool visited[MAX_VERTEX_NUM];
  public:
  	void Display();//输出邻接表
  	void AdjMatrixToAdjList(MGraph<T> mg);//邻接矩阵转换为邻接表
  };

```

## 3.算法设计

### 3.1 邻接矩阵

##### 3.1.1 创建邻接矩阵

```c++
template<class T>
void MGraph<T>::CreateDG()
{
	int i, j;
	T v1, v2;
	cout << "请输入有项图的顶点个数，弧的个数：";
	cin >> mgraph.vexnum >> mgraph.arcnum;
	cout << "请输入各个顶点：";
	for (i = 0; i < mgraph.vexnum; i++)//构造顶点向量
		cin >> mgraph.vexs[i];
	for (i = 0; i < mgraph.vexnum; i++)//初始化邻接矩阵
	{
		for (j = 0; j < mgraph.vexnum; j++) 
		{
			mgraph.arcs[i][j].adj = 0;
		}
	}
	for (i = 0; i < mgraph.arcnum; i++)//构造邻接矩阵
	{
		cout << "请输入一条弧的起点,终点:";
		cin >> v1 >> v2;
		int m = LocateVex(v1);
		int n = LocateVex(v2);
		mgraph.arcs[m][n].adj = 1;
	}
}

template<class T>
int MGraph<T>::LocateVex(T u)
{
	for (int i = 0; i < MAX_VERTEX_NUM; i++)
	{
		if (u == mgraph.vexs[i])
		{
			return i;
		}
	}
	return -1;
}
```

#### 3.1.2 输出邻接矩阵

```c++
template<class T>
void MGraph<T>::DisPlay()
{
	int i, j;
	cout << mgraph.vexnum << "个顶点" << mgraph.arcnum << "条边";
	cout << "顶点为:";
	for (i = 0; i < mgraph.vexnum; i++)
		cout << mgraph.vexs[i] << " ";
	cout << endl;
	for (i = 0; i < mgraph.vexnum; i++)
	{
		for (j = 0; j < mgraph.vexnum; j++)
		{
			cout << setw(5) << mgraph.arcs[i][j].adj << "\t";
		}
		cout << endl;
	}
}
```

### 3.2 图的邻接表

#### 3.2.1 邻接矩阵转换

```c++
template<class T>
void ALGraph<T>::AdjMatrixToAdjList(MGraph<T> mg)
{
	int i,j;
	ArcNode* p;
	for (i = 0; i < mg.mgraph.vexnum; i++)//邻接表表头向量初始化
	{
		algraph.vertices[i].firstarc = NULL;
	}
	for (i = 0; i < mg.mgraph.vexnum; i++)//顶点赋值
	{
		if (mg.mgraph.vexs[i]!="")
		{
			T t = mg.mgraph.vexs[i];
			algraph.vertices[i].data = t;
		}
	}
	for (i = 0; i <mg.mgraph.vexnum; i++)//遍历邻接矩阵
	{
		for (j = 0; j < mg.mgraph.vexnum; j++)
		{
			if (mg.mgraph.arcs[i][j].adj == 1)
			{
				p = new ArcNode;//实例化
				p->adjvex = j;//p指向的顶点
				p->nextarc = algraph.vertices[i].firstarc;//p的下一条弧
				algraph.vertices[i].firstarc = p;//链入链表
			}
		}
	}
	algraph.vexnum = mg.mgraph.vexnum;//顶点数
	algraph.arcnum = mg.mgraph.arcnum;//边数
}
```

#### 3.2.2 邻接表转换

```c++
template<class T>
void ALGraph<T>::Display()
{
	int i;
	ArcNode* p;
	cout << algraph.vexnum << "个顶点：" << endl;
	for (i = 0; i < algraph.vexnum; i++)
		cout << algraph.vertices[i].data << " ";
	cout << endl;
	for (i = 0; i < algraph.vexnum; i++)
	{
		p = algraph.vertices[i].firstarc;
		while (p) 
		{
			cout << algraph.vertices[i].data << "->" << algraph.vertices[p->adjvex].data << "\t";
			cout << endl;
			p = p->nextarc;
		}
	}
}
```

## 4.运行测试

### 试验一

测试用例：

![](https://snz04pap001files.storage.live.com/y4mGmY6vaD1MiAYMtul1SgeLaXcYoYWslJAQHrUIURQolwJ0GDrLXoexCCgh4hPFaANzT9hd7SfXrGegP_8nO7wGuzJPY7AeRD62iKipE8RZXsUbkd1hQH4dqOL-qXBn2mkyCElhP2AonqCOjG90pWBbAnc8jzoTRYzcRCZxNlnGx7TWqf1KTwhKjXJdRxSJRXI?width=1378&height=976&cropmode=none "测试1")

1. 输入顶点数和边数
   ![](https://snz04pap001files.storage.live.com/y4mztJTfI64aGoIy0AB2IvOQZ0NilNkWAfDChqqyEqXmYpIXJITB1jfSvIpRMIU0Chrn9m28mFG_Hd42_r4lbQ8-asQ59bGiACJqNvFfFY0wq3Mo__3nbipzmNvpycN8dsAOCnqjvGh6GKqsrTvO4P4Ls0DafDXR3Ob5Lm20R3yKRSz1_yi-M2za30wSwz0rmiV?width=1470&height=768&cropmode=none "Step1")
2. 输入顶点
   ![](https://snz04pap001files.storage.live.com/y4mEe5-_uhp4DJKz3Ei0X-XeowwLwQakFanmE4CdXzlrnT_9ROkVwxY1OBQCfdGFca4IIq-TV_TIICsC13WMfkmTtRPv09_OBUQcbDZc9VInGj_zlS0mKNgz-eSHy9tbP6iAwj6_JqshJLYhRcCLuXDm7EvpKwjMB5o4lvzI6XVOK-slNgFqf_UmHlmvxCQgDsr?width=1470&height=768&cropmode=none "Step2")
3. 输入起点、终点
   ![](https://snz04pap001files.storage.live.com/y4mrvB-e2RhqG9hW0YvqdXPKPxuCp0HSPoNUzoVEj0n-IUVhvw8m7GiSG90SW5BzVzKr-ECliOhgEbfY9MOKsdlRFhUPD1LZhyApgJd8b-F_f4KbPOLLKsB4pgB-67RHPObgJivZD8HQ9-y4Tyxkn-MSn1ugswtTwBjMm2Wp1RkB-4pJR5BluuLto2Qf2YecfVT?width=1470&height=768&cropmode=none "Step3")
4. 得到邻接矩阵，并转换为邻接表输出
   ![](https://snz04pap001files.storage.live.com/y4muL9C9OUUh5eDU7npSZZD2A1YBsHssOM7vatMy89hHAf8n_tRYDkNpFjjZaczO6wHvS5dkoDE2hpR9xK0Th1hZjxYw5cultuS0A-vSAOtkOuB50Iye9fNy4P8r22KTA1x6LY_MVFB7vYTO9pSSjtixJ98gWOYgZyShKZ0kL-DmDhHTWbauACPHIzByKIHDoZZ?width=1470&height=768&cropmode=none "Step4")

### 试验二

测试用例：

![](https://snz04pap001files.storage.live.com/y4mNPpap13rkccCaVS55Owv9JYo6gh3dDDYYfg9Yah_imJw607vNZqY_fBLpC-mD-leeS0gvTdza7EyWzaQ2N0-vzYbki-cH6PHRx6RTwkEIfbYpyTG6SDQIAJUlZEGFpS93_QkvDgb9SH7QK7bBV7rvGlQ4nFAGNx6gJ2bl5cBTlp5a0SLvkU0bATHVM8-umKJ?width=1257&height=1012&cropmode=none "测试二")

输出：

![](https://snz04pap001files.storage.live.com/y4m9U-Nl9mslL_5s8ne9ZwF_9HBX9WK52Z4Fka_MZYVmHEJIreYRXLALXQOIObF_MwGU9oGza5eofZ9tmJsgONHblt-Vc6HoOBqVpss0e1hv51AVY0QM5jN4Wdo44gk4mxXqEQk-80jmH3U1XACY4kwjuimRzh6UgV1XQuyip3OWj2S-eUJ6sPY2jzcVDBYkaub?width=1470&height=768&cropmode=none "输出")

## 5.调试记录与收获

1. 源程序清单
   * `AdjList.h`邻接表

```c++
     #pragma once
     #include"AdjMatrix.h"
     #include<iostream>

using namespace std;

#define MAX_VERTEX_NUM 20

struct ArcNode
     {
     	int adjvex;//该弧所指向的顶点的位置
     	struct ArcNode* nextarc;//指向下一条弧的指针
     	//int* info;//该弧相关信息的指针
     };

template<class T>
     struct VNode {
     	T data;//顶点信息
     	ArcNode* firstarc;//指向第一条依附该顶点的指针
     };

template<class T>
     struct _ALGraph
     {
     	VNode<T>vertices[MAX_VERTEX_NUM];
     	int vexnum;//顶点数
     	int arcnum;//边数
     };

template<class T>
     class ALGraph 
     {
     	_ALGraph<T>algraph;
     	bool visited[MAX_VERTEX_NUM];
     public:
     	void Display();//输出邻接表
     	void AdjMatrixToAdjList(MGraph<T> mg);//邻接矩阵转换为邻接表
     };

template<class T>
     void ALGraph<T>::Display()
     {
     	int i;
     	ArcNode* p;
     	cout << algraph.vexnum << "个顶点：" << endl;
     	for (i = 0; i < algraph.vexnum; i++)
     		cout << algraph.vertices[i].data << " ";
     	cout << endl;
     	for (i = 0; i < algraph.vexnum; i++)
     	{
     		p = algraph.vertices[i].firstarc;
     		while (p) 
     		{
     			cout << algraph.vertices[i].data << "->" << algraph.vertices[p->adjvex].data << "\t";
     			cout << endl;
     			p = p->nextarc;
     		}
     	}
     }

template<class T>
     void ALGraph<T>::AdjMatrixToAdjList(MGraph<T> mg)
     {
     	int i,j;
     	ArcNode* p;
     	for (i = 0; i < mg.mgraph.vexnum; i++)//邻接表表头向量初始化
     	{
     		algraph.vertices[i].firstarc = NULL;
     	}
     	for (i = 0; i < mg.mgraph.vexnum; i++)//顶点赋值
     	{
     		if (mg.mgraph.vexs[i]!="")
     		{
     			T t = mg.mgraph.vexs[i];
     			algraph.vertices[i].data = t;
     		}
     	}
     	for (i = 0; i <mg.mgraph.vexnum; i++)//遍历邻接矩阵
     	{
     		for (j = 0; j < mg.mgraph.vexnum; j++)
     		{
     			if (mg.mgraph.arcs[i][j].adj == 1)
     			{
     				p = new ArcNode;//实例化
     				p->adjvex = j;//p指向的顶点
     				p->nextarc = algraph.vertices[i].firstarc;//p的下一条弧
     				algraph.vertices[i].firstarc = p;//链入链表
     			}
     		}
     	}
     	algraph.vexnum = mg.mgraph.vexnum;//顶点数
     	algraph.arcnum = mg.mgraph.arcnum;//边数
     }

```
   * `AdjMatrix.h`邻接矩阵

```c++
     #pragma once
     #include<iostream>
     #include<iomanip>
     using namespace std;

#define MAX_VERTEX_NUM 20
     const int infinity = INT_MAX;

struct ArcCell {
     	int adj;//边权
     	//char* info;//该弧的相关信息
     };

template<class T>
     struct _MGraph {
     	T vexs[MAX_VERTEX_NUM];//顶点表
     	ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
     	int vexnum;//顶点数
     	int arcnum;//边数
     };

template<class T>
     class MGraph {
     public:
     	_MGraph<T>mgraph;
     	bool visited[MAX_VERTEX_NUM];
     	void CreateDG();//构造有向图
     	int LocateVex(T u);//图存在，途中存在顶点u，则返回该顶点在图中的位置
     	void DisPlay();//输出邻接矩阵
     };

template<class T>
     void MGraph<T>::CreateDG()
     {
     	int i, j;
     	T v1, v2;
     	cout << "请输入有项图的顶点个数，弧的个数：";
     	cin >> mgraph.vexnum >> mgraph.arcnum;
     	cout << "请输入各个顶点：";
     	for (i = 0; i < mgraph.vexnum; i++)//构造顶点向量
     		cin >> mgraph.vexs[i];
     	for (i = 0; i < mgraph.vexnum; i++)//初始化邻接矩阵
     	{
     		for (j = 0; j < mgraph.vexnum; j++) 
     		{
     			mgraph.arcs[i][j].adj = 0;
     		}
     	}
     	for (i = 0; i < mgraph.arcnum; i++)//构造邻接矩阵
     	{
     		cout << "请输入一条弧的起点,终点:";
     		cin >> v1 >> v2;
     		int m = LocateVex(v1);
     		int n = LocateVex(v2);
     		mgraph.arcs[m][n].adj = 1;
     	}
     }

template<class T>
     int MGraph<T>::LocateVex(T u)
     {
     	for (int i = 0; i < MAX_VERTEX_NUM; i++)
     	{
     		if (u == mgraph.vexs[i])
     		{
     			return i;
     		}
     	}
     	return -1;
     }

template<class T>
     void MGraph<T>::DisPlay()
     {
     	int i, j;
     	cout << mgraph.vexnum << "个顶点" << mgraph.arcnum << "条边";
     	cout << "顶点为:";
     	for (i = 0; i < mgraph.vexnum; i++)
     		cout << mgraph.vexs[i] << " ";
     	cout << endl;
     	for (i = 0; i < mgraph.vexnum; i++)
     	{
     		for (j = 0; j < mgraph.vexnum; j++)
     		{
     			cout << setw(5) << mgraph.arcs[i][j].adj << "\t";
     		}
     		cout << endl;
     	}
     }

```
   * `main.cpp`主函数

```c++
     #include<iostream>
     #include"AdjList.h"
     #include"AdjMatrix.h"
     using namespace std;

int main()
     {
     	MGraph<string> g1;
     	g1.CreateDG();
     	g1.DisPlay();
     	ALGraph<string> g2;
     	g2.AdjMatrixToAdjList(g1);
     	g2.Display();
     }
     ```
     # 实验8.2 有向图的路径问题

## 1.问题描述

对于有向图$G=(V,E)$,任意$v_i,v_j\in(v_i\neq{v_j})$,判断从顶点$v_i$到顶点$v_j$是否存在路径

## 2.数据结构设计

### 2.1 结构设计

使用有向图的邻接表表示构造有向图，使用栈存储

#### 2.1.1 有向图

```c++
     struct ArcNode
     {
     	int adjvex;//该弧所指向的顶点的位置
     	struct ArcNode* nextarc;//指向下一条弧的指针
     	//int* info;//该弧相关信息的指针
     };

template<class T>
     struct VNode {
     	T data;//顶点信息
     	ArcNode* firstarc;//指向第一条依附该顶点的指针
     };

template<class T>
     struct _ALGraph
     {
     	VNode<T>vertices[MAX_VERTEX_NUM];
     	int vexnum;//顶点数
     	int arcnum;//边数
     };
     ```
     #### 2.1.2 栈

```C++
     template<class T>
     class SqStack
     {
     private:
     	T* base;			//栈底指针
     	int top;			//栈顶
     	int stacksize;		//栈容量
     };
     ```
     ### 2.2 函数设计

#### 2.2.1 有向图

通过键盘输入创建有向图，输出邻接表，获取路径

```c++
     template<class T>
     class ALGraph
     {
     	_ALGraph<T>algraph;
     	bool visited[MAX_VERTEX_NUM];
     public:
     	int LocateVex(T u);//返回顶点u在图中的位置
     	void Display();//输出邻接表
     	void CreateGraph();//创建图
     	T GetVex(int index);//index是图中某个顶点的序号，返回v的值
     	int FirstAdjVex(T v);//返回v的第一个邻接点的序号，若无邻接点，则返回空
     	int NextAdjVex(T v, T w);//返回v相对于w的下一个邻接点的序号，若w是v的最后一个邻接点，则返回空
     	void Pathitoj(T vi, T vj, SqStack<T> stack,int *isfind);//寻找vi,vj之间的路径
     ```
     #### 2.2.1 栈

需要使用栈来保存深度遍历的顶点，所以需要使用：创建栈，入栈，出栈，输出栈

```c++
     template<class T>
     class SqStack
     {
     private:
     	T* base;			//栈底指针
     	int top;			//栈顶
     	int stacksize;		//栈容量
     public:
     	SqStack(int m);		//构造函数
     	void Push(T x);		//入栈
     	T Pop();			//出栈
     	T GetTop();			//获取栈顶元素
     	int StackEmpty();	//测栈空
     	void Display();		//显示栈中元素
     };
     ```
     ## 3.算法设计

### 3.1 有向图

#### 3.1.1 创建有向图

```c++
     template<class T>
     void ALGraph<T>::CreateGraph()
     {
     	int i, j, k;
     	T v1, v2;
     	cout << "请输入图的顶点数，边数：";
     	cin >> algraph.vexnum >> algraph.arcnum;
     	cout << "请输入" << algraph.vexnum << "个顶点的值：";
     	for (i = 0; i < algraph.vexnum; i++)
     	{
     		cin >> algraph.vertices[i].data;
     		algraph.vertices[i].firstarc = NULL;
     	}
     	cout << "请输入每条弧的弧尾、弧头！" << endl;
     	for (k = 0; k < algraph.arcnum; k++)
     	{
     		cout << "请输入一条弧的弧尾、弧头：";
     		cin >> v1 >> v2;
     		i = LocateVex(v1);
     		j = LocateVex(v2);
     		ArcNode* p1 = new ArcNode;
     		p1->adjvex = i;
     		p1->nextarc = algraph.vertices[j].firstarc;
     		algraph.vertices[j].firstarc = p1;
     	}
     	for (int i = 0; i < MAX_VERTEX_NUM; i++) {
     		visited[i] = false;
     	}
     }
     ```
     #### 3.1.2 输出邻接表

```c++
     template<class T>
     void ALGraph<T>::Display()
     {
     	int i;
     	ArcNode* p;
     	cout << algraph.vexnum << "个顶点：" << endl;
     	for (i = 0; i < algraph.vexnum; i++)
     		cout << algraph.vertices[i].data << " ";
     	cout << endl;
     	for (i = 0; i < algraph.vexnum; i++)
     	{
     		p = algraph.vertices[i].firstarc;
     		while (p)
     		{
     			cout << algraph.vertices[i].data << "->" << algraph.vertices[p->adjvex].data << "\t";
     			cout << endl;
     			p = p->nextarc;
     		}
     	}
     }
     ```
     #### 3.1.3 判断路径

```c++
     template<class T>
     void ALGraph<T>::Pathitoj(T vi, T vj, SqStack<T> stack,int *isfind)
     {//传入判断标记isfind
     	int i;
     	int j = LocateVex(vi);
     	stack.Push(vi);
     	visited[j] = true;//设置已访问点
     	vi = GetVex(j);
     	for (i = FirstAdjVex(vi); i >= 0; i = NextAdjVex(vi, GetVex(i)))
     	{
     		if (!visited[i] && GetVex(i) != vj)
     		{
     			Pathitoj(GetVex(i), vj, stack,isfind);//继续深度搜索
     		}
     		else if (GetVex(i) == vj)
     		{
     			cout << vj;
     			stack.Display();//输出路径
     			*isfind = 1;
     		}
     		else if (visited[i])
     		{
     			stack.Pop();
     		}
     	}
     }

```
     ### 3.2 栈

#### 3.2.1 构造

```c++
     template<class T>
     SqStack<T>::SqStack(int m)
     {
     	base = new T[m];
     	if (base == NULL)
     	{
     		cout << "栈创建失败，退出!" << endl;
     		exit(1);
     	}
     	stacksize = m;
     	top = -1;
     }
     ```
     #### 3.2.2 入栈

```c++
     template<class T>
     void SqStack<T>::Push(T x)
     {
     	if (top == stacksize - 1)
     		throw "栈满，无法入栈";
     	top++;
     	base[top] = x;
     }

```
     #### 3.2.3 出栈

```c++
     template<class T>
     T SqStack<T>::Pop()
     {
     	T x;
     	if (top == -1)throw"栈空，不能出栈";
     	x = base[top--];
     	return x;
     }
     ```
     #### 3.2.4 遍历栈

```c++
     template<class T>
     void SqStack<T>::Display()
     {
     	int i = top;
     	while (i >= 0)
     		cout << "<-" <<base[i--];
     	cout << endl;
     }
     ```
     ### 3.3 主函数

输入需要判断的顶点，并输出信息

```c++
     ALGraph<string> a1;
     	a1.CreateGraph(); //创建有向图
     	a1.Display();//输出有向图
     	cout << "依次输入两个顶点";
     	string vi, vj;
     	cin >> vi >> vj;//输入需要判断的顶点
     	SqStack<string>stack(20);
     	int isfind=0;
     	a1.Pathitoj(vi, vj, stack, &isfind);//判断路径
     	if (isfind)
     	{
     		cout << "存在路径！";
     	}
     	else
     	{
     		cout << "不存在路径！";
     	}
     ```
     ## 4.运行和测试

- 测试一

使用如下弱连通图测试

![测试1](https://snz04pap001files.storage.live.com/y4mGmY6vaD1MiAYMtul1SgeLaXcYoYWslJAQHrUIURQolwJ0GDrLXoexCCgh4hPFaANzT9hd7SfXrGegP_8nO7wGuzJPY7AeRD62iKipE8RZXsUbkd1hQH4dqOL-qXBn2mkyCElhP2AonqCOjG90pWBbAnc8jzoTRYzcRCZxNlnGx7TWqf1KTwhKjXJdRxSJRXI?width=1378&height=976&cropmode=none)

1. 输入![](https://snz04pap001files.storage.live.com/y4mp-nNHtca1JZYZSaZzaFgZTFdkXpDPi48vufTf0eWGHlRmG6cPete5w1KBWLWNboqBYuhfRztus70JhvPTAY1FMjGothHuFZX-pAG50s78acZ5d_vh-vXUYJ6Crmh4epKqiwmER3LOKak3wscmo9jpEUX_Mvzpvpe1g_JJPvgl6gaL6EEz20rzbor9vVgqgsB?width=1470&height=766&cropmode=none)

![](https://snz04pap001files.storage.live.com/y4m24RPm7fLjFB8Fy0Kj_WIpbLRSy0zw5D3uInZTH5G-ecVdPyLSuv4CvWOdksFW9jdzrhRrO6xBFDwktWW1_rD1QV9j_YBnXKqmtlbEvS4UxKEKKis2e4PHEGd6iugm04HKzUKlMZ90VpImyw0uGFwD66kyH--h1MmmbMA2kgPHJ6-hqocS3awYuxGR7mnTAgS?width=1470&height=766&cropmode=none)

![](https://snz04pap001files.storage.live.com/y4mm8hsAuPoYP2BydyhhvcVezIiBe8pOVhR66Y4vd_-fzPdFkla2PiAke4Z3_H0gQHdI3zH0unYkOvMacfqen5DnwsETO0FBA0-HXINAPrLfZOilAiJulaT6acjF1fOadA3XLRVbDs9Y3PgQrElku9_b3xchz1M09pv4xkXsXVkjieLE0TWflXlvp4JoS1T-F5g?width=1470&height=766&cropmode=none)
       2. 输入需要测试的路径B->C

![](https://snz04pap001files.storage.live.com/y4mXIBwwfQHqhKx5ACK7DFAUPKOdm9lRY-F070BDvJ5YrkyTq2Hw7F41_fZ8aMKSaXvBmhZFt4xx3JWDG9jw6snxScOw-E5Xm0YxNQlPpAySXZg8oSGh9WTgOJTj7SMusabUO0E4I3QkE4TDM9iZwsvJyrYEri0c6JxskNocUxYG7Ej7jCFjnzkYSl6uENK-k2P?width=1470&height=766&cropmode=none)
       3. 获得输出

![](https://snz04pap001files.storage.live.com/y4m7shg2xq_gK84f25EzdC7FgBYoZioavL_4JjguFgNy2oVX2JzbalmpyAHC8Wjmeh3me9NzeZzpELs3uV2t5jAiMNBBE_Iwc45T0Id3dMaAVLKM1BGkgrO2cDkIqtJ4NbkArH8ymHU_k1krdm-Rdw_nIRr0r85QkHrBK5egKPSusU5Lz7OCpbK0yiYg_SjaAwO?width=1470&height=766&cropmode=none)

测试B->A

![](https://snz04pap001files.storage.live.com/y4mIv2G7UrCLifPpJeC0qhY-nVVJBuO-187g0Kn5J42D7F_1YxDf9dTK7NqAtsXnSVeywMKJsp5wvLMUhePjdh37R-bhv9iS6QxO_RaXCNcbMK5IJaRJhYyker7Z2yLYqy6W9ZR5Gbf3Tjbho8QkDA5A321GIQLcFiQUEApgtcV4DmP3fOGHdgDsDPkGED-GT3f?width=1470&height=766&cropmode=none)
     - 测试二：强连通图

![测试2](https://snz04pap001files.storage.live.com/y4mqwIjLXea_JKaoWv8IGAZgKg7YjcmlZO4yu2cXnTuoV21jUgv4DX1uqr3GKwuzko5ynn0N-0WyotyiPWO65e-r2DFA_SgJtQKYOfvc_Nt5RkILrLszQItEqIaImLSlDnuFgQEPexn61QaKY42lOH0Dcp-y-oCAEfTZ2eh5Y5Lf6sBKOdz-nvkPV6h0NQ47ISZ?width=655&height=340&cropmode=none)

1. 测试A->C

![](https://snz04pap001files.storage.live.com/y4mC_e72JzK-4zlBYQ3HqzFdMgeeDrv7mX8-jPHmKS8kzBKlWAx7o9KDNjy4ofg4BxnrXvGAtRXAJ5idkcTCbgN0aJQGBvgiya3pzT9OYXIT4AmtHl3AubecymwXgKVPDXC2o1ozJIGLaDEW1MS24Nt_WvI9V47M5r2ViGsObAnzQ4Go27hnhk37ILRu8Am-ke-?width=1470&height=766&cropmode=none)
       2. 测试B->C

![](https://snz04pap001files.storage.live.com/y4m-hVqOdcaqMaB7RlZ4hGVcFm5hybsqbncAJrXSqawai-2yN6rzskIuuz30dM8_caaLdBYqkC4Ho23PLZ29_sSzXNtx18uduJCaWqPaxJApYbBP8GnwJTzgAGcoEODgRGzpKhGCyqHoqUnbbaalyt2Vo615qvT6rFnVoW5zrrF6VIcPghJ4qgEV2t4e3yGQXwW?width=1470&height=766&cropmode=none)

## 5.调试记录与收获

1. 源程序清单

- 邻接表`ADjList.h`

```c++
          #pragma once
          #include<iostream>
          #include"SqStack.h"

using namespace std;

#define MAX_VERTEX_NUM 20

struct ArcNode
          {
          	int adjvex;//该弧所指向的顶点的位置
          	struct ArcNode* nextarc;//指向下一条弧的指针
          	//int* info;//该弧相关信息的指针
          };

template<class T>
          struct VNode {
          	T data;//顶点信息
          	ArcNode* firstarc;//指向第一条依附该顶点的指针
          };

template<class T>
          struct _ALGraph
          {
          	VNode<T>vertices[MAX_VERTEX_NUM];
          	int vexnum;//顶点数
          	int arcnum;//边数
          };

template<class T>
          class ALGraph
          {
          	_ALGraph<T>algraph;
          	bool visited[MAX_VERTEX_NUM];
          public:
          	int LocateVex(T u);//返回顶点u在图中的位置
          	void Display();//输出邻接表
          	void CreateGraph();//创建图
          	T GetVex(int index);//index是图中某个顶点的序号，返回v的值
          	int FirstAdjVex(T v);//返回v的第一个邻接点的序号，若无邻接点，则返回空
          	int NextAdjVex(T v, T w);//返回v相对于w的下一个邻接点的序号，若w是v的最后一个邻接点，则返回空
          	void Pathitoj(T vi, T vj, SqStack<T> stack,int *isfind);//寻找vi,vj之间的路径
          };

template<class T>
          int ALGraph<T>::LocateVex(T u)
          {
          	for (int i = 0; i < algraph.vexnum; i++)
          	{
          		if (algraph.vertices[i].data == u)
          		{
          			return i;
          		}
          	}
          	return -1;
          }

template<class T>
          void ALGraph<T>::Display()
          {
          	int i;
          	ArcNode* p;
          	cout << algraph.vexnum << "个顶点：" << endl;
          	for (i = 0; i < algraph.vexnum; i++)
          		cout << algraph.vertices[i].data << " ";
          	cout << endl;
          	for (i = 0; i < algraph.vexnum; i++)
          	{
          		p = algraph.vertices[i].firstarc;
          		while (p)
          		{
          			cout << algraph.vertices[i].data << "->" << algraph.vertices[p->adjvex].data << "\t";
          			cout << endl;
          			p = p->nextarc;
          		}
          	}
          }

template<class T>
          void ALGraph<T>::CreateGraph()
          {
          	int i, j, k;
          	T v1, v2;
          	cout << "请输入图的顶点数，边数：";
          	cin >> algraph.vexnum >> algraph.arcnum;
          	cout << "请输入" << algraph.vexnum << "个顶点的值：";
          	for (i = 0; i < algraph.vexnum; i++)
          	{
          		cin >> algraph.vertices[i].data;
          		algraph.vertices[i].firstarc = NULL;
          	}
          	cout << "请输入每条弧的弧尾、弧头！" << endl;
          	for (k = 0; k < algraph.arcnum; k++)
          	{
          		cout << "请输入一条弧的弧尾、弧头：";
          		cin >> v1 >> v2;
          		i = LocateVex(v1);
          		j = LocateVex(v2);
          		ArcNode* p1 = new ArcNode;
          		p1->adjvex = i;
          		p1->nextarc = algraph.vertices[j].firstarc;
          		algraph.vertices[j].firstarc = p1;
          	}
          	for (int i = 0; i < MAX_VERTEX_NUM; i++) {
          		visited[i] = false;
          	}
          	//stack = new SqStack<T>(MAX_VERTEX_NUM);
          }

template<class T>
          T ALGraph<T>::GetVex(int index)
          {
          	if (index < 0 || index >= algraph.vexnum)
          		return NULL;
          	return algraph.vertices[index].data;
          }

template<class T>
          int ALGraph<T>::FirstAdjVex(T v)
          {
          	int i = LocateVex(v);
          	ArcNode* p = algraph.vertices[i].firstarc;
          	if (p)
          		return p->adjvex;
          	else
          		return -1;
          }

template<class T>
          int ALGraph<T>::NextAdjVex(T v, T w)
          {
          	ArcNode* p;
          	int i = LocateVex(v);
          	int j = LocateVex(w);
          	p = algraph.vertices[i].firstarc;//让p指向顶点w
          	while (p && (p->adjvex != j))
          	{
          		p = p->nextarc;
          	}
          	if (!p || !p->nextarc)//没找到w或者w是最后一个顶点
          		return -1;
          	else//找到w且w不是最后一个顶点
          		return p->nextarc->adjvex;
          }

template<class T>
          void ALGraph<T>::Pathitoj(T vi, T vj, SqStack<T> stack,int *isfind)
          {
          	int i;
          	int j = LocateVex(vi);
          	stack.Push(vi);
          	//stack.Display();
          	visited[j] = true;
          	//cout << algraph.vertices[j].data;
          	vi = GetVex(j);
          	for (i = FirstAdjVex(vi); i >= 0; i = NextAdjVex(vi, GetVex(i)))
          	{
          		if (!visited[i] && GetVex(i) != vj)
          		{
          			Pathitoj(GetVex(i), vj, stack,isfind);
          		}
          		else if (GetVex(i) == vj)
          		{
          			cout << vj;
          			stack.Display();
          			*isfind = 1;
          		}
          		else if (visited[i])
          		{
          			stack.Pop();
          		}
          	}
          }

```
        - 栈`SqStack.h`

```c++
          #pragma once
          #include<iostream>
          using namespace std;
          template<class T>
          class SqStack
          {
          private:
          	T* base;			//栈底指针
          	int top;			//栈顶
          	int stacksize;		//栈容量
          public:
          	SqStack(int m);		//构造函数
          	void Push(T x);		//入栈
          	T Pop();			//出栈
          	T GetTop();			//获取栈顶元素
          	int StackEmpty();	//测栈空
          	void Display();		//显示栈中元素
          };

template<class T>
          SqStack<T>::SqStack(int m)
          {
          	base = new T[m];
          	if (base == NULL)
          	{
          		cout << "栈创建失败，退出!" << endl;
          		exit(1);
          	}
          	stacksize = m;
          	top = -1;
          }

template<class T>
          void SqStack<T>::Push(T x)
          {
          	if (top == stacksize - 1)
          		throw "栈满，无法入栈";
          	top++;
          	base[top] = x;
          }

template<class T>
          T SqStack<T>::Pop()
          {
          	T x;
          	if (top == -1)throw"栈空，不能出栈";
          	x = base[top--];
          	return x;
          }

template<class T>
          T SqStack<T>::GetTop()
          {
          	if (top == -1) throw "空栈，栈顶无元素";
          	return base[top];
          }

template<class T>
          int SqStack<T>::StackEmpty()
          {
          	if (top == -1)
          		return 0;
          	else
          		return 1;
          }

template<class T>
          void SqStack<T>::Display()
          {
          	int i = top;
          	while (i >= 0)
          		cout <<"<-" <<base[i--] ;
          	cout << endl;
          }

```
        - 主函数`main.cpp`

```c++
          #include<iostream>
          #include"AdjList.h"
          using namespace std;

int main()
          {
          	ALGraph<string> a1;
          	a1.CreateGraph();
          	a1.Display();
          	cout << "依次输入两个顶点";
          	string vi, vj;
          	cin >> vi >> vj;
          	SqStack<string>stack(20);
          	int isfind=0;
          	a1.Pathitoj(vi, vj, stack, &isfind);
          	if (isfind)
          	{
          		cout << "存在路径！";
          	}
          	else
          	{
          		cout << "不存在路径！";
          	}
          }
          ```

最后修改：2022 年 06 月 03 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

数据结构实践教程-图

酱油瓶 • 2021 年 11 月 15 日

# 试验8.1 存储结构转换问题

## 1.问题描述

以图的邻接矩阵方式创建一有向图，然后根据此存储，求图的邻接表的存储方式，并输出邻接表。

## 2.数据结构设计

分为图的邻接矩阵存储和图的邻接表存储

### 2.1 存储设计

* 图的邻接矩阵`AdjMatrix.h`
  ```c++
  #define MAX_VERTEX_NUM 20
  const int infinity = INT_MAX;

struct ArcCell {
  	int adj;//边权
  };

struct ArcNode
  {
  	int adjvex;//该弧所指向的顶点的位置
  	struct ArcNode* nextarc;//指向下一条弧的指针
  	//int* info;//该弧相关信息的指针,有向图不使用
  };

template<class T>
  struct VNode {
  	T data;//顶点信息
  	ArcNode* firstarc;//指向第一条依附该顶点的指针
  };

template<class T>
  struct _ALGraph
  {
  	VNode<T>vertices[MAX_VERTEX_NUM];
  	int vexnum;//顶点数
  	int arcnum;//边数
  };
  ```

### 2.2 函数设计

```

## 3.算法设计

### 3.1 邻接矩阵

##### 3.1.1 创建邻接矩阵

template<class T>
int MGraph<T>::LocateVex(T u)
{
	for (int i = 0; i < MAX_VERTEX_NUM; i++)
	{
		if (u == mgraph.vexs[i])
		{
			return i;
		}
	}
	return -1;
}
```

#### 3.1.2 输出邻接矩阵

### 3.2 图的邻接表

#### 3.2.1 邻接矩阵转换

#### 3.2.2 邻接表转换

## 4.运行测试

### 试验一

测试用例：

### 试验二

测试用例：

输出：

## 5.调试记录与收获

1. 源程序清单
   * `AdjList.h`邻接表

```c++
     #pragma once
     #include"AdjMatrix.h"
     #include<iostream>

using namespace std;

#define MAX_VERTEX_NUM 20

struct ArcNode
     {
     	int adjvex;//该弧所指向的顶点的位置
     	struct ArcNode* nextarc;//指向下一条弧的指针
     	//int* info;//该弧相关信息的指针
     };

template<class T>
     struct VNode {
     	T data;//顶点信息
     	ArcNode* firstarc;//指向第一条依附该顶点的指针
     };

template<class T>
     struct _ALGraph
     {
     	VNode<T>vertices[MAX_VERTEX_NUM];
     	int vexnum;//顶点数
     	int arcnum;//边数
     };

```
   * `AdjMatrix.h`邻接矩阵

```c++
     #pragma once
     #include<iostream>
     #include<iomanip>
     using namespace std;

#define MAX_VERTEX_NUM 20
     const int infinity = INT_MAX;

struct ArcCell {
     	int adj;//边权
     	//char* info;//该弧的相关信息
     };

```
   * `main.cpp`主函数

```c++
     #include<iostream>
     #include"AdjList.h"
     #include"AdjMatrix.h"
     using namespace std;

## 1.问题描述

对于有向图$G=(V,E)$,任意$v_i,v_j\in(v_i\neq{v_j})$,判断从顶点$v_i$到顶点$v_j$是否存在路径

## 2.数据结构设计

### 2.1 结构设计

使用有向图的邻接表表示构造有向图，使用栈存储

#### 2.1.1 有向图

template<class T>
     struct VNode {
     	T data;//顶点信息
     	ArcNode* firstarc;//指向第一条依附该顶点的指针
     };

template<class T>
     struct _ALGraph
     {
     	VNode<T>vertices[MAX_VERTEX_NUM];
     	int vexnum;//顶点数
     	int arcnum;//边数
     };
     ```
     #### 2.1.2 栈

#### 2.2.1 有向图

通过键盘输入创建有向图，输出邻接表，获取路径

需要使用栈来保存深度遍历的顶点，所以需要使用：创建栈，入栈，出栈，输出栈

### 3.1 有向图

#### 3.1.1 创建有向图

```c++
     template<class T>
     void ALGraph<T>::Display()
     {
     	int i;
     	ArcNode* p;
     	cout << algraph.vexnum << "个顶点：" << endl;
     	for (i = 0; i < algraph.vexnum; i++)
     		cout << algraph.vertices[i].data << " ";
     	cout << endl;
     	for (i = 0; i < algraph.vexnum; i++)
     	{
     		p = algraph.vertices[i].firstarc;
     		while (p)
     		{
     			cout << algraph.vertices[i].data << "->" << algraph.vertices[p->adjvex].data << "\t";
     			cout << endl;
     			p = p->nextarc;
     		}
     	}
     }
     ```
     #### 3.1.3 判断路径

```
     ### 3.2 栈

#### 3.2.1 构造

```c++
     template<class T>
     void SqStack<T>::Push(T x)
     {
     	if (top == stacksize - 1)
     		throw "栈满，无法入栈";
     	top++;
     	base[top] = x;
     }

```
     #### 3.2.3 出栈

输入需要判断的顶点，并输出信息

- 测试一

使用如下弱连通图测试

测试B->A

1. 测试A->C

## 5.调试记录与收获

1. 源程序清单

- 邻接表`ADjList.h`

```c++
          #pragma once
          #include<iostream>
          #include"SqStack.h"

using namespace std;

#define MAX_VERTEX_NUM 20

template<class T>
          struct VNode {
          	T data;//顶点信息
          	ArcNode* firstarc;//指向第一条依附该顶点的指针
          };

template<class T>
          struct _ALGraph
          {
          	VNode<T>vertices[MAX_VERTEX_NUM];
          	int vexnum;//顶点数
          	int arcnum;//边数
          };

template<class T>
          void ALGraph<T>::Display()
          {
          	int i;
          	ArcNode* p;
          	cout << algraph.vexnum << "个顶点：" << endl;
          	for (i = 0; i < algraph.vexnum; i++)
          		cout << algraph.vertices[i].data << " ";
          	cout << endl;
          	for (i = 0; i < algraph.vexnum; i++)
          	{
          		p = algraph.vertices[i].firstarc;
          		while (p)
          		{
          			cout << algraph.vertices[i].data << "->" << algraph.vertices[p->adjvex].data << "\t";
          			cout << endl;
          			p = p->nextarc;
          		}
          	}
          }

```
        - 栈`SqStack.h`

template<class T>
          T SqStack<T>::Pop()
          {
          	T x;
          	if (top == -1)throw"栈空，不能出栈";
          	x = base[top--];
          	return x;
          }

template<class T>
          T SqStack<T>::GetTop()
          {
          	if (top == -1) throw "空栈，栈顶无元素";
          	return base[top];
          }

template<class T>
          int SqStack<T>::StackEmpty()
          {
          	if (top == -1)
          		return 0;
          	else
          		return 1;
          }

template<class T>
          void SqStack<T>::Display()
          {
          	int i = top;
          	while (i >= 0)
          		cout <<"<-" <<base[i--] ;
          	cout << endl;
          }

```
        - 主函数`main.cpp`

```c++
          #include<iostream>
          #include"AdjList.h"
          using namespace std;

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

数据结构实践教程-图

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款