| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
Reworld,下班在家制作游戏,1500万奖金等你拿千里之行 始于足下
共有 629 人关注过本帖
标题:图的遍历,帮忙看看
只看楼主 加入收藏
qinj13178952
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2013-3-22
结帖率:75%
  已结贴   问题点数:20  回复次数:2   
图的遍历,帮忙看看
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 20
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define size 100
 char visited[size];
typedef struct QNode{
  int   data;
  struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
   QueuePtr front;
   QueuePtr rear;
   int data[size];
}LinkQueue;
typedef int  Status;
typedef int  VertexType;
typedef struct ArcNode{
        int adjvex;
        struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
        VertexType data;//顶点信息
       ArcNode    *firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{                 //图的定义
       AdjList vertices;     
        int vexnum,edgenum;//图的当前顶点数和弧数
        int kind;           
}ALGraph;




LinkQueue InitQueue(int n)
{
          LinkQueue Q;int i;QueuePtr p;
          Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
          if(!Q.front)
          printf("存储分配失败");
          Q.front->next=NULL;
          for(i=0;i<n;i++)
          {
             p=(QueuePtr)malloc(sizeof(QNode));
             scanf("%d",&p->data);
             Q.rear->next=p;
             Q.rear=p;
           }
           Q.rear->next = NULL;
          return Q;
}
void EnQueue(LinkQueue Q,int e)
{
          QueuePtr p;
          p=(QueuePtr)malloc(sizeof(QNode));
          if(!p)
          printf("存储分配失败");
          p->data=e;p->next=NULL;
          Q.rear->next=p;
          Q.rear=p;
}
int  DeQueue(LinkQueue Q,int e)
{
          QueuePtr p;
          if(Q.front==Q.rear) return 0;
          p=Q.front->next;e=p->data;
          Q.front->next=p->next;
          if(Q.rear==p)
          Q.rear=Q.front;
          free(p);
          return 1;
}
   


void CreateALGraph(ALGraph &G)//邻接表的建立
{
   int i;
   printf("请输入该树的顶点: ");
   scanf("%d",&G.vexnum);
    printf("请输入该树的边: ");
   scanf("%d",&G.edgenum);
   for(i=0;i<G.vexnum;i++)// 输入顶点信息
   {
    printf("第%d个顶点的信息为: ",i);
     scanf("%d",&G.vertices[i].data);
     G.vertices[i].firstarc=NULL;
   }
   for(i=0;i<G.vexnum;i++)//生成树
  {
          int index=-1;
          ArcNode *r,*p;//r指向当前链表的最后一个表结点;
          while(true)
          {
          printf("输入第%d个顶点的邻接点下标",i);
          scanf("%d",&v);
            p=(ArcNode *)malloc(sizeof(ArcNode));  //建单链表
             p->nextarc=NULL;
            p->adjvex=index;
          if(G.vertices[i].firstarc==NULL)   r=p;
                else
                 { r->nextarc=p; r=r->nextarc;}//尾插法建单链表储存弧来建立图
            }
     }
}



int FirstAdjVex(ALGraph G,int v)
{
    if(G.vertices[v].firstarc!=NULL)
    return G.vertices[v].firstarc->adjvex;
    else return ERROR;
}



int NextAdjVex(ALGraph G,int v,int w)
{
    ArcNode *q;
    q=G.vertices[v].firstarc;
    while(q)
    {
      if(G.vertices[q->adjvex].data==w)
        if(q->nextarc)  return G.vertices[q->nextarc->adjvex].data;
         else return ERROR;
      q=q->nextarc;
     }
    return ERROR;
} //查找G中第v个顶点的单链表中,值为w的下一个表结点的值,若没有则返回-1.

void BFSTraverse(ALGraph G)
{
   LinkQueue Q;
   int v;
  
   for(int v=0;v<G.vexnum;v++)
   visited[v]=false;
   InitQueue(20);
   for(v=0;v<G.vexnum;v++){
    int u;
    if(!visited[v]){
       visited[v]=true;
         printf("%d",G.vertices[v].data);
         EnQueue(Q,v);//将v入队
        while(Q.front!=Q.rear){
          DeQueue(Q,u);//出队一个元素放到u中
             for(int w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)){
                 if(!visited[w]){
                         visited[w]=true;
                         printf("%d",G.vertices[w].data);
                         EnQueue(Q,w);
                         }
                    }
               }
         }
       }
}
void DFS(ALGraph G, int v){
     visited[v]=TRUE;
     int w;
    printf("%d",G.vertices[v].data);
     for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
      if(!visited[w])
      DFS(G,w);
}




void DFSTraverse(ALGraph G){
   
     int v;
     for(v=0;v<G.vexnum;++v)
     visited[v]=FALSE;
     for(v=0;v<G.vexnum;++v)
     if(!visited[v]) DFS(G,v);
 }




int  main(void){
     
      ALGraph G;
      CreateALGraph(G);//采用邻接表存储图
       printf("深度优先遍历图");
     DFSTraverse(G);//深度优先遍历图
       printf("广度优先遍历图");
       BFSTraverse(G);//广度优先遍历图
     return 0;
}



[ 本帖最后由 qinj13178952 于 2013-5-16 23:39 编辑 ]
搜索更多相关主题的帖子: include 
2013-05-16 17:43
cuijunchao
Rank: 5Rank: 5
来 自:湖南桂东
等 级:职业侠客
威 望:3
帖 子:132
专家分:386
注 册:2012-4-4
  得分:20 
你这是要问什么呢?
2013-05-16 22:50
qinj13178952
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2013-3-22
  得分:0 
回复 2楼 cuijunchao
我就是按着书上的代码敲,然后再自己乱凑,然后在参考一下别人的代码,然后就是这样了,但是我不知道要怎么样改才可以正确运行
2013-05-16 23:41
快速回复:图的遍历,帮忙看看
数据加载中...
 
   



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

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