遍历(C++)"/>
邻接表储存图实现广度优先遍历(C++)
目录
基本要求:
邻接表的结构体:
图的邻接表创建:
图的广度优先遍历(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;queue<VerTexType> 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;
}
完整代码:
#include<queue>
#include<map>
#define MVNum 100
using namespace std;
typedef char VerTexType;
map<VerTexType,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;queue<VerTexType> 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.无向图如下图示: |
结果运行:
更多推荐
邻接表储存图实现广度优先遍历(C++)
发布评论