回 帖 发 新 帖 刷新版面

主题:[原创]跪求编程高手帮忙之图的遍历

邻接多重表图的遍历,运行不出来,请高手帮下忙,小妹感激涕零
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include <conio.h>
#include<malloc.h>
using namespace std;
#define MAX_VERTEX_NUM 30
struct EBox
 {
  int mark; 
   int ivex,jvex;
   EBox *ilink,*jlink;
  
 };
 struct VexBox
 {
   int data;
   EBox *firstedge; 
 };
 struct AMLGraph
 {
   VexBox adjmulist[MAX_VERTEX_NUM];
   int vexnum,edgenum;
 };
 typedef struct QNode
 {
     int data;
     struct QNode *next;
 }QNode,*QueuePtr;
 typedef struct
 {
     QueuePtr front;
     QueuePtr rear;
 }LinkQueue;
int visited[MAX_VERTEX_NUM];

int LocateVex(AMLGraph ,int );
void Initilized(AMLGraph &G)
 { 
   int i,j,k,n,m;
   int va,vb;
   EBox *p;
  printf("请输入无向图的顶点数,边数\n ");

    cin>>n>>m;

    G.vexnum=n;
    G.edgenum=m;
    printf("请输入顶点的值:\n");

   for(i=0;i<n;i++) 
   {
       cin>>G.adjmulist[i].data;
     G.adjmulist[i].firstedge=NULL;
   }
   printf("请输入每条边的两个端点:\n");
   for(k=0;k<m;k++)
   {
     printf("第%d边",k+1);


     cin>>va>>vb;
     i=LocateVex(G,va); 
     j=LocateVex(G,vb); 
     p=(EBox*)malloc(sizeof(EBox));
     p->mark=0; 
     p->ivex=i;
     p->ilink=G.adjmulist[i].firstedge; 
     G.adjmulist[i].firstedge=p;
     p->jvex=j;
     p->jlink=G.adjmulist[j].firstedge; 
     G.adjmulist[j].firstedge=p;
   }
}
int LocateVex(AMLGraph G,int u)
{
    int i;
    for(i=0;i<G.vexnum;++i)
    {
        if(G.adjmulist[i].data==u)
          return i;
    }
    return -1;
}
int FirstAdjVex(AMLGraph G,int v)
 { 
   int i;
   i=LocateVex(G,v);
   if(i<0) 
     return -1;
   if(G.adjmulist[i].firstedge) 
     if(G.adjmulist[i].firstedge->ivex==i)
       return G.adjmulist[i].firstedge->jvex;
     else if(G.adjmulist[i].firstedge->jvex==i)
       return G.adjmulist[i].firstedge->ivex;
   else
     return -1;
 }

 int NextAdjVex(AMLGraph G,int v,int w)
 { 
   int i,j;
   EBox *p;
   i=LocateVex(G,v); 
   j=LocateVex(G,w); 
   if(i<0||j<0) 
     return -1;
   p=G.adjmulist[i].firstedge;
   while(p)
     if(p->ivex==i&&p->jvex!=j)
       p=p->ilink; 
     else if(p->jvex==i&&p->ivex!=j) 
       p=p->jlink; 
     else 
       break;
   if(p&&p->ivex==i&&p->jvex==j)
   {
     p=p->ilink;
     if(p&&p->ivex==i)
       return p->jvex;
     else if(p&&p->jvex==i)
       return p->ivex;
   }
   if(p&&p->ivex==j&&p->jvex==i) 
   {
     p=p->jlink;
     if(p&&p->ivex==i)
       return p->jvex;
     else if(p&&p->jvex==i)
       return p->ivex;
   }
   return -1;
}
 void DFS(AMLGraph G,int v)
 {
     int j;
     EBox *p;
     if(visited[v]==1)
         return;
     visited[v]=1;
     printf("%d\n",v);
     p=G.adjmulist[v].firstedge;
     while(p)
     {
         if(p->ivex==v)
             j=p->jvex;
         else 
             j=p->ivex;
         
         if(visited[j]==0)
             printf("<%d,%d>\n",v,j);
         
         DFS(G,j);
         if(p->ivex==v)
             p=p->ilink;
         else p=p->jlink;
         
         
     }
 }
 void DFS(AMLGraph ,int);
 void DFSTraverse(AMLGraph G)
 { 
    for(int v=0;v<G.vexnum;v++)
     visited[v]=0;
   for( v=0;v<=G.vexnum;v++)
     if(visited[v]==0)
       DFS(G,v);
 
 }

 void InitQueue(LinkQueue &Q)
 { // 构造一个空队列Q
   if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))
     exit(0);
   Q.front->next=NULL;
 }
 void EnQueue(LinkQueue &Q,int e)
 { // 插入元素e为Q的新的队尾元素
   QueuePtr p;
   if(!(p=(QueuePtr)malloc(sizeof(QNode)))) 
     exit(0);
   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 -1;
   p=Q.front->next;
   e=p->data;
   Q.front->next=p->next;
   if(Q.rear==p)
     Q.rear=Q.front;
   free(p);
   
 }

int QueueEmpty(LinkQueue Q)
 { 
   if(Q.front->next==NULL)
     return 1;
   else
     return 0;
 }

 
void BFSTraverse(AMLGraph G)
 { 
   int u,w,v;
   LinkQueue Q;
   for( v=0;v<G.vexnum;v++)
     visited[v]=0;
   InitQueue(Q); 
   for(v=0;v<G.vexnum;v++)
     if(visited[v]==0) 
     {
         printf("%d\n",v);
       visited[v]=1; 
       EnQueue(Q,v); 
       while(QueueEmpty(Q)==0) 
       {
         DeQueue(Q,u); 
         for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data))
           if(visited[w]==0)
           {
             printf("<%d,%d>\n",u,w);
             visited[w]=1;
        printf("%d\n",w);
             EnQueue(Q,w);
           }
       }
     }
  }
void main()
 {
   
   AMLGraph G;
   int v1,v2;
   Initilized(G);
 printf("深度优先搜索的结果:\n");
   DFSTraverse(G);
  printf("广度优先搜索的结果:\n");
   BFSTraverse(G);
  
 }

回复列表 (共1个回复)

沙发

[求助]跪求遍历表格提取相应表格中数据的代码hits:129

我来回复

您尚未登录,请登录后再回复。点此登录或注册