设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › C\C++交流 › 数据结构：图遍历的演示
返回列表 发新帖
查看: 5014|回复: 4

[技术交流] 数据结构：图遍历的演示

[复制链接]
SonOmiga
发表于 2015-12-13 12:09:51 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
本帖最后由 SonOmiga 于 2015-12-16 19:11 编辑

这是犹豫老师布置的课题作业,
分为两个文件一个为c.cpp 一个为头文件类型  graph.h
c文件如下:
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<windows.h>
#include"graph.h"
void main()
{
        int i,j,c,n,e,t,x;
        MGraph g;                                //定义图g
        ALGraph *G;                                //定义邻接表G
        g.n=21;
        g.e=21;
        for(i=0;i<g.n;i++)
                for(j=0;j<g.n;j++)
                        g.edges[i][j]=A[i][j];                                //将A[][]邻接矩阵转换成图g的边信息
        printf("\n");
        printf("\n");
        printf("                               图遍历的演示:\n");
        printf("                          正在从文件中读取 ");
        for(i=0;i<3;i++)
        {
                ::Sleep(600);
                printf(".");
        }
        printf("\n");
        printf("                                请稍候!\n");
                for(i=0;i<3;i++)
        {
                ::Sleep(600);
        }
        printf("                          从文件读取信息完毕!\n");
        printf("\n");
        MatToList(g,G);                                          //将邻接矩阵转换成邻接表
        {
        FILE *fp;
        char str[200];
        if((fp=fopen("D:\\C.txt","rt"))==NULL)   //打开C文件(C中存放图的信息)
        {
                printf("\n Cannot open file strike any key exit!");
        }
        while(fgets(str,200,fp)!=NULL)                   //从文件中读取字符串
        {
                printf("%s",str);
                printf("\n");}

        }
        printf("\n");
        printf("\n");        printf("你想通过哪个顶点遍历DFS算法?");
                               scanf("%d",&t);
        printf("从顶点%d开始实现DFS算法:\n",t);
        DFS(G,t);
        printf("\n");
        system("pause");
        printf("\n你想通过哪个顶点遍历BFS算法?");
        scanf("%2d",&t);
        printf("从顶点%d开始实现BFS算法:\n",t);
        BFS(G,t);
        system("pause");
for(i=0;i<G->n;i++)                                  
                visited[i]=0;

        printf("\n你想通过哪个顶点输出深度优先生成树?");
        scanf("%2d",&t);
        DFS1(G,t);
        printf("\n");
        system("pause");
        printf("\n你想通过哪个顶点输出广度优先生成树?");
        scanf("%2d",&t);
        BFS1(G,t);
        printf("\n");
           for(i=0;i<G->n;i++)
                visited[i]=0;
system("pause");
printf("你想通过哪个顶点凹入表打印树?");
                        scanf("%d",&t);
        printf("从顶点%d开始实现深度优先生凹入表打印树:\n",t);
        DFSTest(G,t);
printf("\n");
        system("pause");
printf("\n你想通过哪个顶点凹入表打印树?");
                        scanf("%2d",&t);
        printf("从顶点%d开始实现广度优先生凹入表打印树:\n",t);
        BFSTest(G,t);
        system("pause");
        
}
graph.h代码如下:
#include<stdio.h>
#include<malloc.h>
#define MAXV 21
int visited[MAXV];                                                        //定义全局数组 visited
int A[MAXV][MAXV]=                                                // 输入A[ ][ ]的邻接矩阵

{                                                                                        
{0,1,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0},
        {1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0}
};



结构体类型:

typedef struct
{
        int no;
}Vertex;                                                                        //顶点类型
typedef struct
{
        int edges[MAXV][MAXV];                                //图中的边
        int n,e;                                                                //图中顶点数n 和边数E
        Vertex vexs[MAXV];
}MGraph;                                                                //完整的图类型
typedef struct Anode
{
        int adjvex;
        struct Anode *nextarc;
}ArcNode;                                                                //边节点类型
typedef struct Vnode
{
        Vertex Vdata;                                                //顶点的数据信息
        ArcNode *firstarc;                                        //指向第一条边对应的边节点
}VNode;
typedef VNode AdjList[MAXV];                        //定义一个邻接表类型的数组
typedef struct
{
        AdjList adjlist;                                                //邻接表
        int n,e;                                                                //图中顶点数n 和边数E
}ALGraph;                                                                //完整的图邻接表类型



