非连通图深度优先遍历和广度优先遍历
程序员文章站
2022-05-24 09:10:59
...
预定义:
typedef struct ArcNode{
int adjvex;
ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
VerTexType data;
ArcNode *firstarc;
}VNode,AdjList[MVNum];
typedef struct{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
构造邻接链表:
//记录节点是否已经被访问:
bool visited[MAXSIZE];
int LocateVex(AMGraph *G,VerTexType v){
for(int i=0;i<G->vexnum;i++){
if(G->vex[i]==v)
return i;
}
return -1;
}
int CreateGraph()
{
ALGraph* G;
G->vexnum=x;
G->arcnum=x;
for(i = 0;i<G->vexnum;i++){
G->vertices[i].data=x;
G->vertices[i].firstarc=NULL;
visited[i] = false;
}
for(k=0;k<G->arcnum;k++){
//v1(i)-v2(j),无向
i = LocateVex(G, v1);
j = LocateVex(G, v2);
//头插法,无向图两个结点的边都要插入
ArcNode p1;
p1->adjvex = j;
p1->nextarc = G->vertices[i].firstarc;
G->vertices[i].firstarc = p1;
ArcNode p2;
p2->adjvex = i;
p2->nextarc = G->vertices[j].firstarc;
G->vertices[j].firstarc = p1;
}
}
深度优先遍历DFS:
//从顶点v出发,深度遍历图G
void DFS(ALGraph G,int v){
visit(v);
visited[v]=true;
for(p=G.vertices[v].firstarc;p;p=p->nextarc){
if (!visited[p->adjvex])
DFS(G, p->adjvex);
}
}
//因为是非连通图,依次检查结点i有没有visit,没有则进行一次深度遍历,每进行一次DFS,说明有一个连通分量
void DFSTraverse(ALGraph G){
for(i=0;i<G.vexnum;i++)
if(!visited[i])
DFS(G,i);
}
广度优先遍历BFS:
//与树的层次遍历完全一致
//从顶点v出发,广度优先遍历图G,算法借助一个辅助队列
void BFS(ALGraph G,int v){
visit(v);
visited[v]=true;
Enqueue(Q,v);
while(!Empty(Q)){
DeQueue(Q,v);
for(p=G.vertices[v].firstarc;p;p=p->nextarc)
if(!visited[p->adjvex]){
visit(p->adjvex);
visited[p->adjvex]=true;
EnQueue(Q,p->adjvex);
}
}
}
//因为是非连通图,依次检查结点i有没有visit,没有则进行一次广度遍历,每进行一次BFS,说明有一个连通分量
void BFSTraverse(ALGraph G){
InitQueue(Q);
for(i=0;i<G.vexnum;i++)
if(!visited[i])
BFS(G,i);
}
上一篇: AMD三代APU有哪些 AMD第三代APU处理器新特性详细介绍
下一篇: 动态生成bean实体