【数据结构】实验 7 图

news/2025/3/19 10:34:45/

目录

【实验目的】

【实验预习】

【实验内容】

1.编写程序，实现图的邻接矩阵存储及图的深度优先搜索和广度优先搜索

2.编写程序，实现图的邻接表存储和拓扑排序算法 

3.编写程序，实现带权图的存储、图的最小生成树及单源最短路径算法 

4.编写程序，实现最小生成树的Kruskal算法 

【实验目的】

1.掌握图的两种存储表示方法。

2.掌握图的深度优先和广度优先搜索方法。

3.掌握图的典型应用——求最小生成树、拓扑排序和求最短路径方法。

【实验预习】

1.图的邻接矩阵和邻接表存储表示

2.图的深度优先和广度优先搜索

3.图的最小生成树算法——Prim和Kruskal

4.图的拓扑排序算法

5.图的最短路径算法——Dijstra和Floyd

【实验内容】

1.编写程序，实现图的邻接矩阵存储及图的深度优先搜索和广度优先搜索

#include<stdio.h>
#define N 20
#define MAX 100
#define TRUE 1
#define FALSE 0
int visited[N];
typedef struct{           //循环队列的定义 
    int data[N];
    int front,rear;
}SqQueue;
typedef struct{      
    int vexnum,arcnum;     //图的顶点数和边数 
    char vexs[N];          //顶点信息 
    int arcs[N][N];        //邻接矩阵 
}MGraph;
void createGraph(MGraph *g);   //建立一个无向图的邻接矩阵 
void dfs(int i,MGraph *g);     //从第i个顶点出发深度优先搜索 
void tdfs(MGraph *g);          //深度优先搜索整个图 
void bfs(int k,MGraph *g);     //从第k个顶点广度优先搜索 
void tbfs(MGraph *g);          //广度优先搜索整个图 
void init_visit();             //初始化访问标识数组 
void createGraph(MGraph *g){
    int i,j,e=0;
    char v;
    g->vexnum=0;
    g->arcnum=0;
    i=0;
    printf("\n输入顶点序列（以#结束）：\n");
    while((v=getchar())!='#'){
        g->vexs[i]=v;             //读入顶点信息 
        i++;                      //顶点数目 
    }
    g->vexnum=i;
    for(i=0;i<g->vexnum;i++){      //邻接矩阵初始化为0 
        for(j=0;j<g->vexnum;j++){
            g->arcs[i][j]=0;
        }
    }
    printf("\n输入边的信息（顶点序号，顶点序号），以（-1，-1）结束：\n");
    scanf("%d,%d",&i,&j);
    while(i!=-1){
        g->arcs[i][j]=1;          
        g->arcs[j][i]=1;
        e++;
        scanf("%d,%d",&i,&j);
    }
    g->arcnum=e;
}
void dfs(int i,MGraph *g){
    int j;
    printf("%c",g->vexs[i]);
    visited[i]=1;
    for(j=0;j<g->vexnum;j++)
        if((g->arcs[i][j]==1)&&(!visited[j]))
            dfs(j,g);
}
void tdfs(MGraph *g){
    int i;
    printf("\n从顶点%C开始深度优先搜索序列：\n",g->vexs[0]);
    for(i=0;i<g->vexnum;i++)
        if(visited[i]!=TRUE)
            dfs(i,g);
}
void bfs(int k,MGraph *g){
    int i,j;
    SqQueue qlist,*q;
    q=&qlist;
    q->front=0;
    q->rear=0;
    printf("%c",g->vexs[k]);
    visited[k]=1;
    q->data[q->rear]=k;
    q->rear=(q->rear+1)%MAX;
    while(q->rear!=q->front){
        i=q->data[q->front];
        q->front=(q->front+1)%MAX;
        for(j=0;j<g->vexnum;j++){
            if((g->arcs[i][j]==1)&&(!visited[j])){
                printf("%c",g->vexs[j]);
                visited[j]=1;
                q->data[q->rear]=j;
                q->rear=(q->rear+1)%MAX;
            }
        }
    }
}
void tbfs(MGraph *g){
    int i;
    printf("\n从顶点%C开始广度优先搜索序列：\n",g->vexs[0]);
    for(i=0;i<g->vexnum;i++){
        if(visited[i]!=TRUE){
            bfs(i,g);
        }
    }
    printf("\n");
}
void init_visit(){
    int i;
    for(i=0;i<N;i++){
        visited[i]=FALSE;
    }
}
int main(){
    MGraph ga;
    int i,j;
    printf("**********图邻接矩阵存储和图的遍历**********");
    printf("\n1-输入图的基本信息：\n");
    createGraph(&ga);
    printf("\n2-无向图的邻接矩阵：\n");
    for(i=0;i<ga.vexnum;i++){
        for(j=0;j<ga.vexnum;j++){
            printf("%3d",ga.arcs[i][j]);    
        }
        printf("\n");
    }
    printf("\n3-图的遍历：\n");
    init_visit();
    tdfs(&ga);
    init_visit();
    tbfs(&ga);
    return 0;
} 