函数类型:
void MatToList(MGraph g,ALGraph *&G)                 // 邻接矩阵转换邻接表
{
        int i,j;
        ArcNode *p;
        G=(ALGraph *)malloc(sizeof(ALGraph));
        for(i=0;i<g.n;i++)
                G->adjlist[i].firstarc=NULL;
        for(i=0;i<g.n;i++)
                for(j=g.n-1;j>=0;j--)        
                        if(g.edges[i][j]!=0)
                        {
                                p=(ArcNode *)malloc(sizeof (ArcNode));
                                p->adjvex =j;
                                p->nextarc=G->adjlist[i].firstarc ;
                                G->adjlist[i].firstarc =p;
                        }
        G->n=g.n;G->e=g.e;
}



void DispAdj(ALGraph *G)                                        //输出邻接表
{
        int i;
        ArcNode *p;
        for(i=0;i<G->n;i++)
        {
                p=G->adjlist[i].firstarc ;
                printf("%3d->",i);
                while(p!=NULL)
                {
                        printf("%3d",p->adjvex);
                        p=p->nextarc ;
                }
                printf("\n");
        }
}

void DFS2(ALGraph *G,int v)                                                        //非递归遍历BFS算法
{
        ArcNode *p;
        ArcNode *St[MAXV];
        int top=-1,w,i;
        for(i=0;i<G->n;i++)
                visited[i]=0;
        printf("%3d",v);
        visited[v]=1;
        top++;
        St[top]=G->adjlist[v].firstarc;
        while(top>-1)
        {
                p=St[top];
                top--;
                while(p!=NULL)
                {
                         w=p->adjvex;
                         if(visited[w]==0)
                         {
                                 printf("%3d",w);
                                 visited[w]=1;
                                 top++;
                                 St[top]=G->adjlist[w].firstarc;
                                 
                         }
                         p=p->nextarc ;
                         
                }
        }
        printf("\n");
}






void BFS(ALGraph *G,int v)                                        //遍历BFS算法
{
        ArcNode *p;
        int queue[MAXV],front=0,rear=0;
        int w,i;
        for(i=0;i<G->n;i++)
                visited[i]=0;
        printf("%2d",v);
        visited[v]=1;
        rear=(rear+1)%MAXV;
        queue[rear]=v;
        while(front!=rear)
        {
                front=(front+1)%MAXV;
                w=queue[front];
                p=G->adjlist[w].firstarc;
                while(p!=NULL)
                {
                        if(visited[p->adjvex]==0)
                        {
                                printf("%2d ",p->adjvex);
                                visited[p->adjvex]=1;
                                rear=(rear+1)%MAXV;
                                queue[rear]=p->adjvex;
                        }
                        p=p->nextarc;
                }
        }
        printf("\n");
}
void BFS1(ALGraph *G,int v)                                         //深度优先生成树
{
        ArcNode *p;
        int queue[MAXV],front=0,rear=0;
        int w,i;
        for(i=0;i<G->n;i++)
                visited[i]=0;
        visited[v]=1;
        rear=(rear+1)%MAXV;
        queue[rear]=v;
        while(front!=rear)
        {
                front=(front+1)%MAXV;
                w=queue[front];
                p=G->adjlist[w].firstarc;
                while(p!=NULL)
                {
                        if(visited[p->adjvex]==0)
                        {
                                printf("<%d,%d>",w,p->adjvex);
                                visited[p->adjvex]=1;
                                rear=(rear+1)%MAXV;
                                queue[rear]=p->adjvex;
                        }
                        p=p->nextarc;
                }
        }
        printf("\n");
}
void DFS1(ALGraph *G,int v)                                         //广度优先生成树
{
        ArcNode *p;        
        visited[v]=1;
        p=G->adjlist[v].firstarc;
        while(p!=NULL)
        {
                if(visited[p->adjvex]==0)
                {
                        printf("<%d,%d>",v,p->adjvex);
                        DFS1(G,p->adjvex);
                }
                p=p->nextarc ;
        }
}




