建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历

}

s->adjvex=i-1; s->nextarc=G->adjlist[j-1].firstedge; G->adjlist[j-1].firstedge=s;

////输出邻接表...

}/*CreateALGraph*/

void DFS(ALGraph *G, int v) { EdgeNode *p ; Visited[v]=TRUE ;

printf(\/* 置访问标志，访问顶点v */

p=G->adjlist[v].firstedge; /* 链表的第一个结点 */

while (p!=NULL){

if(!Visited[p->adjvex])

DFS(G, p->adjvex);/* 从v的未访问过的邻接顶点出发深度优先搜

索 */

p=p->nextarc ;

}

}

void DFS_traverse (ALGraph *G) {

int v ;

EdgeNode *p ;

printf(\深度度优先搜索输出结点信息:\

for (v=0; vn; v++) Visited[v]=FALSE ; /* 访问标志初始化 */

p=G->adjlist[v].firstedge ;

for (v=0; vn; v++)

if (!Visited[v]) DFS(G,v); }

///////////////队列 ///////////////////////

typedef struct Node {

ElemType data; // 元素数据

struct Node *next; // 链式队列中结点元素的指针 } QNode, *QueuePtr;

typedef struct {

QueuePtr front; // 队列头指针 QueuePtr rear; // 队列尾指针 } LinkQueue;

Status InitQueue(LinkQueue &Q) { //构造一个空队列Q

Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if(Q.front == NULL) exit(OVERFLOW); //存储失败 Q.front ->next = NULL; return OK; }

Status DestoryQueue(LinkQueue &Q) {

//销毁队列Q

while(Q.front){

Q.rear = Q.front->next; //利用尾指针移动保存队头指针 free(Q.front); //依次释放头结点

Q.front = Q.rear;

}

return OK; }

Status QueueEmpty(LinkQueue Q) {

//assert(Q.front != NULL && Q.rear != NULL); if(Q.front == Q.rear) return TRUE; else

return FALSE; }

Status EnQueue(LinkQueue &Q, ElemType e) //插入元素e为Q新的队尾元素 {

QueuePtr p = (QueuePtr )malloc(sizeof(QNode));

if(!p) exit(OVERFLOW); //存储失败 p ->data = e; p ->next = NULL;

Q.rear ->next = p; //当前队尾指针指向新的结点

Q.rear = p; //移动队尾知道到新的结点，当前结点成为队尾结点 return OK; }

Status DeQueue(LinkQueue &Q, ElemType *e)

//若队列不空，则删除Q的队头元素，用e返回值，并返回OK。否则返回ERROR {

if(Q.front == Q.rear) return ERROR; QueuePtr p = Q.front ->next; *e = p ->data;

Q.front ->next= p ->next; if(Q.rear == p)

Q.rear = Q.front; //只有一个元素，恢复到空队列，只有各头结点 free(p); return OK; }

///////////////////////////////////////

int Visit(int v,ALGraph G) {

// printf(\

printf(\ return OK; }

void BFSTraverse(ALGraph G, Status (*Visit)(int v,ALGraph G))