2.编写程序，实现图的邻接表存储和拓扑排序算法 

#include<stdio.h>
#include<malloc.h>
#define N 20
typedef struct EdgeNode{ 
    int adjvex;            //顶点序号 
    struct EdgeNode *next;   //下一个结点的指针 
}EdgeNode;
typedef struct VNode{
    char data;           //顶点信息 
    int ind;             //顶点入度 
    struct EdgeNode *link;     //指向邻接链表指针 
}VNode;
typedef struct ALgraph{
    int vexnum,arcnum;
    VNode adjlist[N];
}ALGraph;
void createGraph_list(ALGraph *g);
void topSort(ALGraph *g);
void createGraph_list(ALGraph *g){
    int i,j,e;
    char v;
    EdgeNode *s;
    i=0;
    e=0;
    printf("\n输入顶点序列（以#结束）：\n");
    while((v=getchar())!='#'){
        g->adjlist[i].data=v;      //读入顶点信息 
        g->adjlist[i].ind=0;        //入度为0 
        g->adjlist[i].link=NULL;    //指针域设置为空 
        i++;
    }
    g->vexnum=i;
    printf("\n请输入弧的信息（顶点序号，顶点序号），以（-1，-1）结束：\n");
    scanf("%d,%d",&i,&j);
    while(i!=-1){
        s=(struct EdgeNode *)malloc(sizeof(EdgeNode));
        s->adjvex=j;
        s->next=g->adjlist[i].link;
        g->adjlist[i].link=s;     //插入s到邻接表的表头位置 
        g->adjlist[j].ind++;      //顶点j的入度加1 
        e++;
        scanf("%d,%d",&i,&j);
    }
    g->arcnum=e;
}
void topSort(ALGraph *g){
    int i,j,k,top=0,m=0,s[N];     //m为拓扑排序输出的结点数 
    EdgeNode *p;
    for(i=0;i<g->vexnum;i++){
        if(g->adjlist[i].ind==0){
            s[top++]=i;            //入度为0的顶点入栈 
        }
    }
    printf("\n输出拓扑序列：");
    while(top>0){
        j=s[--top];
        printf("%c",g->adjlist[j].data);   //输出入度为0的顶点j 
        m++;
        p=g->adjlist[j].link;        //p指向刚输出的顶点j的邻接表 
        while(p!=NULL){              //修改以j起始有弧的顶点的入度 
            k=p->adjvex;
            g->adjlist[k].ind--;     //与起始点j有弧的顶点的入度减1 
            if(g->adjlist[k].ind==0){
                s[top++]=k;          //入度为0的顶点入栈 
            }
            p=p->next;
        }
    } 
    printf("\n共输出%d个顶点\n",m);
    if(m<g->vexnum){
        printf("图中有环！"); 
    }else{
        printf("图中无环！");
    }
}
int main(){
    ALGraph g;
    int i;
    EdgeNode *s;
    printf("\n1-输入图的基本信息：\n");
    createGraph_list(&g);
    printf("\n2-图的邻接表：");
    for(i=0;i<g.vexnum;i++){
        printf("\n%c：%d",g.adjlist[i].data,g.adjlist[i].ind);
        s=g.adjlist[i].link;
        while(s!=NULL){
            printf("->%d",s->adjvex);
            s=s->next;
        }
    }
    printf("\n");
    printf("\n3-根据图的邻接表实现拓扑排序：\n");
    topSort(&g);
    return 0;
} 