int deep = 0;                                                                          //定义深度为0
void DFSTest(ALGraph *G, int v)                                //凹入法输出广度优先生成树
{
    ArcNode *p;
    visited[v] = 1;
    int index;
    deep++;
    for ( index = 0; index < deep; ++index){
        printf("***");
    }
    printf("%3d", v);
    printf("\n");
    p = G->adjlist[v].firstarc;
    while (p != NULL)
    {
        if (visited[p->adjvex] == 0)
            DFSTest(G, p->adjvex);
        p = p->nextarc;
    }
    deep--;
}

void BFSTest(ALGraph *G, int v)                                //凹入法输出深度优先生成树
{
    int deepth=0;
    int deepthTemp = 0;
    ArcNode *p;
    int queue[MAXV], front = 0, rear = 0;
    int w, i;
    for (i = 0; i<G->n; i++)
        visited[i] = 0;
    printf("***%3d", v);
    printf("\n");
    visited[v] = 1;
    rear = (rear + 1) % MAXV;
    queue[rear] = v;
    deepthTemp = 0;
    while (front != rear)
    {
        front = (front + 1) % MAXV;
        if (front > deepthTemp){
            deepthTemp = rear;
            deepth++;
        }
        w = queue[front];
        p = G->adjlist[w].firstarc;
        while (p != NULL)
        {
            if (visited[p->adjvex] == 0)
            {
                for (int index = 0; index < deepth; ++index){
                    printf("******");
                }
                printf("%2d ", p->adjvex);
                printf("\n");
                visited[p->adjvex] = 1;
                rear = (rear + 1) % MAXV;
                queue[rear] = p->adjvex;
            }
            p = p->nextarc;
        }
    }
    printf("\n");
}
以上是使用邻接矩阵转换成邻接表, 另外有手动输入的邻接表函数如下:
结构体类型:
#include<stdio.h>
#include<malloc.h>
#define MAXV 6
int visited[MAXV];
typedef struct
{
        int no;
}Vertex;                                                                //顶点信息
typedef struct Anode
{
        int adjvex;
        struct Anode *nextarc;
        int info;

}ArcNode;                                                        //边节点信息
typedef struct Vnode
{
        int Vdata;                                                         //顶点的数据信息
        ArcNode *firstarc;                                          //指向第一条边对应的边节点

}VNode;

typedef VNode AdjList[MAXV];                        //定义一个邻接表类型的数组
typedef struct
{
        int n,e;
}Graph;                                                                //图信息
typedef struct
{
        AdjList adjlist;                                                //邻接表
        int n,e;                                                        //图中顶点数n 和边数E
}ALGraph;                                                        //完整的图邻接表类型
        



函数类型:


void Creatgraph (VNode  adjlist[],Graph &graph )                        //手动生成邻接矩阵
{
        int i,j,n,e,begin,end;
        ArcNode *p;    // 定义边节点p
        printf("请输入顶点数n=");
        scanf("%d",&n);
        printf("请输入边数e=");
        scanf("%d",&e);
        graph.n=n;
        graph.e=e;
        for(i=0;i<n;i++)
        {
                adjlist[i].Vdata=i;
                adjlist[i].firstarc=NULL;
        }
        for(j=0;j<2*e;j++)
        {
                printf("\n请输入第%d条边的起始点的序号\n",j);
                printf("        起点编号:");
                scanf("%d",&begin);
                printf("        终点编号:");
                scanf("%d",&end);
                p=(ArcNode*)malloc(sizeof(ArcNode*));
                p->adjvex=end;
                p->nextarc=NULL;
                p->nextarc=adjlist[begin].firstarc;
                adjlist[begin].firstarc=p;
                
        }
}











