FirstAdjVex(G,v)怎样用程序实现
发布网友
发布时间：2022-04-26 11:40
共2个回答
热心网友
时间：2022-04-23 01:04
可能是功底有限吧 网上有的代码实在看不懂 又好又精彩的代码 暂时没找到 看到这个问题的浏览量还不小 我来抛这块砖吧
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
热心网友
时间：2022-04-23 02:22
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;
}
