天天看点
返回

C++构造无向图，邻接矩阵，深度优先遍历，广度优先遍历

目录

定义无向图邻接矩阵

构造无向图

打印邻接矩阵

无向图邻接矩阵深度优先遍历（DFS）

无向图邻接矩阵广度优先遍历（BFS）

测试

 完整代码

定义无向图邻接矩阵 

#define MVNum 100 //最大顶点数

//定义无向图邻接矩阵
struct AMGraph
{
	string vexs[MVNum]; //顶点表
	int arcs[MVNum][MVNum]; //邻接矩阵
	int vexnum, arcnum; //图的当前定点数和边数
};

构造无向图

1、输入总顶点数和总边数

2、依次输入顶点信息存入顶点表

3、初始化邻接矩阵,使每个权值初始化为极大值

4、构造邻接矩阵

//声明
int LocateVex(AMGraph G, string u);

//创建无向图
bool CreateUDN(AMGraph& G)
{
	//1.输入顶点数和边数
	cout << "请输入顶点数：" << endl;
	cin >> G.vexnum;
	cout << "请输入边数：" << endl;
	cin >> G.arcnum;

	//2.依次输入顶点信息存入顶点表
	cout << "请输入顶点：" << endl;
	for (int i = 0; i < G.vexnum; i++)
	{
		cin >> G.vexs[i];
	}

	//3.初始化邻接矩阵,使每个权值初始化为极大值
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			G.arcs[i][j] = 0; //初始化邻接矩阵为0
		}
	}

	//4.构造邻接矩阵
	cout << "请输入一条边所依附的两个顶点及边的权值：" << endl;
	for (int k = 0; k < G.arcnum; k++)
	{
		string v1, v2;
		//int w;
		cin >> v1 >> v2; //输入一条边所依附的两个顶点及边的权值
		int i = LocateVex(G, v1); //确定v1,v2在G中的位置
		int j = LocateVex(G, v2);
		G.arcs[i][j] = 1; //边(v1,v2)的权值置为w
		G.arcs[j][i] = G.arcs[i][j]; //置边(v1,v2)的对称边(v2,v1)的权值为w
	}
	return true;
}

//在图中查找顶点u，存在返回顶点表中的下标，否则返回-1
int LocateVex(AMGraph G, string u)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		if (u == G.vexs[i])
		{
			return i;
		}
	}
	return -1;
}

打印邻接矩阵 

//打印邻接矩阵
void PrintVex(AMGraph G)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
				cout << G.arcs[i][j] << "\t";
		}
		cout << endl;
	}
}

无向图邻接矩阵深度优先遍历（DFS）

1、在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1；

2、再从w1出发，访问与w1邻接但还未被访问过的顶点w2;

3、然后再从w2出发，进行类似的访问，...

4、如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。

5、如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问;

6、如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

bool visited[MVNum]; //深度优先访问标志数组， 其初值为 "false"

//无向图深度优先遍历
void DFS(AMGraph G, int v)
{
	cout << G.vexs[v] << " "; //访问第v个顶点
	visited[v] = true; //访问后标志数组中第v个顶点设为true（1）
	for (int w = 0; w < G.vexnum; w++) //依次检查邻接矩阵v所在行
	{
		if ((G.arcs[v][w]) != 0 && (!visited[w])) //表示w是v的邻接点， 如果w未访问， 则递归调用DFS
		{
			DFS(G, w);
		}
	}
}

无向图邻接矩阵广度优先遍历（BFS）

1、从图的一结点出发，首先依次访问该结点的所有邻接结点v1,v2......vn再按这些顶点被访问的先后次序依次访问与它们相邻的所有未被访问的顶点。

2、重复此过程，直至所有顶点均被访问为止。

bool visited1[MVNum]; //广度优先访问标志数组， 其初值为 "false"

//无向图广度优先遍历
void BFS(AMGraph G, int v)
{
	cout << G.vexs[v] << " "; //访问第v个顶点
	visited1[v] = true;//访问后标志数组中第v个顶点设为true（1）
	queue<int>Q;//创建队列Q
	Q.push(v); //v进队
	while (!Q.empty())//队列非空
	{
		int p = Q.front(); //取出队头元素赋给p
		for (int i = 0; i < G.vexnum; i++)
		{
			if ((G.arcs[p][i] != 0) && (!visited1[i]))//判断i是否是p未访问的邻接点
			{
				cout << G.vexs[i] << " ";//访问第i个顶点
				Q.push(i);//i进队
				visited1[i] = true;
			}
		}
		Q.pop();//删除队头元素
	}
}

测试 

int main()
{
	AMGraph G;
	CreateUDN(G); //构造图
	cout << "图G的邻接矩阵为：" << endl;
	PrintVex(G); //打印
	int v = 0;
	cout << "广度优先遍历为：" << endl;
	BFS(G, v);
	cout << endl;
	cout << "深度优先遍历为：" << endl;
	DFS(G, v);
	cout << endl;

	system("pause");
	return 0;
}
C++构造无向图，邻接矩阵，深度优先遍历，广度优先遍历
C++构造无向图，邻接矩阵，深度优先遍历，广度优先遍历

 完整代码 

#include<iostream>
using namespace std;
#include<queue>

#define MVNum 100 //最大顶点数

//定义无向图邻接矩阵
struct AMGraph
{
	string vexs[MVNum]; //顶点表
	int arcs[MVNum][MVNum]; //邻接矩阵
	int vexnum, arcnum; //图的当前定点数和边数
};

bool visited[MVNum]; //深度优先访问标志数组， 其初值为 "false"

bool visited1[MVNum]; //广度优先访问标志数组， 其初值为 "false"


int LocateVex(AMGraph G, string u);

//创建无向图
bool CreateUDN(AMGraph& G)
{
	//1.输入顶点数和边数
	cout << "请输入顶点数：" << endl;
	cin >> G.vexnum;
	cout << "请输入边数：" << endl;
	cin >> G.arcnum;

	//2.依次输入顶点信息存入顶点表
	cout << "请输入顶点：" << endl;
	for (int i = 0; i < G.vexnum; i++)
	{
		cin >> G.vexs[i];
	}

	//3.初始化邻接矩阵,使每个权值初始化为极大值
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			G.arcs[i][j] = 0; //初始化邻接矩阵为0
		}
	}

	//4.构造邻接矩阵
	cout << "请输入一条边所依附的两个顶点及边的权值：" << endl;
	for (int k = 0; k < G.arcnum; k++)
	{
		string v1, v2;
		//int w;
		cin >> v1 >> v2; //输入一条边所依附的两个顶点及边的权值
		int i = LocateVex(G, v1); //确定v1,v2在G中的位置
		int j = LocateVex(G, v2);
		G.arcs[i][j] = 1; //边(v1,v2)的权值置为w
		G.arcs[j][i] = G.arcs[i][j]; //置边(v1,v2)的对称边(v2,v1)的权值为w
	}
	return true;
}

//在图中查找顶点u，存在返回顶点表中的下标，否则返回-1
int LocateVex(AMGraph G, string u)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		if (u == G.vexs[i])
		{
			return i;
		}
	}
	return -1;
}

//打印邻接矩阵
void PrintVex(AMGraph G)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
				cout << G.arcs[i][j] << "\t";
		}
		cout << endl;
	}
}

//无向图深度优先遍历
void DFS(AMGraph G, int v)
{
	cout << G.vexs[v] << " "; //访问第v个顶点
	visited[v] = true; //访问后标志数组中第v个顶点设为true（1）
	for (int w = 0; w < G.vexnum; w++) //依次检查邻接矩阵v所在行
	{
		if ((G.arcs[v][w]) != 0 && (!visited[w])) //表示w是v的邻接点， 如果w未访问， 则递归调用DFS
		{
			DFS(G, w);
		}
	}
}

//无向图广度优先遍历
void BFS(AMGraph G, int v)
{
	cout << G.vexs[v] << " "; //访问第v个顶点
	visited1[v] = true;//访问后标志数组中第v个顶点设为true（1）
	queue<int>Q;//创建队列Q
	Q.push(v); //v进队
	while (!Q.empty())//队列非空
	{
		int p = Q.front(); //取出队头元素赋给p
		for (int i = 0; i < G.vexnum; i++)
		{
			if ((G.arcs[p][i] != 0) && (!visited1[i]))//判断i是否是p未访问的邻接点
			{
				cout << G.vexs[i] << " ";//访问第i个顶点
				Q.push(i);//i进队
				visited1[i] = true;
			}
		}
		Q.pop();//删除队头元素
	}
}

int main()
{
	AMGraph G;
	CreateUDN(G); //构造图
	cout << "图G的邻接矩阵为：" << endl;
	PrintVex(G); //打印
	int v = 0;
	cout << "广度优先遍历为：" << endl;
	BFS(G, v);
	cout << endl;
	cout << "深度优先遍历为：" << endl;
	DFS(G, v);
	cout << endl;

	system("pause");
	return 0;
}
c++ 算法 数据结构 深度优先 宽度优先
上一篇: 真心让人难受，央视纪录片&lt;&lt;船政学堂&gt;&gt;同样是相同的说辞。一时间不知道到底有没有投降。小微在看到
下一篇: CKEditor和CKFinder在ASP.NET中的应用

继续阅读