精华内容
下载资源
问答
  • 邻接表的深度优先遍历
    2022-07-06 09:30:48

    问题描述:
    设计并实现一个算法,应用递归的程序设计方法,对一个已存在的图进行广度优先遍历(BFS),并输出遍历的顶点线性序列。遍历的起点通过输入指定。
    注意:遍历时,仅从该点出发遍历整个图,如果图不连通,则只遍历一个子图。图的存储结构采用邻接表。将其加入到ADT中。
    参考函数原型:
    //BFS遍历
    template<class TypeOfVer, class TypeOfEdge>
    void adjlist_graph<TypeOfVer, TypeOfEdge>::BFS_Traverse(int u);

    输入说明 :
    建图的输入数据格式参见建图的算法说明。(以无权图为例)
    第一行:图的类型
    第二行:结点数
    第三行:结点集
    第四行:边数
    第五行:边集
    第六行:起始顶点的位序

    输出说明 :
    第一行:顶点集
    第二行:邻接表
    空行
    第三行:BFS遍历序列(结点之间用->分隔)

    输入范例 :
    UDG
    8
    V1 V2 V3 V4 V5 V6 V7 V8
    8
    0 1
    0 2
    1 3
    1 4
    2 5
    2 6
    3 7
    4 7
    5

    输出范例 :
    V1 V2 V3 V4 V5 V6 V7 V8
    V1->2->1->nullptr
    V2->4->3->0->nullptr
    V3->6->5->0->nullptr
    V4->7->1->nullptr
    V5->7->1->nullptr
    V6->2->nullptr
    V7->2->nullptr
    V8->4->3->nullptr
    (空行)
    V6->V3->V7->V1->V2->V5->V4->V8

    #include<iostream>
    #include<vector>
    #include<string>
    #include<sstream>
    #include<queue>
    #include<stack>
    #include<cmath>
    using namespace std;
    string b[10001];//用来存放顶点集
    queue<int> q;//这个队列用于广度优先搜索存放顶点
    bool visited[1001]={false};//一开始设为都没有被访问过
    vector<int> po(10001);
    //DG(有向图)  DN(有向网)  UDG(无向图) UDN(无向网)
    
    //图的邻接表模板类原型参考如下:
    //边表的顶点定义
    template<class TypeOfEdge>//这个就是在边上的顶点定义
    struct edgeNode{
        int data;
        TypeOfEdge weight;
        edgeNode<TypeOfEdge> *next;
        //构造函数,用于构造其他顶点(无权图)
        //函数参数表中的形参允许有默认值,但是带默认值的参数需要放后面
        edgeNode(int d,edgeNode<TypeOfEdge> *ptr=NULL){ data=d;next=ptr; }
        //构造函数,用于构造其他顶点(带权图)
        //函数参数表中的形参允许有默认值,但是带默认值的参数需要放后面
        edgeNode(int d,TypeOfEdge w,edgeNode<TypeOfEdge> *ptr=NULL){
            data=d; weight=w; next=ptr;
        }
        int getData(){ return data; }//取得顶点的序号(顶点集)
        TypeOfEdge getWeight(){ return weight; }//取得边集中对应边的权值
        void SetLink(edgeNode<TypeOfEdge> *link ){ next=link; }//修改顶点的next域
        void SetData(int value){ data=value; }//修改顶点的序号(顶点集)
        void SetWeight(TypeOfEdge value){ weight=value; }//修改边集中对应边的权值
    };
    
    //图的邻接表类   这个结构体是存储顶点的结构体,里面包括顶点和它的下一个指针
    template<class TypeOfVer,class TypeOfEdge>
    struct verNode{
        TypeOfVer ver;//存放顶点名称
        edgeNode<TypeOfEdge> *head;//顶点的指针
        verNode(edgeNode<TypeOfEdge> *h=NULL){ head=h; }
        TypeOfVer getVer(){ return ver; }//取得顶点值(顶点集)
        edgeNode<TypeOfEdge> *getHead(){ return head; }//取得对应的边表的头指针
        void setVer(TypeOfVer value){ ver=value; }//设置顶点值(顶点集)
        void setHead(edgeNode<TypeOfEdge> *value){ head=value; }//设置对应的边表的头指针
    };
    
    template<class TypeOfVer,class TypeOfEdge>//顶点类型  边的类型
    class adjlist_graph{
        private:
           int Vers;//顶点数
           int Edges;//边数
           string GraphKind;//图的种类标志
           verNode<TypeOfVer,TypeOfEdge> *verList;//按顺序存储结构存储顶点集
           bool Delete_Edge(int u,int v);
           bool DFS(int u,int num,int visited[]);//DFS遍历(递归部分)
        public:
           //构造函数构造一个只有顶点没有边的图
           //3个参数的含义:图的类型、顶点数、顶点值
           adjlist_graph(string kd,int vSize,TypeOfVer d[]){
                GraphKind=kd;
                Vers=vSize;
                verList=new verNode<TypeOfVer,TypeOfEdge> [Vers];//建立顶点值
                for(int i=0;i<Vers;++i){
                    verList[i].ver=d[i];
                    verList[i].head=NULL;//一开始构造的时候顶点还没有相邻的顶点
                }
           }
           //构造函数构造一个无权图
           //5个参数的含义:图的类型、顶点数、顶点集、  边数和边集
           adjlist_graph(string kd,int vSize,TypeOfVer d[],int eSize,int **e){
                GraphKind=kd;
                Vers=vSize;
                Edges=eSize;
                verList=new verNode<TypeOfVer,TypeOfEdge> [Vers];//建立顶点值
                for(int i=0;i<Vers;++i){
                    verList[i].ver=d[i];
                    verList[i].head=NULL;//一开始构造的时候顶点还没有相邻的顶点
                }
                for(int i=0;i<Edges;++i){//从边开始构造顶点
                    for(int j=0;j<Vers;++j){
                        if(e[i][0]==j){
                            if(GraphKind[0]!='U'){//有向图的情况就只有1个方向
                                Insert_Edge1(e[i][0],e[i][1]);
                                Edges-=1;
                                break;
                            }
                            else{//无向图的表结点的个数是边数的2倍
                                Insert_Edge1(e[i][0],e[i][1]);
                                Insert_Edge1(e[i][1],e[i][0]);
                                Edges-=2;
                                break;
                            }
                        }
                    }
                }
           }
           //构造函数构造一个有权图
           //6个参数的含义:图的类型、顶点数、顶点集、      边数、边集         权集
           adjlist_graph(string kd,int vSize,TypeOfVer d[],int eSize,int **e,TypeOfEdge w[]){
                GraphKind=kd;
                Vers=vSize;
                Edges=eSize;
                verList=new verNode<TypeOfVer,TypeOfEdge> [Vers];//建立顶点值
                for(int i=0;i<Vers;++i){
                    verList[i].ver=d[i];
                    verList[i].head=NULL;//一开始构造的时候顶点还没有相邻的顶点
                }
                for(int i=0;i<Edges;++i){//从边开始构造顶点
                    for(int j=0;j<Vers;++j){
                        if(e[i][0]==j){
                            if(GraphKind[0]!='U'){//有向图的情况就只有1个方向
                                Insert_Edge2(e[i][0],e[i][1],w[i]);
                                Edges-=1;
                                break;
                            }
                            else{//无向图的表结点的个数是边数的2倍
                                Insert_Edge2(e[i][0],e[i][1],w[i]);
                                Insert_Edge2(e[i][1],e[i][0],w[i]);
                                Edges-=2;
                                break;
                            }
                        }
                    }
                }
           }
           bool GraphisEmpty(){ return Vers==0; }//判断图空否
           string GetGraphKind(){ return GraphKind; }//返回图的类型
           int* GetVerNum(){ return &Vers; }//取得当前顶点数
           int* GetEdgeNum(){ return &Edges; }  //取得当前边数
           bool GetVer(int u,TypeOfVer &data){//取得G中指定顶点的值
                return true;
           }
           //返回G中指定顶点u的第一个邻接顶点的位序(顶点集)
           //若顶点在G中没有邻接顶点,则返回-1
           int GetFirstAdjVex(int u){
                if(u<0||u>=Vers)
                    return false;
                int v;
                if(verList[u].head!=NULL){
                    v=verList[u].head->data;
                    return v;
                }
                v=-1;
                return -1;
           }
           //返回G中指定顶点u的下一个邻接顶点(相对于v)的位序(顶点集)
           //若顶点在G中没有邻接顶点,则返回false
           int GetNextAdjVex(int u,int v){//就是说第u行的第v+1个顶点
                if(u<0||u>=Vers||v<0||v>=Vers)
                    return false;
                edgeNode<TypeOfEdge> *p=verList[u].head;
                while(p){
                    if(p->data==v)
                        break;
                    p=p->next;
                }
                if(p->next){
                    return p->next->data;
                }
                return -1;
           }
           bool PutVer(int u,TypeOfVer data);//对G中指定顶点赋值
           bool InsertVer(const TypeOfVer data);//往G中添加一个顶点
           int LocateVer(TypeOfVer data);//返回G中指定顶点的位置
           //对于有权图,取两端点为v1和v2的边上的权值。
           //获取成功,返回true;否则,返回false
           bool GetWeight(int u,int v,int &w){//有权图也分为有向和无向
                if(u<0||u>=Vers||v<0||v>=Vers)
                    return false;
                if(GraphKind[0]!='U'){//如果是无向图,哪个顶点作为开头都可以
                    edgeNode<TypeOfEdge> *p=verList[u].head;
                    while(p){
                        if(p->data==v){
                            w=p->weight;
                            return true;
                        }
                        p=p->next;
                    }
                }
                else{
                    edgeNode<TypeOfEdge> *p=verList[u].head;
                    while(p){
                        if(p->data==v){
                            w=p->weight;
                            return true;
                        }
                        p=p->next;
                    }
                    p=verList[v].head;//如果以u开始的起点没找到,再以v开头为起点找
                    while(p){
                        if(p->data==u){
                            w=p->weight;
                            return true;
                        }
                        p=p->next;
                    }
                }
                w=-1;
                return false;
           }
           //求指定顶点的(出)度  (无向图/网:度; 有向图/网:出度 )
           int Get_Degree(int u){
                if(u<0||u>=Vers)
                    return -1;
                int k=0;
                edgeNode<TypeOfEdge> *p=verList[u].head;
                while(p){
                    ++k;
                    p=p->next;
                }
                return k;
           }
           //求有向图指定顶点的入度
           int Get_InDegree(int u){
                if(u<0||u>=Vers||GraphKind[0]=='U')//顶点不存在/非有向图返回-1
                    return -1;
                bool flag=false;
                int k=0;
                for(int i=0;i<Vers;++i){
                    if(i==u)
                        continue;
                    edgeNode<TypeOfEdge> *p=verList[i].head;
                    while(p){
                        if(p->data==u){
                            ++k;
                            flag=true;
                        }
                        p=p->next;
                    }
                }
                return flag ? k : -1;//如果入度不为0,返回k,否则返回-1
           }
           //检查指定2个顶点是否是邻接顶点
           bool ExistEdge(int u,int v){
                if(GraphKind[0]=='U'){//如果是无向图的情况
                    edgeNode<TypeOfEdge> *p=verList[u].head;
                    while(p){//只需要遍历一个就行
                        if(p->data==v)
                            return true;
                        p=p->next;
                    }
                }
                else{
                    edgeNode<TypeOfEdge> *px=verList[u].head;
                    while(px){
                        if(px->data==v)
                            return true;
                        px=px->next;
                    }
                    edgeNode<TypeOfEdge> *py=verList[v].head;
                    while(py){
                        if(py->data==u)
                            return true;
                        py=py->next;
                    }
                }
                return false;
           }
           //输出顶点集
           void PrintVer(){
               for(int i=0;i<Vers;++i){
                    if(i==0)
                        cout<<verList[i].ver;
                    else
                        cout<<" "<<verList[i].ver;
               }
               cout<<endl;
           }
           //输出邻接表
           void PrintAdjList(){
                for(int i=0;i<Vers;++i){
                    cout<<verList[i].ver;
                    if(verList[i].head!=NULL){
                        edgeNode<TypeOfEdge> *p=verList[i].head;//从顶点开始遍历
                        while(p){
                            cout<<"->"<<p->data;
                            /*if(p->weight!=-1)
                                cout<<"("<<p->weight<<")";*/
                            p=p->next;
                        }
                        cout<<"->nullptr"<<endl;
                    }
                    else
                        cout<<"->nullptr"<<endl;
                }
           }
           //无权图插入一条边
           bool Insert_Edge1(int u,int v){//u是起点,v是终点
                if(u<0||u>=Vers||v<0||v>=Vers)//不在范围内时无法插入,返回false
                    return false;
                if(verList[u].head!=NULL){
                    edgeNode<TypeOfEdge> *p=verList[u].head;//这个是判断如果本来就存在这条边的情况
                    while(p){
                        if(p->data==v)
                            return false;
                        p=p->next;
                    }
                }
                edgeNode<TypeOfEdge> *x=new edgeNode<TypeOfEdge>(v);//直接使用构造函数赋值
                //x.data=v;不要这么写
                x->next=verList[u].head;//head本身就是指向的第一个指针,所以head后面不用加->next
                verList[u].head=x;
                ++Edges;//边数加一
                return true;
           }
           //有权图插入一条边
           bool Insert_Edge2(int u,int v,TypeOfEdge w=-1){//先给没赋值的权值赋为-1,如果不等于-1,就输出,否则不输出
                if(u<0||u>=Vers||v<0||v>=Vers)//不在范围内时无法插入,返回false
                    return false;
                if(verList[u].head!=NULL){
                    edgeNode<TypeOfEdge> *p=verList[u].head;//这个是判断如果本来就存在这条边的情况
                    while(p){
                        if(p->data==v)
                            return false;
                        p=p->next;
                    }
                }
                edgeNode<TypeOfEdge> *x=new edgeNode<TypeOfEdge>(v);//直接使用构造函数赋值
                //x.data=v;不要这么写
                x->next=verList[u].head;//head本身就是指向的第一个指针,所以head后面不用加->next
                verList[u].head=x;
                x->weight=w;//给权值赋值
                ++Edges;//边数加一
                return true;
           }
           //往G中删除一个顶点
           bool DeleteVer(int data){//因为题中传入的参数就是顶点的序号,根本不是顶点本身
                if(data<0||data>=Vers)//如果不在范围内返回false
                    return false;
                edgeNode<TypeOfEdge> *pw=verList[data].head;
                int k=0;//用来记录被删除的顶点有多少边与之相连
                if(GraphKind[0]=='U'){
                    while(pw){//如果是无向图只需要记录要被删除的边表中有多少结点就够了
                        ++k;
                        edgeNode<TypeOfEdge> *po=pw;
                        pw=pw->next;
                        delete po;
                    }
                }
                else{//如果是有向图,我们需要遍历整个链表
                    edgeNode<TypeOfEdge> *rp=verList[data].head;
                    while(rp){//这个循环是记录被删除顶点的边表的结点个数
                        ++k;
                        rp=rp->next;
                    }
                    for(int i=0;i<Vers;++i){//这个循环就是记录其他链表中有多少是和被删除顶点有关的边
                        edgeNode<TypeOfEdge> *r=verList[i].head;
                        while(r){
                            if(r->data==data)
                                ++k;
                            r=r->next;
                        }
                    }
                }
                Edges-=k;//减掉边只有的边数
                for(int i=data;i<Vers-1;++i){//将后面的顶点往前移一位
                    verList[i].ver=verList[i+1].ver;
                    verList[i].head=verList[i+1].head;//指针也要往前移一位
                }
                --Vers;
                //PrintAdjList();//输出邻接表用来测试顶点和指针的移动是否正确
                for(int i=0;i<Vers;++i){
                    edgeNode<TypeOfEdge> *px=verList[i].head;
                    edgeNode<TypeOfEdge> *py=verList[i].head;
                    while(px==py){//这个是判断如果与顶点结点相连的就是要删除的结点的情况
                        if(px==py&&px==NULL&&py==NULL)
                            break;
                        else if(px->data==data){
                            px=px->next;
                            verList[i].head=px;
                            edgeNode<TypeOfEdge> *q=py;
                            py=py->next;
                            delete q;
                        }
                        else if(px->data>data){
                            --(px->data);
                            px=px->next;
                        }
                    }
                    while(px){//当px在前,py在后时
                        if((px->data)>data){
                            --(px->data);
                            px=px->next;
                        }
                        else if(px->data==data){//如果相等的话就删除这个结点
                            edgeNode<TypeOfEdge> *q=px;
                            py->next=px->next;
                            px=px->next;
                            delete q;
                            continue;
                        }
                        else if((px->data)<data)
                            px=px->next;
                        py=py->next;
                    }
                }
                return true;
           }
           bool DeleteEdge(int u,int v);//删除边 (外壳:有向(删除1条边), 无向(删除2条边))
           void DFS_Traverse(int u);//DFS遍历
           //深度优先遍历
           void DFS(int u){
                cout<<verList[u].ver;
                visited[u]=true;
                int w;
                for(w=GetFirstAdjVex(u);w>=0;w=GetNextAdjVex(u,w)){
                    if(!visited[w]){
                        cout<<"->";
                        DFS(w);
                    }
                }
           }
           void BFS_Traverse(int u);       //BFS遍历
           //广度优先遍历
           void BFS(int u){
                cout<<verList[u].ver;
                visited[u]=true;
                q.push(u);
                int w;
                while(!q.empty()){
                    u=q.front();
                    q.pop();
                    for(w=GetFirstAdjVex(u);w>=0;w=GetNextAdjVex(u,w)){
                        if(!visited[w]){
                            cout<<"->"<<verList[w].ver;
                            visited[w]=true;
                            q.push(w);
                        }
                    }
                }
                /*cout<<verList[u].ver;
                visited[u]=true;
                q.push(u);
                int m;
                edgeNode<TypeOfEdge> *p=verList[u].head;
                while(!q.empty()){
                    m=q.front();
                    q.pop();
                    p=verList[m].head;
                    while(p){
                        if(!visited[p->data]){
                            cout<<"->"<<verList[p->data].ver;
                            visited[p->data]=true;
                            q.push(p->data);
                        }
                        p=p->next;
                    }
                }*/
           }
           //~adjlist_graph(); //析构函数
    };
    
    template<class TypeOfVer,class TypeOfEdge>
    void shuchu(adjlist_graph<TypeOfVer,TypeOfEdge> &tu,int n){
        //cout<<tu.GetGraphKind()<<endl;
        tu.PrintVer();//输出顶点集
        int* x;//个数是int型
        x=tu.GetVerNum();
        //cout<<*x<<endl;//输出顶点个数
        //tu.PrintVer();//输出顶点集
        TypeOfEdge* we;
        we=tu.GetEdgeNum();
        //cout<<*we<<endl;//输出边数
        tu.PrintAdjList();//输出邻接表
    }
    
    
    int main(){
        string str;//图的类型
        int n,m;//顶点数和边数
        getline(cin,str);
        cin>>n;//输入顶点个数
        for(int i=0;i<n;++i)
            cin>>b[i];//输入顶点集合
        cin>>m;//输入边数
        int **e;
        e=new int* [m];
        for(int i=0;i<m;++i)
            e[i]=new int [2];
        for(int i=0;i<m;++i)
            cin>>e[i][0]>>e[i][1];//输入边集
        /*int c[m];
        for(int i=0;i<m;++i)
            cin>>c[i];//输入权集*/
        adjlist_graph<string,int> tu(str,n,b,m,e);//使用构造函数构造图的类
        int no,to;//指定的要删除的顶点
        cin>>no;
        /*int jk;
        cin>>jk;//输入要插入边的权值*/
        shuchu(tu,n);
        cout<<endl;
        //cout<<tu.GetNextAdjVex(no,to)<<endl;
        //tu.DFS(no);
        tu.BFS(no);
        //shuchu(tu,n);
        return 0;
    }
    
    

    BFS函数如果只写被注释掉的代码也是可以过的。
    没有注释是按书上的思路来的,通过使用队列来记录的方式。

    这里面的深度优先遍历的代码也是可以用的,2中遍历方式的输入是一样的,只是调用的函数不同,如果想用深度优先遍历就把496行给注释掉,495行去掉注释就可以啦。

    更多相关内容
  • c++实现图的邻接表深度优先遍历,广度优先遍历
  • 用Java描述的图,以邻接表存储,包含常用算法
  • 邻接表深度优先遍历

    千次阅读 2020-12-15 16:02:30
    下面是使用邻接表做出的深度优先遍历案例: #include<stdlib.h> #include<stdio.h> #include<malloc.h> #include<string.h> //图的邻接表类型定义 typedef char VertexType[4]; typedef ...

    深度优先遍历和广度优先遍历的参考知识点:https://blog.csdn.net/a2217018103/article/details/90678830
    下面是使用邻接表做出的深度优先遍历案例:

    #include<stdlib.h>
    #include<stdio.h>
    #include<malloc.h>
    #include<string.h>
    //图的邻接表类型定义
    typedef char VertexType[4];
    typedef char InfoPtr;
    typedef int VRType;
    #define MaxSize 50   //最大顶点个数 
    typedef enum {DG,DN,UN,UG} GraphKind; //图的类型:有向图、有向网、无向图和无向网
    typedef struct ArcNode{//边表结点的类型定义 
    	int adjvex;// 弧(边)指向的顶点的位置
    	InfoPtr *info;//与弧(边)相关的信息 
    	struct ArcNode *nextarc;//指示下一个与该顶点相邻接的顶点 
    } ArcNode; 
    typedef struct VNode{ //表头结点的类型定义 
    	VertexType data;//用于存储顶点
    	ArcNode * firstarc;//指示第一个与该顶点邻接的顶点 
    }VNode,AdjList[MaxSize];
    typedef struct{	//图的类型定义 
    	AdjList vertex;
    	int vexnum,arcnum;//图的顶点的数目与弧的数目 
    	GraphKind kind;//图的类型 
    }AdjGraph;
    //函数声明
    int LocateVertex(AdjGraph G,VertexType v);
    void CreateGraph(AdjGraph *G);
    void DisplayGraph(AdjGraph G);
    void DestroyGraph(AdjGraph *G);
    //深度 
    void DFSTraverse(AdjGraph G);
    void DFS(AdjGraph G,int v) ;
    int FirstAdjVertex(AdjGraph G,VertexType v);
    int NextAdjVertex(AdjGraph G,VertexType v,VertexType w);
    
    void BFSTraverse(AdjGraph G); 
    void CreateGraph(AdjGraph *G){
    	int i,j,k;
    	VertexType v1,v2;//定义两个顶点v1和v2
    	ArcNode *p;
    	printf("请输入图的顶点数,边数(逗号分割):");
    	scanf("%d,%d",&(*G).vexnum,&(*G).arcnum) ;
    	printf("请输入%d个顶点的值:\n",G->vexnum);
    	for(i=0;i<G->vexnum;i++){
    		scanf("%s",G->vertex[i].data);
    		G->vertex[i].firstarc=NULL;
    	}
    	printf("请输入弧尾和弧头(以空格作为间隔);\n");
    	for(k=0;k<G->arcnum;k++){
    		scanf("%s%s",v1,v2);
    		i=LocateVertex(*G,v1);
    		j=LocateVertex(*G,v2);
    		//j为入边,i为出边 创建邻接表
    		p=(ArcNode*)malloc(sizeof(ArcNode));
    		p->adjvex=j;//邻接点域 
    		p->info=NULL;//数据域 
    		p->nextarc=G->vertex[i].firstarc;//指针域
    		G->vertex[i].firstarc=p;
    		//i为入边,j为出边 创建邻接表
    		p=(ArcNode*)malloc(sizeof(ArcNode));
    		p->adjvex=i;//邻接点域 
    		p->info=NULL;//数据域 
    		p->nextarc=G->vertex[i].firstarc;//指针域
    		G->vertex[j].firstarc=p;
    	}
    	(*G).kind=UG;
    }
    //查找 
    int LocateVertex(AdjGraph G,VertexType v){
    	int i;
    	for(i=0;i<G.vexnum;++i){
    		if(strcmp(G.vertex[i].data,v)==0){
    			return i; 
    		}
    	}
    	return -1;
    }
    //销毁无向图 
    void DestroyGraph(AdjGraph *G){
    	int i;
    	ArcNode *p,*q;
    	for(i=0;i<(*G).vexnum;++i){//释放图中的边表结点 
    		p=G->vertex[i].firstarc;//p指向边表的第一个结点 
    		if(p!=NULL){//如果边表不为空,则释放边表的结点 
    			q=p->nextarc;
    			free(p);
    			p=q;
    		} 
    	} 
    	(*G).vexnum=0;//将顶点的数目为0 
    	(*G).arcnum=0;//将边的数目为0 
    }
    //打印 
    void DisplayGraph(AdjGraph G){
    	int i;
    	ArcNode *p;
    	printf("%d个顶点:\n",G.vexnum);
    	for(i=0;i<G.vexnum;i++){
    		printf("%s",G.vertex[i].data);
    	}
    	printf("\n%d条边:\n",2*G.arcnum);
    	for(i=0;i<G.vexnum;i++){
    		p=G.vertex[i].firstarc;//将p指向边表的第一个结点
    		while(p){
    			printf("%s->%s  ",G.vertex[i].data,G.vertex[p->adjvex].data);
    			p=p->nextarc;
    		} 
    		printf("\n");
    	}
    }
    int visited[MaxSize]; 
    //深度 
    void DFSTraverse(AdjGraph G){
    	int v;
    	for(v=0;v<G.vexnum;v++){
    		visited[v]=0;		//访问标志数组初始化为未被访问 
    	}
    	printf("\n深度优先遍历序列:\n");
    	for(v=0;v<G.vexnum;v++){
    		if(!visited[v]){	
    			DFS(G,v);	//对未访问的顶点v进行深度优先遍历 
    		}
    	}
    	printf("\n");
    } 
    //打印深度优先遍历的数据 
    void Visit(VertexType v){
    	printf("%s ", v);
    }
    //从顶点v出发递归深度优先遍历 
    void DFS(AdjGraph G,int v) {
    	int w;
    	visited[v]=1;//访问标志设置为已访问 
    	Visit(G.vertex[v].data);
    	for(w=FirstAdjVertex(G,G.vertex[v].data);w>0;w=NextAdjVertex(G,G.vertex[v].data,G.vertex[w].data))
    		if(!visited[w])
    			DFS(G,w);//递归调用DFS对v的尚未访问的序号为w的邻接顶点 
    }
    //返回顶点v的第一个邻接顶点的序号 
    int FirstAdjVertex(AdjGraph G,VertexType v){
    	ArcNode *p;
    	int v1;
    	v1=LocateVertex(G,v);//v1为顶点v在图G中的序号 
    	p=G.vertex[v1].firstarc;
    	if(p)		//如果顶点v的第一个邻接点的存在,返回邻接点的序号,否则返回-1 
    		return p->adjvex;
    	else
    	   return -1;
    }
    //返回v的相对于w的下一个临界顶点的序号 
    int NextAdjVertex(AdjGraph G,VertexType v,VertexType w){
    		ArcNode *p,*next;
    		int v1,w1;
    		v1=LocateVertex(G,v);	//v1为顶点v在图G中的序号 
    		w1=LocateVertex(G,w);   //w1为顶点v在图G中的序号 
    		for(next=G.vertex[v1].firstarc;next;){
    			if(next->adjvex!=w1){
    					
    				}
    		   next=next->nextarc;
    		}
    		p=next;			//p指向顶点v的邻接顶点w的结点 
    		if(!p||p->nextarc){//如果w不存在或w是最后一个邻接点,则返回-1 
    			return -1;
    		}else{
    			return p->nextarc->adjvex;//返回v的相对于w的下一个邻接点的序号 
    		}
    }
    int main(){
    	AdjGraph G;
    	printf("采用邻接表创建无向图G:\n");
    	CreateGraph(&G);
    	printf("输出无向图G:");
    	DisplayGraph(G); 
    	DFSTraverse(G);
    	DestroyGraph(&G);
    	return 1;
    } 
    
    

    效果图:
    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • 天津理工大学实验报告 学院系名称 计算机与通信工程学院 姓名 学号 专业 计算机科学与技术 班级 2009 级 1 班 实验项目 实验四 图的深度优先与广度优先遍历 课程名称 数据结构与算法 课程代码 实验时间 2011 年 5 月...
  • } } static void dfsAl(ALGraph G, int v) {//基于邻接表深度优先遍历 int w; graph.AdjNode p; System.out.println(G.Vex[v].data + "\t"); visited[v] = true; p = G.Vex[v].first; // 依次检查 v 的所有邻接点...

    一 要创建的图

    二 代码

    package graph;
    
    import java.util.Scanner;
    
    public class DFSAL {
        static final int MaxVnum = 100;  // 顶点数最大值
        // 访问标志数组,其初值为"false"
        static Boolean visited[] = new Boolean[MaxVnum];
    
        static {
            for (int i = 0; i < visited.length; i++) {
                visited[i] = false;
            }
        }
    
        static int locatevex(DFSAL.ALGraph G, char x) {
            for (int i = 0; i < G.vexnum; i++) // 查找顶点信息的下标
                if (x == G.Vex[i].data)
                    return i;
            return -1; // 没找到
        }
    
        // 插入一条边
        static void insertedge(DFSAL.ALGraph G, int i, int j) {
            graph.AdjNode s = new graph.AdjNode();
            s.v = j;
            s.next = G.Vex[i].first;
            G.Vex[i].first = s;
        }
    
        // 创建有向图邻接表
        static void CreateALGraph(DFSAL.ALGraph G) {
            int i, j;
            char u, v;
    
            System.out.println("请输入顶点数和边数:");
            Scanner scanner = new Scanner(System.in);
            G.vexnum = scanner.nextInt();
            G.edgenum = scanner.nextInt();
            System.out.println("请输入顶点信息:");
    
            for (i = 0; i < G.vexnum; i++)//输入顶点信息,存入顶点信息数组
                G.Vex[i].data = scanner.next().charAt(0);
            for (i = 0; i < G.vexnum; i++)
                G.Vex[i].first = null;
            System.out.println("请依次输入每条边的两个顶点u,v");
    
            while (G.edgenum-- > 0) {
                u = scanner.next().charAt(0);
                v = scanner.next().charAt(0);
                i = locatevex(G, u); // 查找顶点 u 的存储下标
                j = locatevex(G, v); // 查找顶点 v 的存储下标
                if (i != -1 && j != -1)
                    insertedge(G, i, j);
                else {
                    System.out.println("输入顶点信息错!请重新输入!");
                    G.edgenum++; // 本次输入不算
                }
            }
        }
    
        // 输出邻接表
        static void printg(DFSAL.ALGraph G) {
            System.out.println("----------邻接表如下:----------");
            for (int i = 0; i < G.vexnum; i++) {
                graph.AdjNode t = G.Vex[i].first;
                System.out.print(G.Vex[i].data + ":  ");
                while (t != null) {
                    System.out.print("[" + t.v + "]\t");
                    t = t.next;
                }
                System.out.println();
            }
        }
    
        static void dfsAl(ALGraph G, int v) {//基于邻接表的深度优先遍历
            int w;
            graph.AdjNode p;
            System.out.println(G.Vex[v].data + "\t");
    
            visited[v] = true;
            p = G.Vex[v].first;
            // 依次检查 v 的所有邻接点
            while (p != null) {
                w = p.v; // w 为 v 的邻接点
                if (!visited[w]) // w 未被访问
                    dfsAl(G, w);// 从 w 出发,递归深度优先遍历
                p = p.next;
            }
        }
    
        public static void main(String[] args) {
            DFSAL.ALGraph G = new DFSAL.ALGraph();
            for (int i = 0; i < G.Vex.length; i++) {
                G.Vex[i] = new graph.VexNode();
            }
            CreateALGraph(G); // 创建有向图邻接表
            printg(G); // 输出邻接表
            System.out.println("请输入遍历图的起始点:");
            Scanner scanner = new Scanner(System.in);
            char c = scanner.next().charAt(0);
            int v = locatevex(G, c);//查找顶点u的存储下标
            if (v != -1) {
                System.out.println("广度优先搜索遍历图结果:");
                dfsAl(G, v);
            } else
                System.out.println("输入顶点信息错!请重新输入!");
        }
    
        // 定义邻接点类型
        static class AdjNode {
            int v; // 邻接点下标
            graph.AdjNode next; // 指向下一个邻接点
        }
    
        // 定义顶点类型
        static class VexNode {
            char data; // VexType为顶点的数据类型,根据需要定义
            graph.AdjNode first; // 指向第一个邻接点
        }
    
        // 定义邻接表类型
        static class ALGraph {
            graph.VexNode Vex[] = new graph.VexNode[CreateALGraph.MaxVnum];
            int vexnum; // 顶点数
            int edgenum; // 边数
        }
    }

    三 测试

     

     

    展开全文
  • C++实现,数据结构,图的邻接矩阵表示,深度优先遍历,广度优先遍历,DFS,BFS,为什么要五十个字才能上传啊
  • Java深度优先遍历和广度优先遍历邻接表算法-数据结构和算法-07-图

     自行了解邻接矩阵和邻接表的图的存储,其实一个是顺序存储一个是链表存储,大概的含义。。

    在这里插入图片描述

    解析图

    在这里插入图片描述

    代码

    package com.my.data.structure;
    
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    /**
     * 邻接表深度优先和官渡优先遍历
     */
    public class GraphTest02 {
    
        public List<VertexNode> vertexNodeList = new ArrayList<VertexNode>();
        public int numVertexes = 8;
    
        class EdgeNode {
            int adjVex;     //邻接点城,存储该顶点对应的下标
            int weight;     //存储权值
            EdgeNode next;  //链城,指向下一个邻接点
    
            EdgeNode(int a, int w, EdgeNode n) {
                this.adjVex = a;
                this.weight = w;
                this.next = n;
            }
    
            public void addNext(EdgeNode n) {
                this.next = n;
            }
        }
    
        class VertexNode {
            String v;               //存储顶点信息
            EdgeNode firstEdge;     //边表头指针
    
            VertexNode(String val, EdgeNode edgeNode) {
                v = val;
                firstEdge = edgeNode;
            }
    
            public void addFirstEdge(EdgeNode n) {
                this.firstEdge = n;
            }
        }
    
        public void createAlGraph() {
            //初始化顶点 V1-V8
            for (int i = 0; i < numVertexes; i++) {
                vertexNodeList.add(new VertexNode("V" + (i + 1), null));
            }
    
            /** 邻接矩阵存储
             *    V1 V2 V3 V4 V5 V6 V7 V8
             * V1 0  1  1  0  0  0  0  0
             * V2 1  0  0  1  1  0  0  0
             * V3 1  0  0  0  0  1  1  0
             * V4 0  1  0  0  0  0  0  1
             * V5 0  1  0  0  0  0  0  1
             * V6 0  0  1  0  0  0  1  0
             * V7 0  0  1  0  0  1  0  0
             * V8 0  0  0  1  1  0  0  0
             */
            //边处理
            for (int j = 0; j < numVertexes; j++) {
                vertexNodeList.get(j).addFirstEdge(new EdgeNode(j, 0, null));
                if (j == 0) vertexNodeList.get(j).firstEdge.addNext(new EdgeNode(1, 0, new EdgeNode(2, 0, null)));
                if (j == 1)
                    vertexNodeList.get(j).firstEdge.addNext(new EdgeNode(0, 0, new EdgeNode(3, 0, new EdgeNode(4, 0, null))));
                if (j == 2)
                    vertexNodeList.get(j).firstEdge.addNext(new EdgeNode(0, 0, new EdgeNode(5, 0, new EdgeNode(6, 0, null))));
                if (j == 3) vertexNodeList.get(j).firstEdge.addNext(new EdgeNode(1, 0, new EdgeNode(7, 0, null)));
                if (j == 4) vertexNodeList.get(j).firstEdge.addNext(new EdgeNode(1, 0, new EdgeNode(7, 0, null)));
                if (j == 5) vertexNodeList.get(j).firstEdge.addNext(new EdgeNode(2, 0, new EdgeNode(6, 0, null)));
                if (j == 6) vertexNodeList.get(j).firstEdge.addNext(new EdgeNode(2, 0, new EdgeNode(5, 0, null)));
                if (j == 7) vertexNodeList.get(j).firstEdge.addNext(new EdgeNode(3, 0, new EdgeNode(4, 0, null)));
            }
        }
    
        boolean[] dfsVisit = new boolean[numVertexes];
        boolean[] bfsVisit = new boolean[numVertexes];
    
        /**
         * 邻接表深度优先遍历
         *
         * @param idx
         */
        public void dfs(int idx) {
            System.out.print(vertexNodeList.get(idx).v + " ");
            dfsVisit[idx] = true;
    
            Queue<EdgeNode> queue = new LinkedList<>();
            if(vertexNodeList.get(idx).firstEdge.next!=null)
                queue.add(vertexNodeList.get(idx).firstEdge.next);
            while (!queue.isEmpty()){
                EdgeNode cur = queue.poll();
                if(!dfsVisit[cur.adjVex]) {
                    dfs(cur.adjVex);
                }else {
                    if(cur.next != null) queue.add(cur.next);
                }
            }
        }
    
        /**
         * 邻接表广度优先遍历
         *
         * @param idx
         */
        public void bfs(int idx) {
            if(!bfsVisit[idx]) {
                System.out.print(vertexNodeList.get(idx).v + " ");
                bfsVisit[idx] = true;
            }
    
            Queue<EdgeNode> queue = new LinkedList<>();
            if(vertexNodeList.get(idx).firstEdge.next!=null)
                queue.add(vertexNodeList.get(idx).firstEdge.next);
            while (!queue.isEmpty()){
                EdgeNode cur = queue.poll();
                if(!bfsVisit[cur.adjVex]) {
                    System.out.print(vertexNodeList.get(cur.adjVex).v + " ");
                    bfsVisit[cur.adjVex] = true;
                }
                if(cur.next != null) queue.add(cur.next);
            }
        }
    
        public static void main(String[] args) {
            GraphTest02 graphTest02 = new GraphTest02();
            graphTest02.createAlGraph();
            System.out.println("邻接表深度优先遍历");
            for (int i = 0; i < graphTest02.numVertexes; i++) {
                if(!graphTest02.dfsVisit[i]) graphTest02.dfs(i);
            }
            System.out.println();
            System.out.println("邻接表广度优先遍历");
            for (int i = 0; i < graphTest02.numVertexes; i++) {
                graphTest02.bfs(i);
            }
        }
    }
    
    
    • 结果
    邻接表深度优先遍历
    V1 V2 V4 V8 V5 V3 V6 V7 
    邻接表广度优先遍历
    V1 V2 V3 V4 V5 V6 V7 V8 
    
    展开全文
  • 本程序通过java使用邻接表对图进行深度和广度优先遍历,其中包括图和节点的数据结构实现
  • ![图片说明](https://img-ask.csdn.net/upload/201511/22/1448157843_92689.png) 麻烦各位看看怎么写 我写到 V4---V5就不知道怎么写下去了,
  • 邻接表: 邻接矩阵,也就是使用二维数组用来存放每个顶点与对应边的关系,例如两个顶点存在边,那么就将这个二维数组对应的下标设置为一个非0值。如下图: 无向图情况: 有向图情况: 邻接矩阵是一种不错的图存储...
  • 图的表示:邻接表 邻接表结构原理 在邻接列表实现中,每一个顶点会存储一个从它这里开始的相邻边的列表。比如,如果顶点 B 有一条边到 A、C 和 E,那么 A 的列表中会有 3 条边。 邻接列表只描述指向外部的边。...
  • 程序设计任务: 设计一个程序,实现以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。基本要求:以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的...
  • java深度优先和广度优先的邻接矩阵和邻接表实现(递归)
  • 设计一个算法,实现从顶点v出发的深度优先遍历的非递归过程。 输入 多组数据,每组m+2数据行。第一行有两个数字n和m,代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个整数h和k,代表边依附的两...
  • 深度优先遍历邻接表) void ALGraph::DFT(int v) { int j; EdgeNode *p=NULL: cout<<adjlist[v].vertex; visited[v]=1; p=adjlist[v].firstEdge; while(p!=NULL) { j=p->adjvex; if...
  • } } 深度优先遍历阐述 深度优先遍历的思想如下: 因为图的人一顶点都可能与其他顶点相连接,所以图的遍历算法比树的遍历算法要复杂的多。在访问了某个顶点之后,可能沿着某条路径搜索又回到了出发点。因此,为保证...
  • #include<stdio.h> #include<stdlib.h> #define MaxVertices 100...//建立边 typedef struct node { int adjvex; //指向边结点 struct node *nextarc; //指向下一条边,没有则为NULL int info...
  • 邻接表深度遍历 #include <iostream> using namespace std; const int v = 10; int record[v]; //用来记录节点是否被访问过 char Ding[v]; // 用来记录顶点数据 struct Print { int date; ...
  • 此篇我们将介绍邻接表的思想及两种遍历的代码。首先明确邻接表的存储方式:邻接表中存在两种结构:顶点表节点和边表节点。顶点表节点是存储当前节点,其后的一串边表节点是此点的邻接点。#include&lt;iostream&...
  • 深度优先遍历(Depth-First Search): 用深度优先搜索策略遍历一个图类似于树的前序遍历,对于一个图G=(V,E),首先将图中的每一个顶点都标记为未访问,然后选取一个源点v,将其标为已访问,再递归地用深度优先搜索方法...
  • #include <bits/stdc++.h> #include "Graph.cpp" using namespace std;...void DFS(ALGraph *G, int v) { // 邻接表的DFS算法 ArcNode *p; cout << " " << v; visited[v] = 1; p...
  • 请写出图的邻接矩阵和邻接表,深度和广度遍历结果,最小生成树...详见本人博客:图的遍历:深度优先遍历(DFS) 4.广度遍历结果:1234567 (遍历第一行(结点V1的所有邻接点),遍历完V1的所有邻接点,然后遍历第二行(V.
  • C语言实现邻接表深度优先遍历

    千次阅读 2019-06-17 20:39:35
    1. 对于图的遍历主要有两种遍历方式:深度优先遍历和广度优先遍历,对于图的遍历与树不同的是需要增加一个标记数组来对访问过的节点进行标记,假如访问过了我们就不能够再进行访问了 2. 下面是使用C语言实现深度...
  • 9天没有摸C语言,手很生啊!唉,考试终于结束了,就剩三门了。算法、数据结构太重要了,不要忽视啊!#include &lt;bits/stdc++.h&...typedef struct ArcNode //定义节点 { int adjve...
  • c语言实现的邻接表连通图深度优先遍历,包括图的邻接表建立,图的深度优先遍历
  • 建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历.doc
  • 深度优先遍历与广度优先遍历(邻接表) #include<stdio.h> #include<stdlib.h> #define MAX_VER_NUM 20 //最大顶点个数 #define M 50 //队列长度 //DG有向图 UDG无向图 typedef enum { DG, UDG }...
  • 基于邻接表存储有向图的深度优先遍历 试编写程序,以邻接表位存储结构实现无向图的广度优先遍历操作。 (1)以图的邻接表表示为存储结构建立有向图。 (2)编写有向图的深度优先遍历函数。 (3)以用户指定的顶点为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,152
精华内容 6,860
热门标签
关键字:

邻接表的深度优先遍历