头歌 数据结构 实验六——图的存储及操作（合集）

前言:

这些题的提示给的都非常充分了，基本上按照要求来都可以做出来，大家加油 p( ^ O ^ )q 加油！

邻接矩阵

第1关：有向图邻接矩阵的构建

status CreateDG(MGraph &m) //ÓÐÏòͼ´´½¨ 
{
    /********begin********/
    int incinfo,i,j,k;
    VertexType v1,v2;
    cin>>m.vexnum>>m.arcnum>>incinfo;
    for(int i=0;i<m.vexnum;i++){
        cin>>m.vex[i];
    }
    for(i=0;i<m.vexnum;i++){
        for(j=0;i<m.vexnum;i++){
            m.arcs[i][j].adj=0;
            m.arcs[i][j].info=NULL;
        }
    }
    for(k=0;k<m.arcnum;k++){
        cin>>v1>>v2;
        i=LocateVex(m,v1);
        j=LocateVex(m,v2);
        m.arcs[i][j].adj=1;
        if(incinfo){
            cin>>m.arcs[i][j].info;
        }
    }
    /*********end*********/
    return OK;
}

第二关：邻接矩阵存储的有向图的深度优先遍历以及广度优先遍历

void DFS(MGraph &m,int v)
{//µÝ¹éÉîËÑ 
    /*********begin***********/
    stack<int> s;
    s.push(v);
    visited[v]=1;
    cout<<m.vex[v];
    while(!s.empty()){
        int now,flag=0;
        now=s.top();
        for(int i=0;i<m.vexnum;i++){
            if(m.arcs[now][i].adj==1&&!visited[i]){
                s.push(i);
                visited[i]=1;
                cout<<m.vex[i];
                flag=1;
                break;
            }
        }
        if(flag==0){
            s.pop();
        }
    }
    /**********end************/
}
void BFSTraverse(MGraph &m)
{
    for(int i=0;i<m.vexnum;i++) visited[i]=0;
    queue<int> q;
    /************begin*****************/
    int t=0;
    q.push(t);
    visited[t]=1;
    cout<<m.vex[t];
    while(!q.empty()){
        int now;
        now=q.front();
        for(int i=0;i<m.vexnum;i++){
            if(m.arcs[now][i].adj==1&&!visited[i]){
                q.push(i);
                visited[i]=1;
                cout<<m.vex[i];
            }
        }
        q.pop();
    }
    /*************end******************/
}

第3关：邻接矩阵存储的有向图的拓扑排序

status TopologicalSort(MGraph &m)
{
    int InDegree[m.vexnum]={0};
    int i,count,ans,temp,j;
    stack<int> s;
    for(i=0;i<m.vexnum;i++)
    {
        count=0;
        for(j=0;j<m.vexnum;j++)
        {
            if(m.arcs[i][j].adj) InDegree[j]++;
        }
    }
    /***********begin**********/
    for(int i=0;i<m.vexnum;i++){
        if(InDegree[i]==0){
            s.push(i);
        }
    }
    while(!s.empty()){
        int now=s.top();
        s.pop();
        cout<<m.vex[now];
        for(int i=0;i<m.vexnum;i++){
            if(m.arcs[now][i].adj==1){
                InDegree[i]--;
                if(InDegree[i]==0){
                    s.push(i);
                }
            }
        }
    }
    /***********end************/ 
}

邻接表

第1关：实现图的邻接表存储

tips：

这题老师给的print函数有问题，你们需要自己改，如果不改输出的格式肯定就不对，需要把空格放在数字的前面

void Creat_ALG(ALGraph *m){
    VertexType a,b;//Æðµãa£¬ÖÕµãb 
    for(int i=0;i<m->arcnum;i++){
        //printf("ÇëÊäÈëÆðµãºÍÖյ㣺\n");
        scanf("%d%d",&a,&b);
        /************begin************/ 
        int x,y;
        for(int j=0;j<m->vexnum;j++){
            if(a==m->vertices[j].data){
                x=j;
            }
            if(b==m->vertices[j].data){
                y=j;
            }
        }
        ArcNode *p=new ArcNode;
        p->num=y;
        ArcNode *t=m->vertices[x].firstarc;
        if(!t){
            p->next=t;
            m->vertices[x].firstarc=p;
        }else{
            while(t->next!=NULL){
                t=t->next;
            }
            p->next=t->next;
            t->next=p;
        }
        /************end************/ 
    } 
}

第2关：基于邻接表存储实现图的两种遍历算法

tips：

这题老师给的print函数同样有问题，你们需要自己改

void dfs(stack<int> &s,ALGraph m,int visit[]){//Ó÷ûºÅ&ʵÏÖË«Ïò´«µÝ 
    //Éî¶ÈÓÅÏȱéÀú 
    /*************begin*************/
    while(!s.empty()){
        int now,temp=0;
        now=s.top();
        ArcNode *p=m.vertices[now].firstarc;
        while(p!=NULL){
            if(visit[p->num]==0){
                s.push(p->num);
                visit[p->num]=1;
                cout<<" "<<m.vertices[p->num].data;
                temp=1;
                break;
            }
            p=p->next;
        }
        if(temp==0){
            s.pop();
        }
    } 
    /*************end*************/
}
void bfs(queue<int> &q,ALGraph m,int visit[]){
    //¹ã¶ÈÓÅÏȱéÀú
    /*************begin*************/
    while(!q.empty()){
        int now,temp;
        now=q.front();
        ArcNode *p=m.vertices[now].firstarc;
        while(p!=NULL){
            if(visit[p->num]==0){
                q.push(p->num);
                visit[p->num]=1;
                cout<<" "<<m.vertices[p->num].data;
            }
            p=p->next;
        }
        q.pop();
    }
    /*************end*************/
}

第3关：实现DAG图的拓扑排序

void FindInDegree(ALGraph G,int a[]){//ͳ¼Æ¸÷¸ö¶¥µãµÄÈë¶È 

    /*************begin*************/
    for(int i=0;i<G.vexnum;i++){
        ArcNode *p=G.vertices[i].firstarc;
        while(p!=NULL){
            a[p->num]++;
            p=p->next;
        }
    }
    /*************end*************/
}
void TopologicalSort(ALGraph G){//ÍØÆËÅÅÐòº¯Êý
 
    int indegree[G.vexnum+1];//indegreeÊý×éÀ´¼Ç¼¶¥µãµÄÈë¶È 
    
    memset(indegree,0,sizeof(indegree));//Êý×éÔªËسõʼ»¯Îª0 
    
    FindInDegree(G,indegree);//µ÷ÓÃͳ¼ÆÈë¶Èº¯Êý 
    
    /*************begin*************/
    stack<int> s;
    for(int i=0;i<G.vexnum;i++){
        if(indegree[i]==0){
            s.push(i);
        }
    }
    while(!s.empty()){
        int now=s.top();
        s.pop();
        cout<<G.vertices[now].data<<" ";
        ArcNode *p=G.vertices[now].firstarc;
        while(p!=NULL){
            indegree[p->num]--;
            if(indegree[p->num]==0){
                s.push(p->num);
            }
            p=p->next;
        }
    }
    /*************end*************/
}