php中文网 | cnphp.com

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
查看: 346|回复: 0

图的宽度_深度优先遍历(链表)

[复制链接]

2573

主题

2580

帖子

9105

积分

管理员

Rank: 9Rank: 9Rank: 9

UID
1
威望
0
积分
6410
贡献
0
注册时间
2021-4-14
最后登录
2024-3-29
在线时间
653 小时
QQ
发表于 2022-7-28 12:55:33 | 显示全部楼层 |阅读模式
[mw_shl_code=cpp,true]#include<iostream>
#include<malloc.h>
using namespace std;
#define MAX 20                 //定义常量值为20

int visited[MAX];         //定义标志数组(全局)

//定义边结构(边界点)
typedef struct Anode{
    int adjvex;                         //邻接点域(数据域)
    struct Anode *next;         //指向下一邻接点的指针域
}ALnode;
//定义顶点表结点
typedef struct vexnode{
    char data;                                 //顶点域
    ALnode *firstal;                 //指向第一条边结点
}VexHeadNode;
//定义图的邻接表存储结构
typedef struct{
    VexHeadNode adjlist[MAX];         //邻接表头结点数组
    int n;                                                 //图的当前顶点数
    int e;                                                 //图的当前弧数,即边数
}Graph;

//建立图的邻接表
void createGraph(Graph &G){
    int i,j,k;                         //辅助变量
    ALnode *p;                         //辅助结点
    cout<<"输入图的顶点数:";
    cin>>G.n;
    cout<<"输入图的边数:";
    cin>>G.e;
    cout<<endl;                 //换行
    cout<<"输入图的各顶点(存储序号从0开始):"<<endl;
    for(i=0;i<G.n;i++){                                  //生成有n个顶点的顶点表
        cout<<"第"<<i<<"个顶点信息:";
        cin>>G.adjlist.data;                 //顶点数据存入表头
        G.adjlist.firstal=NULL;                 //边表头指针域置为空
    }
    cout<<endl;                 //换行
    cout<<"输入图中的边,顶点序号从0开始:"<<endl;
    for(k=0;k<G.e;k++){
        cout<<endl;         //换行
        cout<<"输入第"<<k+1<<"条边:"<<endl;
        cout<<"输入出发顶点的序号:";
        cin>>i;
        cout<<"输入指向顶点的序号:";
        cin>>j;
        //邻接表存储连接
        p=(ALnode *)malloc(sizeof(ALnode)); //分配存储空间
        p->adjvex=j;                                                 //指向顶点的序号存入邻接点数据域
        p->next=G.adjlist.firstal;                 //新的结点的指针域置为空
        G.adjlist.firstal=p;                         //新结点信息依次存入邻接表中
    }
}

//输出邻接表
void printGraph(Graph G){
    int i;                         //辅助变量
    ALnode *p;                 //辅助结点
    cout<<"邻接表中的存储内容如下所示:"<<endl;
    for(i=0;i<G.n;i++){
        cout<<i<<' '<<G.adjlist.data;         //输出表头结点的数据
        p=G.adjlist.firstal;                         //指向下一结点
        while(p!=NULL){
            cout<<"--->"<<p->adjvex<<' ';         //顺次输出结点信息
            p=p->next;
        }
        cout<<endl;         //换行
    }
}

//深度优先遍历
void DFSTraverse(Graph G,int v){
    ALnode *p;                                         //辅助结点
    cout<<"("<<v<<","<<G.adjlist[v].data<<")"<<' ';         //输出顶点信息
    visited[v] = 1;  
    p=G.adjlist[v].firstal;         //访问第v个顶点
    while(p!=NULL){
        if(visited[p->adjvex]==0){
            DFSTraverse(G,p->adjvex);
        }
        p=p->next;
    }
}

//广度优先遍历
void BFSTraverse(Graph G,int v){
    int i,j,visited[MAX];                         //辅助变量、标志数组
    ALnode *p;                                                 //辅助结点
    int queue[MAX],front=0,rear=0;         //定义循环队列  
    for(i=0;i<G.n;i++){  
        visited=0;                                 //标志数组信息初始化
    }
    cout<<"("<<v<<","<<G.adjlist[v].data<<")"<<' ';         //输出顶点信息
    visited[v]=1;                                         //对应顶点的标志置为1
    rear=(rear+1)%MAX;                                 //队尾指针后移
    queue[rear]=v;                                         //查找的顶点对应序号入队列
    //循环遍历
    while(front!=rear){
        front=(front+1)%MAX;                 //队头指针后移
        j=queue[front];                         //从队列中取出顶点对应序号
        p=G.adjlist[j].firstal;         //取对应序号的顶点信息
        while(p!=NULL){
            if(visited[p->adjvex]==0){
                visited[p->adjvex]=1;
                cout<<"("<<p->adjvex<<","<<G.adjlist[p->adjvex].data<<")"<<' '; //输出顶点信息
                rear=(rear+1)%MAX;                         //队尾指针后移
                queue[rear]=p->adjvex;                 //查找的顶点对应序号入队列
            }
            p=p->next;
        }
    }
}

//主函数
int main(){
    Graph G;                                                 //定义图结构变量
    int v1,v2,choose;
    cout<<"请选择:0-退出;1-创建有向图(采用邻接表存储结构);2-深度优先遍历;3-广度优先遍历"<<endl;
    cin>>choose;
    while(choose!=0){
        switch(choose){
            case 1:{
                createGraph(G);                 //创建有向图
                printGraph(G);                         //输出
                break;
            }
            case 2:{
                cout<<"输入从哪个顶点开始遍历(序号从0开始):";
                cin>>v1;
                DFSTraverse(G,v1);
                for(int i=0;i<G.n;i++){
                    visited=0;                 //标志数组信息初始化
                }
                cout<<endl;
                break;
            }
            case 3:{
                cout<<"输入从哪个顶点开始遍历(序号从0开始):";
                cin>>v2;
                BFSTraverse(G,v2);
                cout<<endl;
                break;
            }
            default:cout<<"输入错误,请重新选择!"<<endl;
        }
        cout<<"请选择:0-退出;1-创建有向图(采用邻接表存储结构);2-深度优先遍历;3-广度优先遍历"<<endl;
        cin>>choose;
    }
}
[/mw_shl_code]





上一篇:javaScript Cookie读写
下一篇:OpenCV将图像分离为rgb,hls,hsv通道并显示
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|php中文网 | cnphp.com ( 赣ICP备2021002321号-2 )51LA统计

GMT+8, 2024-3-29 15:53 , Processed in 0.181787 second(s), 35 queries , Gzip On.

Powered by Discuz! X3.4 Licensed

Copyright © 2001-2020, Tencent Cloud.

申明:本站所有资源皆搜集自网络,相关版权归版权持有人所有,如有侵权,请电邮(fiorkn@foxmail.com)告之,本站会尽快删除。

快速回复 返回顶部 返回列表