目录

【实验目的】

【实验预习】

【实验内容】

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

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

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

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

【实验目的】

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

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

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

【实验预习】

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

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

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

4.图的拓扑排序算法

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

【实验内容】

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

#include
#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;ivexnum;i++){      //邻接矩阵初始化为0 
        for(j=0;jvexnum;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;jvexnum;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;ivexnum;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;jvexnum;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;ivexnum;i++){
        if(visited[i]!=TRUE){
            bfs(i,g);
        }
    }
    printf("\n");
}
void init_visit(){
    int i;
    for(i=0;i
        visited[i]=FALSE;
    }
}
int main(){
    MGraph ga;
    int i,j;
    printf("**********图邻接矩阵存储和图的遍历**********");
    printf("\n1-输入图的基本信息：\n");
    createGraph(&ga);
    printf("\n2-无向图的邻接矩阵：\n");
    for(i=0;i
        for(j=0;j
            printf("%3d",ga.arcs[i][j]);    
        }
        printf("\n");
    }
    printf("\n3-图的遍历：\n");
    init_visit();
    tdfs(&ga);
    init_visit();
    tbfs(&ga);
    return 0;
} 

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

#include
#include
#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;ivexnum;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(mvexnum){
        printf("图中有环！"); 
    }else{
        printf("图中无环！");
    }
}
int main(){
    ALGraph g;
    int i;
    EdgeNode *s;
    printf("\n1-输入图的基本信息：\n");
    createGraph_list(&g);
    printf("\n2-图的邻接表：");
    for(i=0;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
#include
#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;ivexnum;i++){
        lowcost[i]=g->arcs[u][i];
        closest[i]=u;
    }
    lowcost[u]=0;
    printf("\n最小生成树：\n");
    for(i=1;ivexnum;i++){
        min=INFIN;
        for(j=0;jvexnum;j++){
            if(lowcost[j]!=0&&lowcost[j]
                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;jvexnum;j++){
            if(g->arcs[k][j]!=0&&g->arcs[k][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
        flag[i]=0;
    }    
    j=startVex;
    printf("%c",g.vexs[j]);
    flag[j]=1;
    stack[top++]=k;
    while(top>0){
        for(i=0;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
        dist[i]=g.arcs[v][i];
        s[i]=0;
        for(j=0;j
            path[i][j]=0;
        }
        if(dist[i]
            path[i][v]=1;
            path[i][i]=1;
        }
    }
    dist[v]=0;
    s[v]=1;
    for(i=0,u=1;i
        mindis=INFIN;
        for(j=0;j
            if(s[j]==0){
                if(dist[j]
                    u=j;
                    mindis=dist[j];
                }
            }
        }
        s[u]=1;
        for(j=0;j
            if((s[j]==0)&&dist[u]+g.arcs[u][j]
                dist[j]=dist[u]+g.arcs[u][j];
                for(k=0;k
                    path[j][k]=path[u][k];
                }
                path[j][j]=1;
            }
        }
    }
    printf("\n顶点%c->到各顶点的最短路径\n",g.vexs[v]);
    for(i=0;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
#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;ivexnum;i++)
        for(j=i;jvexnum;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     {
        for(j=0;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;ivexnum;i++){
        flag[i]=i;
    }
    for(i=0;iarcnum;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;jvexnum;j++)
                if(flag[j]==temp){
                    flag[j]=factor;
                }
                    
        }
    }
}

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