3.编写程序，实现带权图的存储、图的最小生成树及单源最短路径算法 

#include<stdio.h>
#include<malloc.h>
#define N 20
#define INF 32766
#define INFIN 32767
#define TRUE 1
typedef struct{
    int vexnum,arcnum;
    char vexs[N];
    int arcs[N][N];
}MGraph;
void printPath(MGraph g,int startVex,int EndVex,int path[][N]);
void createMGraph_w(MGraph *g,int flag);
void prim(MGraph *g,int u);
void dijkstra(MGraph g,int v);
void createGraph_w(MGraph *g,int flag){
    int i,j,w;
    char v;
    g->vexnum=0;
    g->arcnum=0;
    i=0;
    printf("\n输入顶点序列（以#结束）：\n"); 
    while((v=getchar())!='#'){
        g->vexs[i]=v;
        i++;
    } 
    g->vexnum=i;
    for(i=0;i<6;i++){
        for(j=0;j<6;j++){
            g->arcs[i][j]=INF;
        }
    }
    printf("\n输入边的信息：（顶点，顶点，权值），以（-1，-1，-1）结束\n");
    scanf("%d,%d,%d",&i,&j,&w);
    while(i!=-1){
        g->arcs[i][j]=w;
        if(flag==1)
        g->arcs[j][i]=w;
        scanf("%d,%d,%d",&i,&j,&w);
    }
}
void prim(MGraph *g,int u){
    int lowcost[N],closest[N],i,j,k,min;
    for(i=0;i<g->vexnum;i++){
        lowcost[i]=g->arcs[u][i];
        closest[i]=u;
    }
    lowcost[u]=0;
    printf("\n最小生成树：\n");
    for(i=1;i<g->vexnum;i++){
        min=INFIN;
        for(j=0;j<g->vexnum;j++){
            if(lowcost[j]!=0&&lowcost[j]<min){
                min=lowcost[j];
                k=j;
            }
        }
        printf("(%c,%c)--%d\n",g->vexs[closest[k]],g->vexs[k],lowcost[k]);
        lowcost[k]=0;
        for(j=0;j<g->vexnum;j++){
            if(g->arcs[k][j]!=0&&g->arcs[k][j]<lowcost[j]){
                lowcost[j]=g->arcs[k][j];
                closest[j]=k;
            }
        }
    }
}
void printPath(MGraph g,int startVex,int EndVex,int path[][N]){
    int stack[N],top=0;
    int i,j,k;
    int flag[N];
    k=EndVex;
    for(i=0;i<g.vexnum;i++){
        flag[i]=0;
    }    
    j=startVex;
    printf("%c",g.vexs[j]);
    flag[j]=1;
    stack[top++]=k;
    while(top>0){
        for(i=0;i<g.vexnum;i++){
            if(path[k][i]==1&&flag[i]==0){
                if(g.arcs[j][i]!=INF){
                    printf("->%c(%d)",g.vexs[i],g.arcs[j][i]);
                    flag[i]=1;
                    j=i;
                    k=stack[--top];
                    break;
                }
                else{
                    if(i!=k) stack[top++]=i;
                }
            }
        }
    }
    if(flag[k]==0) printf("->%c(%d)",g.vexs[k],g.arcs[j][k]);
}
void dijkstra(MGraph g,int v){
    int s[N],path[N][N],dist[N];
    int mindis,i,j,u,k;
    for(i=0;i<g.vexnum;i++){
        dist[i]=g.arcs[v][i];
        s[i]=0;
        for(j=0;j<g.vexnum;j++){
            path[i][j]=0;
        }
        if(dist[i]<INF){
            path[i][v]=1;
            path[i][i]=1;
        }
    }
    dist[v]=0;
    s[v]=1;
    for(i=0,u=1;i<g.vexnum;i++){
        mindis=INFIN;
        for(j=0;j<g.vexnum;j++){
            if(s[j]==0){
                if(dist[j]<mindis){
                    u=j;
                    mindis=dist[j];
                }
            }
        }
        s[u]=1;
        for(j=0;j<g.vexnum;j++){
            if((s[j]==0)&&dist[u]+g.arcs[u][j]<dist[j]){
                dist[j]=dist[u]+g.arcs[u][j];
                for(k=0;k<g.vexnum;k++){
                    path[j][k]=path[u][k];
                }
                path[j][j]=1;
            }
        }
    }
    printf("\n顶点%c->到各顶点的最短路径\n",g.vexs[v]);
    for(i=0;i<g.vexnum;i++){
        if(i==v) continue;
        printf("\n顶点%c->顶点%c:",g.vexs[v],g.vexs[i]);
        if(dist[i]==INF||dist[i]==0){
            printf("无路径");
        }else{
            printf("%d",dist[i]);
            printf("经过顶点:");
            printPath(g,v,i,path);
        }
    }
}
int main(){
    int select;
    MGraph ga;
    do{
        printf("\n*************MENU*************\n");
        printf("1. 图的最小生成树-Prim算法\n");
        printf("2. 图的单源最短路径-Dijstra算法\n");
        printf("0. EXIT");
        printf("\n*************MENU*************\n");
        printf("\ninput choice:");
        scanf("%d",&select);
        getchar();
        switch(select){
            case 1:
                printf("\n1-图的最小生成树-Prim算法\n");
                printf("\n输入带权图的基本信息：\n");
                createGraph_w(&ga,1);
                prim(&ga,0);
                break;
            case 2:
                printf("\n2-图的单源最短路径-Dijstra算法\n");
                printf("\n输入带权图的基本信息：\n");
                createGraph_w(&ga,0);
                dijkstra(ga,0);
                break;
            default:
                break; 
        }
    }while(select);
    return 0;
}

