怎么清理网站后门文件,网站建设类论文格式,腾讯企点是什么软件,凤台县美丽乡村建设网站目录
基本要求#xff1a;
邻接表的结构体#xff1a;
图的邻接表创建#xff1a;
图的广度优先遍历#xff08;BFS#xff09;#xff1a;
邻接表的打印输出#xff1a;
完整代码#xff1a;
测试数据#xff1a;
结果运行#xff1a; 通过给出的图的顶点和… 目录
基本要求
邻接表的结构体
图的邻接表创建
图的广度优先遍历BFS
邻接表的打印输出
完整代码
测试数据
结果运行 通过给出的图的顶点和边的信息构建无向图的邻接表存储结构。在此基础上从A顶点开始对无向图进行广度优先遍历输出遍历序列。
基本要求
1从测试数据读入顶点和边信息建立无向图邻接表存储结构
2把构建好的邻接表输入显示
3从A顶点开始编写BFS广度优先遍历算法
4输出广度优先遍历序列。
邻接表的结构体
typedef char VerTexType;
typedef struct Arcnode//边节点
{int adjvex;//该边所指向的顶点的位置struct Arcnode* nextarc;//指向下一条边的指针
}Arcnode;
typedef struct vnode//顶点节点
{VerTexType data;//顶点信息Arcnode* firstarc;//指向第一条依附该顶点的边的指针
}Vnode, AdjList[MVNum];
typedef struct//图
{AdjList vertices;//头顶点int vexnum, arcnum;//图当前顶点数和边数
}ALGraph;图的邻接表创建
bool CreateUDG(ALGraph G)
{cin G.vexnum G.arcnum;//输入总顶点数总边数for (int i 0; i G.vexnum; i)//输入各点构造表头结点表{cin G.vertices[i].data;//输入顶点值G.vertices[i].firstarc NULL;//初始化表头节点指针域mp[G.vertices[i].data] 0;//辅助数组是否访问过该点0表示没访问过}VerTexType v1, v2;for (int k 0; k G.arcnum; k){cin v1 v2;//输入边相邻节点int i LocateVex(G, v1);int j LocateVex(G, v2);//确定v1,v2位置Arcnode* p1, * p2;p1 new Arcnode;//生成一个新的边节点p1-adjvex j;//邻节点序号为jp1-nextarc G.vertices[i].firstarc;G.vertices[i].firstarc p1;//将新节点插入顶点vi的边表头部p2 new Arcnode;p2-adjvex i;//邻接点序号为ip2-nextarc G.vertices[j].firstarc;G.vertices[j].firstarc p2;//将新节点插入顶点vj的表头部}return 1;
}图的广度优先遍历BFS
void BFS(ALGraph G,VerTexType u)
{cout”BFS序列”endl;queueVerTexType q;q.push(u);while (!q.empty()){u q.front();q.pop();int i LocateVex(G, u);//取该点的位置if (!mp[G.vertices[i].data])//辅助数组是否访问过{cout G.vertices[i].data ;mp[G.vertices[i].data] 1;}Arcnode* p;p G.vertices[i].firstarc;while (p ! NULL)//访问该头节点的链表{if (!mp[G.vertices[p-adjvex].data]){cout G.vertices[p-adjvex].data ;mp[G.vertices[p-adjvex].data] 1;q.push(G.vertices[p-adjvex].data);}p p-nextarc;}}
}邻接表的打印输出
bool Print(ALGraph G)
{cout 邻接表 endl;for (int i 0; i G.vexnum; i){cout G.vertices[i].data ;Arcnode* p;p G.vertices[i].firstarc;while (p ! NULL){cout G.vertices[p-adjvex].data ;p p-nextarc;}cout endl;}return 1;
}完整代码
#includequeue
#includemap
#define MVNum 100
using namespace std;
typedef char VerTexType;
mapVerTexType,int mp;
typedef struct Arcnode//边节点
{int adjvex;//该边所指向的顶点的位置struct Arcnode* nextarc;//指向下一条边的指针
}Arcnode;
typedef struct vnode//顶点节点
{VerTexType data;//顶点信息Arcnode* firstarc;//指向第一条依附该顶点的边的指针
}Vnode, AdjList[MVNum];
typedef struct//图
{AdjList vertices;//头顶点int vexnum, arcnum;//图当前顶点数和边数
}ALGraph;
int LocateVex(ALGraph G, VerTexType u)//取该点位置
{for (int i 0; i G.vexnum; i)if (u G.vertices[i].data) return i;return -1;
}
bool CreateUDG(ALGraph G)
{cin G.vexnum G.arcnum;//输入总顶点数总边数for (int i 0; i G.vexnum; i)//输入各点构造表头结点表{cin G.vertices[i].data;//输入顶点值G.vertices[i].firstarc NULL;//初始化表头节点指针域mp[G.vertices[i].data] 0;}VerTexType v1, v2;for (int k 0; k G.arcnum; k){cin v1 v2;//输入边相邻节点int i LocateVex(G, v1);int j LocateVex(G, v2);//确定v1,v2位置Arcnode* p1, * p2;p1 new Arcnode;//生成一个新的边节点p1-adjvex j;//邻节点序号为jp1-nextarc G.vertices[i].firstarc;G.vertices[i].firstarc p1;//将新节点插入顶点vi的边表头部p2 new Arcnode;p2-adjvex i;//邻接点序号为ip2-nextarc G.vertices[j].firstarc;G.vertices[j].firstarc p2;//将新节点插入顶点vj的表头部}return 1;
}
bool Print(ALGraph G)
{cout 邻接表 endl;for (int i 0; i G.vexnum; i){cout G.vertices[i].data ;Arcnode* p;p G.vertices[i].firstarc;while (p ! NULL){cout G.vertices[p-adjvex].data ;p p-nextarc;}cout endl;}return 1;
}
void BFS(ALGraph G,VerTexType u)
{cout”BFS序列”endl;queueVerTexType q;q.push(u);while (!q.empty()){u q.front();q.pop();int i LocateVex(G, u);//取该点的位置if (!mp[G.vertices[i].data])//辅助数组是否访问过{cout G.vertices[i].data ;mp[G.vertices[i].data] 1;}Arcnode* p;p G.vertices[i].firstarc;while (p ! NULL)//访问该头节点的链表{if (!mp[G.vertices[p-adjvex].data]){cout G.vertices[p-adjvex].data ;mp[G.vertices[p-adjvex].data] 1;q.push(G.vertices[p-adjvex].data);}p p-nextarc;}}
}
int main()
{ALGraph G;CreateUDG(G);Print(G);BFS(G, A);//从A开始遍历
}测试数据
[测试数据] 12 16 A B C D E F G H I J K L A D B C B D B F C F D G E B E F E G E H F I G K H I I K J K K L 测试数据说明 1.第一行两个整数分别表示无向图中的顶点数m和边数n 2.第二行中的m个整数表示m个顶点数据元素数据类型为字符型 3.从第三行开始连续n行数据每一行两个字符表示无向图中的一条边关联的两个顶点数据信息。 4.无向图如下图示
结果运行
