|
#include
#include
#include
#define INF 32767
#define MAVX 100
typedef int InfoType;
typedef int Vertex;
typedef struct
{
int no;
InfoType info;
}VertexType;
typedef struct
{
int edges[MAVX][MAVX];
int vexnum,arcnum;
VertexType vexs[MAVX];
}MGraph;
typedef struct ANode
{
int adjvex;
struct ANode *nextarc;
InfoType info;
}ArcNode;
typedef struct Vnode
{
Vertex data;
ArcNode *firstarc;
}VNode;
typedef VNode AdjList[MAVX];
typedef struct
{
AdjList adjlist;
int n,e;
}ALGraph;
int visited[MAVX];
void MatToList(MGraph g,ALGraph * &G)
{
int i,j,n=g.vexnum;
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
for(i=0;iadjlist[i].firstarc=NULL;
for(i=0;i=0;j--)
if(g.edges[i][j]!=0)
{
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=j;
p->info=g.edges[i][j];
p->nextarc=G->adjlist[i].firstarc;
G->adjlist[i].firstarc=p;
}
G->n=n;
G->e=g.arcnum;
}
void DispMat(MGraph g)
{
int i,j;
for(i=0;i
int i;
ArcNode *p;
for(i=0;in;i++)
{
p=G->adjlist[i].firstarc;
if(p!=NULL)printf("%3d:",i);
while(p!=NULL)
{
printf("%3d",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}
void DFS(ALGraph *G,int v)
{
ArcNode *p;
visited[v]=1;
p=G->adjlist[v].firstarc;
while(p!=NULL)
{
if(visited[p->adjvex]==0)
{
printf(" ",v,p->adjvex);
DFS(G,p->adjvex);
}
p=p->nextarc;
}
}
void BFS(ALGraph *G,int v)
{
ArcNode *p;
int queue[MAVX],front=0,rear=0;
int visited[MAVX];
int w,i;
for(i=0;in;i++) visited[i]=0;
visited[v]=1;
rear=(rear+1)%MAVX;
queue[rear]=v;
while(front!=rear)
{
front=(front+1)%MAVX;
w=queue[front];
p=G->adjlist[w].firstarc;
while(p!=NULL)
{
if(visited[p->adjvex]==0)
{
printf(" ",w,p->adjvex);
visited[p->adjvex]=1;
rear=(rear+1)%MAVX;
queue[rear]=p->adjvex;
}
p=p->nextarc;
}
}
printf("\n");
}
int main()
{
int i,j;
MGraph g;
ALGraph *G;
int A[MAVX][11];
g.vexnum=11;
g.arcnum=13;
for(i=0;i |