4.编写程序，实现最小生成树的Kruskal算法 

#include<stdio.h>
#define N 20
#define TRUE 1
#define INF 32766         
#define INFIN 32767       

typedef struct{
    int vexnum,arcnum;
    char vexs[N];
    int arcs[N][N];
}graph;

typedef struct{
    int begin ,end; 
    int weight;  
}Edge;

Edge edges[N];
void SortEdges(graph *g){
    int i,j,k,L=0;
    for(i=0;i<g->vexnum;i++)
        for(j=i;j<g->vexnum;j++)
        if(g->arcs[i][j]!=INF){
            k=L;
            while(k>0&&edges[k-1].weight>g->arcs[i][j]){
                edges[k]=edges[k-1];
                k--;
             }
            edges[k].weight=g->arcs[i][j];
            edges[k].begin=i;
            edges[k].end=j;
            L++;
        }
}

int flag[N];

void CreateMGraph(graph *g)
{
    int i,j,k=0,v=0,a=0;
    char rec;
    scanf("%c",&rec);
    i=0;
    while(rec!='#'){
        v++;
        g->vexs[i]=rec;
        scanf("%c",&rec);
        i++;
    }
    for(i=0;i<v;i++)
    {
        for(j=0;j<v;j++)
            g->arcs[i][j]=INFIN;
    }
    i=0;
    scanf("%d,%d,%d",&i,&j,&k);
    while(i!=-1)
    {
        g->arcs[i][j]=k;
        g->arcs[j][i]=k;
        a++;
        scanf("%d,%d,%d",&i,&j,&k);
    }
    g->vexnum=v;
    g->arcnum=a-1;
}
void Kruskal(graph *g)
{
    int i,j,factor,temp;
    for(i=0;i<g->vexnum;i++){
        flag[i]=i;
    }
    for(i=0;i<g->arcnum;i++)
    {
        if(flag[edges[i].begin]!=flag[edges[i].end])
        {
            printf("\n(%c,%c)--%d",g->vexs[edges[i].begin],g->vexs[edges[i].end],edges[i].weight);
            factor=flag[edges[i].begin];
            temp=flag[edges[i].end];
            for(j=0;j<g->vexnum;j++)
                if(flag[j]==temp){
                    flag[j]=factor;
                }
                    
        }
    }
}