void DispAdj(VNode adjlist[],Graph &graph)                                        //输出邻接表
{
        int i;
        ArcNode *p;
        for(i=0;i<graph.n;i++)
        {
                p=adjlist[i].firstarc ;
                printf("   %d",adjlist[i].Vdata);
                while(p)
                {
                        printf("->");
                        printf("  %d",adjlist[p->adjvex].Vdata);
                        p=p->nextarc ;
                }
                printf("\n");
        }

}
void BFS(VNode  adjlist[],Graph &graph,int v)                                //广度优先遍历
{
        ArcNode *p;
        int queue[MAXV],front=0,rear=0;
        int w,i;

        for(i=0;i<graph.n;i++)
                visited[i]=0;
        printf("%2d",v);
        visited[v]=1;
        rear=(rear+1)%MAXV;
        queue[rear]=v;
        while(front!=rear)
        {
                front=(front+1)%MAXV;
                w=queue[front];
                p=adjlist[w].firstarc;
                while(p!=NULL)
                {
                        if(visited[p->adjvex]==0)
                        {
                                printf("%2d",p->adjvex);
                                visited[p->adjvex]=1;
                                rear=(rear+1)%MAXV;
                                queue[rear]=p->adjvex;
                        }
                        p=p->nextarc;
                }
        }
        printf("\n");
}



void DFS(VNode  adjlist[],Graph &graph,int v)                                //非递归深度优先遍历
{
        ArcNode *p;
        ArcNode *St[MAXV];
        int top=-1,w,i;
        for(i=0;i<graph.n;i++)
                visited[i]=0;
        printf("%2d",v);
        visited[v]=1;
        top++;
        St[top]=adjlist[v].firstarc;
        while(top>-1)
        {
                p=St[top];
                top--;
                while(p!=NULL)
                {
                         w=p->adjvex;
                         if(visited[w]==0)
                         {
                                 printf("%2d",w);
                                 visited[w]=1;
                                 top++;
                                 St[top]=adjlist[w].firstarc;
                                 
                         }
                         p=p->nextarc ;
                         
                }
        }
        printf("\n");
}


主函数:
void main()
{
        int i,j,t,c,n,v,e;
        VNode adjlist[MAXV];
        Graph graph;
        FILE *fp;
        char str[200];
        ArcNode *P;
        ALGraph *G;
        printf("\n");
        printf("\n");
        printf("                               图遍历的演示:\n");
        printf("                          正在从文件中读取... ");
        printf("\n");
        printf("                                请稍候!\n");
        printf("                          从文件读取信息完毕!\n");
        if((fp=fopen("D:\\C.txt","rt"))==NULL)   //打开C文件(C中存放图的信息)
        {
                printf("\n Cannot open file strike any key exit!");
        }
        while(fgets(str,200,fp)!=NULL)                   //从文件中读取字符串
        {
                printf("%s",str);
                printf("\n");

        }
        printf("\n");
        printf("无向图的邻接表:\n"); 
        Creatgraph(adjlist,graph);
        DispAdj(adjlist,graph);
        printf("你想通过哪个顶点遍历DFS算法?");
                        scanf("%d",&t);
        DFS(adjlist,graph,t);
                
        printf("\n你想通过哪个顶点遍历BFS算法?");
        scanf("%2d",&t);
        BFS(adjlist,graph,t);
}
(手动输入小型矩阵必须把无向图顶点的边都输入进去 如 V1顶点连接V2顶点 那当你输入起始编号和终点编号的时候都得输入v1 v2
和v2 v1)
若有同学有疑问,可以联系我QQ77325313,我也是学习小组布置的任务,可以互相交流.





题目要求

题目要求

自己做的一个简单的图

自己做的一个简单的图

评分

参与人数 1鱼币 +5 收起 理由
零度非安全 + 5 支持楼主！

查看全部评分

想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

～风介～
发表于 2015-12-14 00:32:25 | 显示全部楼层
亲，可以考虑用代码格式发布代码哦~
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

SonOmiga
 楼主| 发表于 2015-12-14 12:50:15 | 显示全部楼层
～风介～ 发表于 2015-12-14 00:32
亲，可以考虑用代码格式发布代码哦~

怎么用啊

评分

参与人数 1鱼币 +5 收起 理由
零度非安全 + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

～风介～
发表于 2015-12-14 17:32:54 | 显示全部楼层
SonOmiga 发表于 2015-12-14 12:50
怎么用啊

QQ拼音截图未命名.png
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

SonOmiga
 楼主| 发表于 2015-12-18 14:04:52 | 显示全部楼层
～风介～ 发表于 2015-12-14 17:32

好了 ! :loveliness:

评分

参与人数 1鱼币 +20 收起 理由
零度非安全 + 20 支持楼主！

查看全部评分

想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-26 16:36

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表