DFS&BFS

题目:

[实验目的]
验证图的深度优先遍历与广度优先遍历算法。
[实验内容及要求]
1.输入一个有向图的顶点数n和边数e,设图中顶点编号为1到n,
1) 依次输入每个边的起点和终点,创建该图的邻接表;
2) 边链表中边结点编号按照从小到大的顺序存储。
2.实现图的深度优先遍历和广度优先遍历,输入顶点序号V,给出1中有向图
自v开始的深度优先遍历序列和广度优先遍历序列。
3.为了增强程序的可读性,程序中要有适当的注释。

 

函数部分:

typedef struct graph_link{
    int code;
    graph_link *next;
}gl,*pgl;

vector<pgl> create_Adjacent(int point){
    vector<pgl>adjacent;
    for(int i=0;i<point;i++)
    {
        pgl p=(pgl)malloc(sizeof(gl));
        p->code=i+1;
        p->next=NULL;
        adjacent.push_back(p);
    }
    string start,end;
    while(1){
        cout<<"please input start(if you want to stop,input *):";
        cin>>start;
        if(start[0]=='*')
            break;
        cout<<"please input end:";
        cin>>end;
        for(int i=0;i<point;i++)
            if(adjacent[i]->code==str2int(start)){
                pgl node=(pgl)malloc(sizeof(gl));
                node->next=NULL;
                node->code=str2int(end);
                pgl p=adjacent[i];
                while(p->next!=NULL)
                    p=p->next;
                p->next=node;
            }
    }
    return adjacent;
}

void output_adjacent(vector<pgl>adjacent){
    for(int i=0;i<adjacent.size();i++)
    {
        pgl end=adjacent[i];
        while(end->next!=NULL){
            cout<<end->code<<" -> ";
            end=end->next;
        }
        cout<<end->code<<endl;
    }
}

void DFS(vector<pgl>adjacent,int point){
    stack<pgl>link;
    pgl p;
    int *visit=new int[point];
    for(int i=0;i<point;i++)
        visit[i]=0;
    int start;
    cout<<"please input the point DFS start:";
    cin>>start;
    for(int i=0;i<point;i++)
        if(adjacent[i]->code==start)
            p=adjacent[i];
    link.push(p);
    while(!link.empty()){
        pgl node=link.top();
        link.pop();
        if(!visit[node->code-1])
        {
            cout<<node->code<<" -> ";
            visit[node->code-1]=1;
            
            for(int i=0;i<point;i++)
                if(adjacent[i]->code==node->code)
                    node=adjacent[i];
            
            node=node->next;
            while(node!=NULL){
                link.push(node);
                node=node->next;
            }
        }
    }
    cout<<"end"<<endl;
}

void BFS(vector<pgl>adjacent,int point){
    queue<pgl>link;
    pgl p;
    int *visit=new int[point];
    for(int i=0;i<point;i++)
        visit[i]=0;
    int start;
    cout<<"please input the point BFS start:";
    cin>>start;
    for(int i=0;i<point;i++)
        if(adjacent[i]->code==start)
            p=adjacent[i];
    link.push(p);
    while(!link.empty()){
        pgl node=link.front();
        link.pop();
        if(!visit[node->code-1])
        {
            cout<<node->code<<" -> ";
            visit[node->code-1]=1;
            for(int i=0;i<point;i++)
                if(adjacent[i]->code==node->code)
                    node=adjacent[i];
            node=node->next;
            while(node!=NULL){
                link.push(node);
                node=node->next;
            }
        }
    }
    cout<<"end"<<endl;
}

 

调用部分:

int point;
cout<<"please input how many points:";
cin>>point;
vector<pgl>adjacent=create_Adjacent(point);
output_adjacent(adjacent);
DFS(adjacent,point);
BFS(adjacent,point);

 

点赞
  1. 浪矢清说道:
    Google Chrome Windows 10

    您这个算法好像没法创建1->2 ,1->3,1->4这样的放射状图(或许只是我太菜了不会用

    1. 浪矢清说道:
      Google Chrome Windows 10

      (手动删评 我太菜了

      1. SAGIRI SAGIRI说道:
        Google Chrome Windows 10

        :ku:

发表评论