| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 402 人关注过本帖
标题:今晚写的有关于图的一些操作算法,欢迎指教
只看楼主 加入收藏
q491701201
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2011-5-12
结帖率:0
收藏
已结贴  问题点数:20 回复次数:2 
今晚写的有关于图的一些操作算法,欢迎指教
#include<stdio.h>
#include<malloc.h>
#include<windows.h>

#define MAX_Weight 1000        //定义无穷大的具体值
#define MAX_Ver    10            //定义顶点数的最大值


typedef enum
{
        DG,        //不带权有向图
        AG,        //不带权无向图
        WDG,    //带权有向图
        WAG        //带权无向图
}GraphKind;        //图的种类结构体定义

/**************************
//
//邻接链表表示法
//
**************************/

typedef struct LinkNode
{
        int adjvex;                //邻接点在头结点数组中的下标位置
        int infor;                //边或弧的相关信息,如权值        
        struct LinkNode *next;    //指向下一个邻接点
}LinkNode;

typedef struct
{
        char data;                //顶点信息
        int degree;                //顶点的度
        LinkNode *first;        //指向第一个表结点
}VexNode;                        //顶点结点类型定义

typedef struct
{
        char data1,data2;        //边或弧所依附的顶点
        int infor;                //边或弧的相关信息,如权值
}ArcNode;                        //边或弧类型定义

typedef struct
{
        GraphKind  kind;        //图的种类标志
        int vexnum;                //顶点数目
        int arcnum;                //边或弧的数目
        VexNode  list[MAX_Ver];    //顶点信息集合
}Graph;                            //图的类型定义

void Create_Graph( Graph *G )    //图的初始化,建立一个空图
{
        G->vexnum = 0;
        G->arcnum = 0;
}

/*
 * 图的顶点定位,如果顶点存在则返回该顶点在头结点数组中的下标值;
 * 如果顶点不存在,则返回数值-1.
*/
int Locate_Vex( Graph *G, char v )
{
        int k;
        for ( k=0; k<G->vexnum; k++ )
        {
                if(G->list[k].data == v)        //顶点存在则返回该顶点下标值
                        return k;
                else
                        continue;
        }
        return -1;        //顶点不存在,则返回-1
}

/***************************
 * 向头结点数组中添加顶点
***************************/
void Add_Vex( Graph *G, char v )
{
        if(G->vexnum > MAX_Ver)
                printf("图的顶点数超出预定范围,发生越界!\n");
        else if(Locate_Vex(G,v) != -1)
                printf("你所输入的顶点已经存在!\n");
        else
        {
                G->list[G->vexnum].data = v;            //向数组存入顶点
                G->list[G->vexnum].degree = 0;            //顶点的度置为0
                G->list[G->vexnum].first = NULL;        //顶点指针域置为空
                G->vexnum++;                                //顶点数增加1
        }

}

/******************************
 * 利用两个顶点构造图的边或弧
******************************/
void Add_Arc( Graph *G, ArcNode *arc )
{
        int k,j;
        LinkNode *q,*p;            //边或弧所依附的表结点
        k = Locate_Vex(G,arc->data1);    //弧尾顶点的下标值
        j = Locate_Vex(G,arc->data2);    //弧头顶点的下标值

        if(k == -1)
                printf("顶点%c不存在!\n",arc->data1);
        else if(j == -1)
                printf("顶点%c不存在!\n",arc->data2);
        else
        {
                p = (LinkNode*)malloc(sizeof(LinkNode));        //开辟弧尾表结点的存储空间
                p->adjvex = arc->data1;
                p->infor = arc->infor;
                p->next = NULL;

                q = (LinkNode*)malloc(sizeof(LinkNode));        //开辟弧头表结点的存储空间
                q->adjvex = arc->data2;
                q->infor = arc->infor;
                q->next = NULL;
        }
        
        //如果建立无向图的邻接链表,则利用头插入法把两个表结点分别插入到对应的单链表中
        if(G->kind == AG || G->kind == WAG)
        {
                q->next = G->list[k].first;
                G->list[k].first = q;
                G->list[k].degree++;
                p->next = G->list[j].first;
                G->list[j].first = p;
                G->list[j].degree++;
        }
        else
        {
                //建立有向图的正邻接链表
                q->next = G->list[k].first;
                G->list[k].first = q;
                G->list[k].degree++;
        }

}

//图的邻接链表输出
void Output_Graph( Graph *G )
{
        int j;
        LinkNode *q;

        printf("\n你输入的图是:");
        switch(G->kind)
        {
                case 0:
                        printf("    DG:不带权有向图!\n"); break;
                case 1:
                        printf("    AG:不带权无向图!\n"); break;
                case 2:
                        printf("    WDG:带权有向图!\n"); break;
                case 3:
                        printf("    WAG:带权无向图!\n"); break;
        }

        printf("\n图的邻接链表输出如下:\n\n");
        printf("下标 | 顶点 | 度 | 邻接点下标 | 权值");
        for ( j=0; j<G->vexnum; j++ )
        {
                printf("\n");
                printf(" %d      (%c  , %d)",j,G->list[j].data,G->list[j].degree);
                q = G->list[j].first;
                while(q != NULL)
                {
                        int k;
                        k = Locate_Vex(G,q->adjvex);
                        printf("%s"," ->");
                        printf(" (%d,%d)",k,q->infor);
                        q = q->next;
                }
        }
}

