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）
	queueQ;//创建队列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;
}

完整代码

#includeusing namespace std;
#include#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）
	queueQ;//创建队列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;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章名称：C++构造无向图，邻接矩阵，深度优先遍历，广度优先遍历-创新互联
转载来源：http://6mz.cn/article/dpdogj.html