数据结构代码（用C语言） 图的遍历操作

数据结构代码（用C语言） 图的遍历操作

#include
#include
#include
#include
#include
#include
#include
#include
#include

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1

typedef int Status;
typedef int Boolean; Boolean 是布尔类型,其值是TRUE 或FALSE */


#define MAX_VERTEX_NUM 20
typedef enumGraphKind;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
InfoType *info;
}ArcNode;
typedef struct
{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;




int LocateVex(ALGraph G,VertexType u)
{

int i;
for(i=0;iif(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
Status CreateGraph(ALGraph &G)
{
int i,j,k;
int w;
VertexType va,vb;
ArcNode *p;
printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
scanf("%d",&(G.kind));
printf("请输入图的顶点数,边数: ");
scanf("%d,%d",&(G.vexnum),&(G.arcnum));
printf("请输入%d 个顶点的值(<%d 个字符):\n",G.vexnum,MAX_NAME);
for(i=0;i{
scanf("%s",G.vertices[i].data);
G.vertices[i].firstarc=NULL;
}
if(G.kind==1||G.kind==3)
printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");
else
printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
for(k=0;k{
if(G.kind==1||G.kind==3)
scanf("%d%s%s",&w,va,vb);
else
scanf("%s%s",va,vb);
i=LocateVex(G,va);
j=LocateVex(G,vb);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
if(G.kind==1||G.kind==3)
{
p->info=(int *)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL;
p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
if(G.kind>=2)
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;
if(G.kind==3)
{
p->info=(int*)malloc(sizeof(int));
*(p->info)=w;
}
else
p->info=NULL;
p->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=p;
}
}
return OK;
}
void DestroyGraph(ALGraph &G)
{
int i;
ArcNode *p,*q;
G.vexnum=0;
G.arcnum=0;
for(i=0;i{
p=G.vertices[i].firstarc;
while(p)
{
q=p->nextarc;
if(G.kind%2)
free(p->info);
free(p);
p=q;
}
}
}
VertexType* GetVex(ALGraph G,int v)
{
if(v>=G.vexnum||v<0)
exit(ERROR);
return &G.vertices[v].data;
}
int FirstAdjVex(ALGraph G,VertexType v)
{

ArcNode *p;
int v1;
v1=LocateVex(G,v);
p=G.vertices[v1].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,VertexType v,VertexType w)
{


ArcNode *p;
int v1,w1;
v1=LocateVex(G,v);
w1=LocateVex(G,w);
p=G.vertices[v1].firstarc;
while(p&&p->adjvex!=w1)
p=p->nextarc;
if(!p||!p->nextarc)
return -1;
else
return p->nextarc->adjvex;
}
Boolean visited[MAX_VERTEX_NUM];
void(*VisitFunc)(char* v);
void DFS(ALGraph G,int v)
{
int w;
VertexType v1,w1;
strcpy(v1,*GetVex(G,v));
visited[v]=TRUE;
VisitFunc(G.vertices[v].data);
for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))
if(!visited[w])
DFS(G,w);
}
void DFSTraverse(ALGraph G,void(*Visit)(char*))
{
int v;
VisitFunc=Visit;
for(v=0;vvisited[v]=FALSE;
for(v=0;vif(!visited[v])
DFS(G,v);
printf("\n");
}
typedef int QElemType;
#include"LinkQueueDef.h"
#include"LinkQueueAlgo.h"
void BFSTraverse(ALGraph G,void(*Visit)(char*))
{
int v,u,w;
VertexType u1,w1;
LinkQueue Q;
for(v=0;vvisited[v]=FALSE;
InitQueue(Q);
for(v=0;vif(!visited[v])
{
visited[v]=TRUE;
Visit(G.vertices[v].data);
EnQueue(Q,v);
while(!QueueEmpty(Q))
{
DeQueue(Q,u);
strcpy(u1,*GetVex(G,u));
for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
if(!visited[w])
{
visited[w]=TRUE;
Visit(G.vertices[w].data);
EnQueue(Q,w);
}
}
}
printf("\n");
}
void Display(ALGraph G)
{
int i;
ArcNode *p;
switch(G.kind)
{ case DG: printf("有向图\n"); break;
case DN: printf("有向网\n"); break;
case AG: printf("无向图\n"); break;
case AN: printf("无向网\n");
}
printf("%d 个顶点：\n",G.vexnum);
for(i=0;iprintf("%s ",G.vertices[i].data);
printf("\n%d 条弧(边):\n",G.arcnum);
for(i=0;i{
p=G.vertices[i].firstarc;
while(p)
{
if(G.kind<=1)
{
printf("%s→%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==DN)
printf(":%d ",*(p->info));
}
else
{
if(iadjvex)
{
printf("%s－%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
if(G.kind==AN)
printf(":%d ",*(p->info));
}
}
p=p->nextarc;
}
printf("\n");
}
}




#include "pubuse.h"
#define MAX_NAME 3
typedef int InfoType;
typedef char VertexType[MAX_NAME];
#include"ALGraphDef.h"
#include"ALGraphAlgo.h"
void print(char *i)
{
printf("%s ",i);
}

void main()
{
int i,j,k,n;
ALGraph g;
VertexType v1,v2;
printf("请选择有向图\n");
CreateGraph(g);
Display(g);
printf("深度优先搜索的结果:\n");
DFSTraverse(g,print);
printf("广度优先搜索的结果:\n");
BFSTraverse(g,print);
DestroyGraph(g);
}

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息