图的邻接表的创建和广度优先遍历

#include<iostream>
using namespace std;
#define MVNum 100
//最大顶点数
#define MAXQSIZE 100
//最大队列长度
typedef char VerTexType;
//假设顶点的数据类型为字符型
typedef int ArcType;
//假设边的权值类型为整型
int visited[MVNum];
//访问标志数组，其初值为"false"
typedef char VerTexType;
//顶点信息
typedef int OtherInfo;
//和边相关的信息
//- - - - -图的邻接表存储表示- - - - -
//---------表结点ArcNode--------
typedef struct ArcNode
//表结点
{
int adjvex;
//该边所指向的顶点的位置
struct ArcNode* nextarc;
//指向下一条边的指针
OtherInfo info;
//和边相关的信息
} ArcNode;
//---------头结点VNode--------
//---------VerTexType类型顶点信息
//--------- ArcNode类型第一个邻接顶点表结点指针
typedef struct VNode
{
VerTexType data;
ArcNode* firstarc;
//指向第一条依附该顶点的边的指针
} VNode, AdjList[MVNum];
//AdjList表示邻接表类型
//-----------邻接表------------
typedef struct
{
AdjList vertices;
int vexnum, arcnum;
//图的当前顶点数和边数
} ALGraph;
//----队列的定义及操作--------
typedef struct
{
int* base;//存储空间的基地址
int front;//头指针
int rear; //尾指针
} sqQueue;
void InitQueue(sqQueue& Q)//构造一个空队列Q
{
Q.base = new int[MAXQSIZE];//为队列分配一个最大容量为MAXQSIZE的数组空间
Q.front = Q.rear = 0;
//将头指针和尾指针置为0，队列为空
}//InitQueue
void EnQueue(sqQueue& Q, ArcType e)//插入元素e为Q的新的队尾元素
{
Q.base[Q.rear] = e;//新元素插入队尾
Q.rear = (Q.rear + 1) % MAXQSIZE;//队尾指针加1
}//EnQueue
bool QueueEmpty(sqQueue Q)//判断是否为空队
{
if (Q.front == Q.rear)return 1;//如果队头指针等于队尾指针返回1
else return 0;
//否则返回0
}//QueueEmpty
void DeQueue(sqQueue& Q, ArcType& u)//队头元素出队并置为u
{
u = Q.base[Q.front]; //将队头元素赋值给u
Q.front = (Q.front + 1) % MAXQSIZE;//队头指针加1
}//DeQueue
//--------------------------------------------------
int LocateVex(ALGraph G, VerTexType v)//确定点v在G中的位置
{
int n;
for (int i = 0; i < G.vexnum; i++)//遍历整个顶点数组，相等返回 位置下标
{
if (v == G.vertices[i].data)
{
n = i;
}
}
return n;
}//LocateVex
void CreateUDG(ALGraph& G)
{
//采用邻接表表示法，创建无向图G
cout << "请输入总顶点数，总边数中间以空格隔开:";
cin >> G.vexnum >> G.arcnum; //输入总顶点数，总边数
cout << "输入点的名称，如 A " << endl;
for (int i = 0; i < G.vexnum; i++)//输入点
{
cin >> G.vertices[i].data;
//输入顶点值
G.vertices[i].firstarc = NULL;//初始化表头节点的指针域为NULL
}
cout << "请输入一条边依附的顶点,如 a b" << endl;
for (int k = 0; k < G.arcnum; k++)//输入各边，构造邻接表
{
VerTexType v1, v2;
cin >> v1 >> v2;//输入一条边依附的两个顶点
int i = LocateVex(G, v1);
int j = LocateVex(G, v2);//确定v1,v2在G中的位置
ArcNode* p1 = new ArcNode;//生成一个新的边节点*p1
p1->adjvex = j;//邻接点序号为j
p1->nextarc = G.vertices[i].firstarc;//将新节点*p1插入顶点vi的边表头部
G.vertices[i].firstarc = p1;
ArcNode* p2 = new ArcNode;//生成另一个对称的新的边节点*p2
p2->adjvex = i;//邻接点序号为i
p2->nextarc = G.vertices[j].firstarc;
G.vertices[j].firstarc = p2;//将新节点*p2插入顶点vj的边表头部
}
}//CreateUDG
int FirstAdjVex(ALGraph G, int v)//返回v的第一个邻接点
{
if (G.vertices[v].firstarc)//邻接点不为空
return G.vertices[v].firstarc->adjvex;//返回第一个邻接点的顶点位置
else return -1;//为空，返回-1
}//FirstAdjVex
//返回v相对于w的下一个邻接点的顶点位置
int NextAdjVex(ALGraph G, int u, int w)
{
while (G.vertices[u].firstarc != NULL && G.vertices[u].firstarc->adjvex != w)
// u的第一个邻接点不为空，并且该点下一个的顶点位置不等于w
{//让u的邻接点指向下一个
G.vertices[u].firstarc = G.vertices[u].firstarc->nextarc;
}
// while循环一直到w的位置，该点不为空，且该点的下一个也不为空
if (G.vertices[u].firstarc != NULL && G.vertices[u].firstarc->nextarc != NULL)
return G.vertices[u].firstarc->nextarc->adjvex;
//返回w位置的下一个邻接点的顶点位置
else
return -1;//返回v相对于w的下一个邻接点
}//NextAdjVex
void BFS(ALGraph G, int v)//按广度优先非递归遍历连通图G
{
sqQueue Q;
int u, w;
cout<<G.vertices[v].data<<" ";visited[v] = true;
//访问第v个顶点
InitQueue(Q);
//辅助队列Q初始化，置空
EnQueue(Q, v);
//v进队
while (!QueueEmpty(Q)) {
//队列非空
DeQueue(Q, u);
//队头元素出队并置为u
for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
//从第一条弧开始依次的去找结点，然后再找与下一条弧相连的节点。
if (!visited[w])//w为u的尚未访问的邻接顶点
{
cout << G.vertices[w].data<<" ";
visited[w] = true;
EnQueue(Q, w); //w进队
}//访问每个邻接点，访问完以后将每个邻接点入队
}//while
}//BFS
int main()
{
ALGraph G;//定义一个邻接表变量
int i=0;
CreateUDG(G);//创建邻接表
cout << endl;
cout << "无向连通图G创建完成！" << endl << endl;
cout<<"输出邻接表的数据：n"<<endl;
for(int k=0;k<G.vexnum;k++)
{
ArcNode* p = new ArcNode;//生成一个新的节点用来遍历邻接表的每一个链表
p=G.vertices[k].firstarc;//p指向k的第一个邻接点
while(p)
{
cout<<p->adjvex<<" ";//输出顶点位置
p=p->nextarc;
}
cout<<endl;
}
cout << "广度优先搜索遍历连通图结果：" << endl;
BFS(G, i);// 广度优先搜索遍历
cout <<endl;
return 0;
}//main

最后

以上就是含糊黄蜂为你收集整理的图的邻接表的创建和广度优先遍历的全部内容，希望文章能够帮你解决图的邻接表的创建和广度优先遍历所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。