#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MAX_VERTEX_NUM 50
typedef struct Arcnode
{
int adjvex;
struct Arcnode *nextarc;
} Arcnode;
typedef struct VNode
{
int data;
Arcnode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertice;
int vexnum, arcnum;
int kind;
} Graph;
int visit[100];//用来标记每个定点是否被访问过
void changeV_G(int v[], Graph &G, int n);//将邻接矩阵转换成邻接表int FirstAdjVex(Graph G, int v);
int NextAdjVex(Graph G, int v, int w);
void DFS(Graph G, int v);
void DFSTraverse(Graph G, int v[]);
void changeV_G(int v[], Graph &G, int n)
{
for(int i=0; i<n; i++)
{
G.vertice[i].data=i;
G.vertice[i].firstarc=NULL;
}
G.vexnum=n;//图的顶点数
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
{
int x=n*i+j;
if(v[x]==1)
{
if(G.vertice[i].firstarc==NULL)
{
G.vertice[i].firstarc=new Arcnode;
G.vertice[i].firstarc->adjvex=j;
G.vertice[i].firstarc->nextarc=NULL;
}
else
{
Arcnode *p=G.vertice[i].firstarc;
for(; p->nextarc!=NULL; p=p->nextarc)
{
}
p->nextarc=new Arcnode;
p=p->nextarc;
p->adjvex=j;
p->nextarc=NULL;
}
}
}
}
void DFSTraverse(Graph G, int visit[], int n)
{
for(int i=0; i<n; i++)
{
for(int v=0; v<G.vexnum; v++) visit[v] = 0;
for(int v=i; v<G.vexnum; v++)
if(!visit[v]) DFS(G,v);
printf("\n");
}
}
void DFS(Graph G, int v)
{
visit[v]=1;
printf("%d ",G.vertice[v].data );
int w;
for( w = FirstAdjVex(G, v); w>= 0; w = NextAdjVex(G, v, w)) {
if(!visit[w])
DFS(G, w);
}
}
int FirstAdjVex(Graph G, int v)//G.vertice[v].data
{
if(G.vertice[v].firstarc!=NULL)
return G.vertice[v].firstarc->adjvex;
else
return -1;
}
int NextAdjVex(Graph G, int v, int w)
{
Arcnode *p;
for(p = G.vertice[v].firstarc;;)
{
if(p->adjvex==w)
break;
p=p->nextarc;
}
if(p->nextarc==NULL) return -1;
else return p->nextarc->adjvex;
}
typedef struct QNode
{
int data;
struct QNode *next;
} QNode, *QueuePtr;
typedef struct
{
QueuePtr ffront;
QueuePtr rear;
} LinkQueue;
int InitQueue(LinkQueue &Q)
{
Q.ffront=(QueuePtr)malloc(sizeof(QNode));
Q.rear=Q.ffront;
if(!Q.ffront) exit(1);
Q.ffront->next = NULL;
return 1;
}
int EnQueue(LinkQueue &Q, int e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(1);
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return 1;
}
int Dequeue(LinkQueue &Q, int &e)
{
if(Q.ffront == Q.rear) return 0;
QueuePtr p;
p = Q.ffront->next;
e = p ->data;
Q.ffront->next = p->next;
if(Q.rear==p) Q.rear = Q.ffront;
free(p);
return 1;
}
int QueueEmpty(LinkQueue Q)
{
if(Q.ffront==Q.rear)
return 1;
else return 0;
}
void BFSTraverse(Graph G, int visit[], int n)
{
int v;
for(int i=0; i<n; i++)
{
for(v=0; v<G.vexnum; v++)
visit[v]=0;
LinkQueue Q;
InitQueue(Q);
int w, u;
for(v=i; v<G.vexnum; v++)
if(!visit[v])
{
visit[v] = 1;
printf("%d ", G.vertice[v].data);
EnQueue(Q, v);//v入队列
while(!QueueEmpty(Q))
{
Dequeue(Q, u);//队头元素出队并置为u
for(w=FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
if(! visit[w])
{
visit[w] = 1;
printf("%d ", G.vertice[w].data);
EnQueue(Q, w);//w入队列
}//if
}//while
}//if
printf("\n");
}
}
int main()
{
int n;
int *v;//图的邻接矩阵
Graph G;
scanf("%d", &n);
v =(int *) malloc(sizeof(int)*n*n);
for(int i=0; i<n*n; i++)
scanf("%d", &v[i]);
changeV_G(v, G, n);//将邻接矩阵转换成邻接表
printf("DFS\n");
DFSTraverse(G, visit, n);
printf("WFS\n");
BFSTraverse(G, visit, n);
return 0;
}。