typedef enum
{
        F,
        T
}Bool;
Bool visit[MAX_Ver];
//从顶点V出发,深度遍历V所在的子图
void DFS( Graph *G ,char v )
{
   
        int k;
        k = Locate_Vex(G,v);
        LinkNode *p;
        visit[k] = T;            //置访问标志
        printf("%c  ",G->list[k].data);
        p = G->list[k].first;
        while(p != NULL)
        {
                int j = Locate_Vex(G,p->adjvex);
                if(visit[j] != TRUE)
                        DFS(G,p->adjvex);
                p = p->next;
        }
}

//深度优先遍历函数
void DFS_Traverse( Graph *G )
{
        int v;
        for ( v=0; v<G->vexnum; v++ )
                visit[v] = F;
        LinkNode *p = G->list[v].first;
        for ( v=0; v<G->vexnum; v++ )
                if(!visit[v])
                        DFS(G,G->list[v].data);
}

//定义一个队列将要访问的顶点
typedef struct
{
        int Data[MAX_Ver];
        int front,rear;
}Queue;

//广度优先遍历函数
void BFS_Traverse( Graph *G )
{
        int k,v,w;
        LinkNode *p;
        Queue *q;
        q = (Queue*)malloc(sizeof(Queue));        //开辟空间
        q->front = q->rear = 0;    //初始化队列队头与队尾
        for ( k=0; k<G->vexnum; k++ )
                visit[k] = F;    //初始化访问标志
        for ( k=0; k<G->vexnum; k++ )
        {
               
                if(!visit[k])            //下标为V的顶点尚未访问
                {
                        q->Data[q->rear++] = k;    //顶点下标入队
                        while(q->front != q->rear)
                        {
                             w = q->Data[q->front++];
                             visit[w] = T;
                             printf("%c  ",G->list[w].data);
                             p = G->list[w].first;
                             while(p != NULL)
                             {
                                     if(!visit[Locate_Vex(G,p->adjvex)])
                                             q->Data[q->rear++] = Locate_Vex(G,p->adjvex);
                                     p = p->next;
                             }
                        }
                }
        }
}

int main()
{
        
        int weight;        //边或弧的权值
        char Vex[MAX_Ver],vex,fex1,fex2;    //图的顶点
        char Vex1[MAX_Ver],Vex2[MAX_Ver];        //边或弧所依附的两个顶点
        
        Graph *G;        //定义一个图类型
        ArcNode *arc;    //定义一个边类型

        printf("调用初始化函数建立空图G...\n");
        G = (Graph*)malloc(sizeof(Graph));        //申请存放图G的空间
        Create_Graph(G);        //调用初始化函数建立G
        printf("初始化结束!\n");
        printf("你要建立的图种类是:\n    0:不带权有向图    1:不带权无向图    2:带权有向图    3:带权无向图\n");
        scanf("%d",&G->kind);
        printf("请输入图的顶点,以\".\"结束.\n");
        while( 1 )
        {
                scanf("%s",Vex);
                vex = Vex[0];
                if(vex == '.')
                        break;
                else
                        Add_Vex(G,vex);
               
        }
        arc = (ArcNode*)malloc(sizeof(ArcNode));
        if(G->kind == AG || G->kind == DG)
        {
                printf("\n\n请按\"顶点 顶点\"的形式输入图的边或弧,当输入\". .\"时结束输入!\n");
                while( 1 )
                {
                        scanf("%s%s",Vex1,Vex2);
                        fex1 = Vex1[0];
                        fex2 = Vex2[0];
                        if(fex1 == '.' && fex2 == '.')
                                break;
                        else
                        {
                                arc->data1 = fex1;
                                arc->data2 = fex2;
                                arc->infor = 0;
                                Add_Arc(G,arc);
                                printf("继续输入边或弧:\n");
                        }

                }
        }
        else
        {
                printf(" \n\n请按\"顶点 顶点 权值\"的形式输入图的边或弧,当输入\". . 0\"时结束输入!\n");
                while( 1 )
                {
                        scanf("%s%s%d",Vex1,Vex2,&weight);
                        fex1 = Vex1[0];
                        fex2 = Vex2[0];
                        if(fex1 == '.' && fex2 =='.' && weight == 0)
                                break;
                        else
                        {
                                arc->data1 = fex1;
                                arc->data2 = fex2;
                                arc->infor = weight;
                                Add_Arc(G,arc);
                                printf("继续输入边或弧:\n");
                        }
                }
        }

        Output_Graph(G);
        int ch;
        printf("\n\n你想通过哪种方式遍历所建立的图?\n");
        printf("1:深度优先遍历(DFS)\n2:广度优先遍历(BFS)\n\n");
        L:scanf("%d",&ch);
        switch(ch)
            {
                case 1:
                    {
                            printf("你选择了深度优先遍历,遍历结果如下:\n");
                            DFS_Traverse(G);        //调用深度优先遍历函数
                            break;
                    }
                case 2:
                    {
                            printf("你选择了广度优先遍历,遍历结果如下:\n");
                            BFS_Traverse(G);        //调用广度优先遍历函数
                            break;
                    }
                default:
                        printf("输入错误,请重新输入:");
                        goto L;
                    
            }
        Sleep(2*1000);
        printf("\n\n电脑分析结果与人工分析结果一致!\n\n");
        return 0;
}
搜索更多相关主题的帖子: 结构体 最大值 
2011-05-12 22:41
诸葛修勤
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:11
帖 子:549
专家分:1955
注 册:2010-10-28
收藏
得分:20 
不管怎么说 敲出这么多那就是厉害 支持下
2011-05-13 08:25
诸葛修勤
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:11
帖 子:549
专家分:1955
注 册:2010-10-28
收藏
得分:0 
试了下 效果很好


改进下  在图的遍历的时候 最好做成可以选择从哪个顶点开始遍历
2011-05-13 08:33
快速回复:今晚写的有关于图的一些操作算法,欢迎指教
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.031220 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved