Question

FirstAdjVex(G,v)怎样用程序实现

Answer 1

可能是功底有限吧 网上有的代码实在看不懂  又好又精彩的代码 暂时没找到 看到这个问题的浏览量还不小 我来抛这块砖吧

int FirstAdjVex(Graph G,int v)
{
   int i;
   if(!G.vertices[v].firstarc)//判断是否有临界点
    {
        return 0;
    }
   return G.vertices[v].firstarc->adjvex;//如果有返回该点的位置
}
int NextAdjVex(Graph G,int u,int w)//表示u相对于w的下一个临界点w>=0 表示存在临界点
{
    ArcNode *p;
    p=G.vertices[u].firstarc;
    while(p&&p->adjvex!=w)
        p=p->nextarc;//找到w点的位置
        p=p->nextarc;////w位置的下一个位置

       if(p)//如果该位置不为NULL说明和u位置还有相连的
      {        
       return p->adjvex;
     }
       return -1;//该位置为NULL说明，与u位置有关系的点已经遍历完
}

(以上为无方向的图)

也许图难就难在指针和位置的交叉吧 加油

下面是我的代码 因为只针对这个遍历所以比较简单 见笑了

#include<iostream>
#include"Status.h"
int visited[100];
using namespace std;
typedef struct ArcNode
{
  int adjvex;
  struct ArcNode *nextarc;
  int info;   
}ArcNode;
typedef struct VNode
{
    char data;
    ArcNode *firstarc;
}VNode,AdjList[100];
typedef struct
{
    AdjList vertices;
    int vexnum,arcnum;
}Graph;
typedef struct
{
    int *base;
    int front;
    int rear;
}SqQueue;
Status InitQueue(SqQueue &Q)
{
    Q.base=new int[100];
    Q.front=Q.rear=0;
    return OK;
}
int EnQueue(SqQueue &Q,int e)
{
    Q.base[Q.rear]=e;
    Q.rear=Q.rear+1;
    return OK;
}
Status DeQueue(SqQueue &Q,int &e)
{
   
    e=Q.base[Q.front];
     cout<<"出队e:"<<e<<endl;
    Q.front+=1;
    return OK;
}
Status QueueEmpty(SqQueue Q)
{
    if(Q.rear==Q.front)
    return OK;
    return 0;
}
int LocateVex(Graph G,char t)
{
    int i;
    for(i=1;i<G.vexnum;i++)
    {
        if(G.vertices[i].data==t)
        return i;
    }
}
Status CreateGraph(Graph &G)
{
    int i,j,k;
    ArcNode *p1;
    cout<<"请输入结点个数："<<endl;
    cin>>G.vexnum;
    cout<<"请输入边的个数："<<endl;
    cin>>G.arcnum;
    for(i=1;i<=G.vexnum;i++)
    {
        cout<<"输入顶点："<<endl;
        cin>>G.vertices[i].data;
        visited[i]=0;
        G.vertices[i].firstarc=NULL;
    }
    char v1,v2;
    for(k=0;k<G.arcnum;k++)
    {
        cout<<"输入两顶点："<<endl;
        cin>>v1>>v2;
        i=LocateVex(G,v1);
        j=LocateVex(G,v2);
        p1=new ArcNode;
        p1->adjvex=j;
        //cout<<"j="<<j<<endl;
        p1->nextarc=G.vertices[i].firstarc;
        G.vertices[i].firstarc=p1;
        p1=new ArcNode;
        p1->adjvex=i;
        //cout<<"i="<<i<<endl;
        p1->nextarc=G.vertices[j].firstarc;
        G.vertices[j].firstarc=p1;
    }
}
int FirstAdjVex(Graph G,int v)
{
   int i;
   if(!G.vertices[v].firstarc)
    {
        return 0;
    }
   return G.vertices[v].firstarc->adjvex;
}
int NextAdjVex(Graph G,int u,int w)//表示u相对于w的下一个临界点w>=0 表示存在临界点
{
    ArcNode *p;
    p=G.vertices[u].firstarc;
    while(p&&p->adjvex!=w)
        p=p->nextarc;
        p=p->nextarc;
       if(p)
      {        
       return p->adjvex;
     }
       return -1;
}
void BFS(Graph G,int v)//v=1
{   
    //visited[v]=1;
    SqQueue Q;
    InitQueue(Q);
    EnQueue(Q,v);//v=1
    int u,w;
    while(!QueueEmpty(Q))
    {
        DeQueue(Q,u);//u=1
        for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
            if(!visited[w])
           {   
                 visited[w]=1;
                cout<<G.vertices[w].data<<endl;
                EnQueue(Q,w);   
           }
      }
}
int main()
{
    Graph g;
    CreateGraph(g);
    BFS(g,1);
    return 0;
}

                                                                              2016 12 15

Answer 2

int FirstadjVex(Graph G,int v)//若无邻接点，返回-1
{//返回图G中第v个顶点的第一个邻接点
int i,j=-1;//可能是顶点自身到自身
for(i=0;i<G.vexnum;i++)
{
if(!G.Arcs[v][i].adj||G.Arcs[v][i].adj==INFINITY)//第v个顶点的第i个邻接顶点
j++;
else
{
j++;
break;
}
}
if(i==G.vexnum-1&&!G.Arcs[v][i].adj||G.Arcs[v][i].adj==INFINITY)
return -1;
return j;
}