#|图的邻接矩阵（广度优先遍历） #|类模板|DHU-----OJ|图论|c++|广度

目的：使用C++模板设计并逐步完善图的邻接矩阵抽象数据类型（ADT）。
内容：（1）请参照图的邻接矩阵模板类原型，设计并逐步完善图的邻接矩阵ADT。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。）
（2）设计并实现一个算法，使用队列，对一个已存在的图进行广度优先遍历（BFS)，并输出遍历的顶点线性序列。遍历的起点通过输入指定。注意：遍历时，仅从该点出发遍历整个图，如果图不连通，则只遍历一个子图。图的存储结构采用邻接矩阵。将其加入到ADT中。
函数原型：
void BFS_Traverse(int u); //BFS遍历
辅助函数原型：
（1）int GetFirstAdjVex(int u, int &v); //返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1
（2）int GetNextAdjVex(int u, int v, int &w); //返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1

输入说明：
建图的输入数据格式参见建图的算法说明。
第一行：图的类型
第二行：结点数
第三行：结点集
第四行：边数
第五行：边集
第六行：起始顶点的位序

输出说明：
第一行：顶点集
空行
第二行：邻接矩阵
空行
第三行：BFS遍历序列（结点之间用->分隔）

输入范例：
UDG
8
V1 V2 V3 V4 V5 V6 V7 V8
8
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
0

输出范例：
V1 V2 V3 V4 V5 V6 V7 V8
空行
0 1 1 0 0 0 0 0
1 0 0 1 1 0 0 0
1 0 0 0 0 1 1 0
0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 1
0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 1 0 0 0
空行
V1->V2->V3->V4->V5->V6->V7->V8

#include #include #include #include #include #include #include using namespace std; string b[10001]; //放顶点集 queue q; //这个队列用于广度优先搜索存放顶点 bool visited[10001]={ false }; //这样写就都是false了把所有顶点都设为没有被访问过//DG（有向图） DN（有向网） UDG（无向图） UDN（无向网）template//顶点类型与边的类型 class adjmatrix_graph{//顶点用字符串，边用整型 private: int Vers; //顶点数 int Edges; //边数 TypeOfEdge **edge; //邻接矩阵 //(TypeOfEdge表示顶点关系类型。对于无权图，用1或0，表示相邻否；对于带权图，则为权值类型) TypeOfVer *ver; //存放结点值 TypeOfEdge noEdge; //邻接矩阵中的∞的表示值 string GraphKind; //图的种类标志 bool DFS(int u,int &num,int visited[]); //DFS遍历（递归部分） public: //构造函数构造一个只有结点没有边的图。4个参数的含义： //图的类型、结点数、结点值和邻接矩阵中表示结点间没有边的标记 //（无权图：0，有权图：输入参数定） adjmatrix_graph(string kd,int vSize,TypeOfVer d[],TypeOfEdge noEdgeFlag){ GraphKind=kd; Vers=vSize; ver=new TypeOfEdge[Vers]; ver=d; //这个要写，然后就不用写下面的赋值了 noEdge=noEdgeFlag; //这个赋值一开始没写 //for(int i=0; i=Vers) return false; data=https://www.it610.com/article/ver[u]; return true; } //返回G中指定顶点u的第一个邻接顶点的位序（顶点集） //若顶点在G中没有邻接顶点，则返回-1 int GetFirstAdjVex(int u){ if(u<0||u>=Vers) return -1; for(int i=0; i=Vers||v<0||v>=Vers) return -1; for(int i=v+1; i=Vers) return "no"; return ver[x]; } //返回G中指定顶点的位置,这个返回的是下标 int LocateVer2(TypeOfVer data){//遍历用这个函数 for(int i=0; i=0; w=GetNextAdjVex(m,w)){ if(!visited[w]){ cout<<"->"< int Get_InDegree(int u); ~adjmatrix_graph() {//析构函数 for(int i=0; i void shuchu(adjmatrix_graph &tu,int n){ //cout< int adjmatrix_graph::Get_InDegree(int u){ if(GetGraphKind()[0]=='U')//无向图直接返回-1 return -1; int n=0,m; string kkk; kkk=LocateVer1(u); //没有找到这个顶点返回-1 if(kkk=="no") return -1; //cout<>n; //顶点数 for(int i=0; i>b[i]; //顶点集合 //int no; //cin>>no; //无边标记 cin>>m; //边数 int **a; a=new int* [m]; for(int i=0; i>a[i][0]>>a[i][1]; //输入边集 //string ans; //cin>>ans; //输入的顶点 int k; //代表顶点的序号 cin>>k; /*int *c; c=new int [m]; for(int i=0; i>c[i]; //输入权集*/ //int u,v; //cin>>u>>v; //输入要删除边的弧头和弧尾 adjmatrix_graph,int> tu(str,n,b,m,a); shuchu(tu,n); tu.BFS_Traverse(k); return 0; }

广度优先搜索的思路：
【#|图的邻接矩阵（广度优先遍历）】设立一个查看结点是否被访问过的数组，一开始都是false，被访问过之后是true。这个数组的作用就是保证每个结点只被访问一次。
还需要用到队列，访问过一个之后需要将其入队，依次访问其相邻的结点，没被访问就输出并入队，然后继续执行循环，直到所有结点都被访问一遍。
这样广度优先搜索就结束了。