int main()
{
    graph ga;
    CreateMGraph(&ga);
    SortEdges(&ga);
    Kruskal(&ga);
} 


http://www.ppmy.cn/news/73.html

相关文章

C语言习题练习11--指针

C语言习题练习11--指针

1.代码结果 #include <stdio.h> int main() {int arr[] {1,2,3,4,5};short *p (short*)arr;int i 0;for(i0; i<4; i){*(pi) 0;}for(i0; i<5; i){printf("%d ", arr[i]);}return 0; } 正常&#xff1a;0001--00 02--00 03--00 04--00 05 数组内部是倒…
阅读更多...
iText7高级教程之html2pdf——6.在pdfHTML中使用字体

iText7高级教程之html2pdf——6.在pdfHTML中使用字体

到目前为止&#xff0c;我们还没有花太多的精力来研究将HTML转换为PDF时使用的字体。我们知道Helvetica是iText在没有指定字体时使用的默认字体&#xff08;第2章&#xff09;&#xff0c;我们知道如果需要嵌入字体&#xff0c;pdfHTML会附带一些内置字体&#xff08;第4章&…
阅读更多...
web概述20

web概述20

MVC模式 MVC全名是Model View Controller是模型视图控制器的缩写&#xff0c;是一种软件设计典范&#xff0c;是一种架构型的模式&#xff0c;本身不引入新功能&#xff0c;只是帮助将开发的结构组织的更加合理。 它使用一种业务逻辑、数据、界面显示分离的方法&#xff0c;将…
阅读更多...
掌握这十个Linux命令，秒变Linux老手

掌握这十个Linux命令，秒变Linux老手

前言 在Linux下&#xff0c;完成一个事情往往有N种方法。Linux的一大哲学就是"一个工具只做一样事情"&#xff0c;通过不同工具的组合使用&#xff0c;完成不同的需求。熟练掌握好常用命令&#xff0c;有时事半功倍&#xff0c;起到出其不意的效果。不仅大大提升你的…
阅读更多...
Go定时器使用

Go定时器使用

概述 在软件开发场景&#xff0c;难免会用到定时器&#xff0c; 在go语言中&#xff0c;我们一般使用标准库time就可以实现很多定时器功能 定时器种类 单次定时器: 创建后只触发一次周期定时器: 每隔一段指定的时间触发一次 单次定时器 创建方法 方法一&#xff1a;使用 …
阅读更多...
zabbix监控Nginx

zabbix监控Nginx

目录 一、环境准备 二、部署Nginx被监控端 三、自定义Nginx监控key 四、给目标主机创建监控项 一、环境准备 搭建zabbix基础环境 zabbix基础环境部署参照&#xff1a;zabbix基础环境部署_桂安俊kylinOS的博客-CSDN博客 以下实验部署均基于上述环境 二、部署Nginx被监控端…
阅读更多...
【Canvas】js用canvas绘制一个钟表时钟动画效果

【Canvas】js用canvas绘制一个钟表时钟动画效果

学习JavaScript的看过来&#xff0c;有没有兴趣用Canvas画图呢&#xff0c;可以画很多有趣的事物&#xff0c;自由发挥想象&#xff0c;收获多多哦&#xff0c;旋转角度绘图这个重点掌握到了吗&#xff0c;这里有一个例子&#xff0c;如何用canvas画钟表时钟动图效果&#xff0…
阅读更多...
防火墙原理讲解——练习实验

防火墙原理讲解——练习实验

♥️作者&#xff1a;小刘在C站 ♥️每天分享云计算网络运维课堂笔记&#xff0c;一起努力&#xff0c;共赴美好人生&#xff01; ♥️夕阳下&#xff0c;是最美的&#xff0c;绽放。 目录 一防火墙基础 二防火墙配置 三防火墙的高级应用 四.实验图纸 五.实验命令 一防火…
阅读更多...
最新文章

Copyright @ 2022~2023