数据结构 图的遍历源代码

数据结构图的遍历

#include “LGraph.h“

Status CreateGraph（AMLGraph &G）//利用邻接多重表创建图
{
	FILE *fp*fq;
	int i;
	int x1y1;//用来储存输入的两个顶点的位置
	PEBox p;
	if（（fp=fopen（“Edge.txt““r“））==NULL）//打开文件
    {
        printf（“Open Failed!“）;
    }
    if（（fq=fopen（“City.txt““r“））==NULL）//打开文件
    {
        printf（“Open Failed!“）;
    }
	G.g=（VexBox*）malloc（MAX_VERTEX_NUM*sizeof（VexBox））;//为邻接多重表的头结点申请空间
	if（!G.g）
        return 0;
	G.vexnum=25;//结点个数
	G.edgenum=30;//边数
	for（i=0;i    {
		fscanf（fq“%s“&G.g[i].city）;
		G.g[i].data=i+1;
		G.g[i].firstedge=NULL;
	}
	for（i=0;i    {
		p=（PEBox）malloc（sizeof（EBox））;//新申请一个表结点来储存边的信息
		if（!p） return 0;
		p->ilink=NULL;
		p->jlink=NULL;
		fscanf（fp“%d“&x1）;
		fscanf（fp“%d“&y1）;
		x1--;
		y1--;
		p->ivex=x1;
		p->jvex=y1;
		p->ilink=G.g[x1].firstedge;//将表结点插入到邻接多重表中
		G.g[x1].firstedge=p;
		p->jlink=G.g[y1].firstedge;
		G.g[y1].firstedge=p;
	}
	return OK;
}
//深度遍历并给出序列
Status DFSTraverse（AMLGraph &Gint yint visited[]）
{
    PEBox w;
    printf（“%s  “G.g[y].city）;
    visited[y]=1;//标记为已遍历
    w=G.g[y].firstedge;//指向该位置下的第一个表结点
	while（w）{
		if（w->ivex==y）{//查找相应数据的位置
			if（visited[w->jvex]==0）{//判断是否遍历过
			DFSTraverse（Gw->jvexvisited）;//未被遍历过则深度优先遍历该结点
			}
			w=w->ilink;//指针后移
		}
		else{
			if（visited[w->ivex]==0）{//判断是否遍历过
			DFSTraverse（Gw->ivexvisited）;//未被遍历过则深度优先遍历该结点
			}
			w=w->jlink;//指针后移
			}
    }
    return OK;
}
//查询a在邻接多重表中的位置
Status Locate（AMLGraph Gchar a[]）
{
	int i;
	for（i=0;i		if（strcmp（G.g[i].citya）==0）
            return i;
	}
	return ERROR;
}
//广度遍历并给出序列

void BFSTraverse（AMLGraph G）
{
	linkQueue Q;
	int ab;
	int visi[MAX_VERTEX_NUM];//标志数组
	char y[20];
	for（a=0;a		visi[a]=0;
	InitQueue（Q）;//创建队列
	printf（“please input the starting point：“）;
	scanf（“%s“&y）;
	a=Locate（Gy）;//查找y在邻接多重表的位置
	visi[a]=1;//标记为已遍历
	EnQueue（Qa）;//进队列
	while（Q.front!=Q.rear）//队不为空则进行循环
    {
        DeQueue（Qa）;//队头出队列
        Print（GG.g[a].city）;
	    for（b=FirstAdjVex（GG.g[a].city）;b>=0;b=NextAdjVex（GG.g[a].cityG.g[b].city））
        {
            if（visi[b]==0）
            {
                visi[b]=1;
                EnQueue（Qb）;
            }
        }
    }
}
//深度遍历并给出生成树
Status DFSTree（AMLGraph &Gint yint visited[]int p）
{
    PEBox w;
    printf（“<%s%s>\t“G.g[p].cityG.g[y].city）;
    visited[y]=1;//标记为已遍历
    w=G.g[y].firstedge;//指向该位置下的第一个表结点
	while（w）
	{
		if（w->ivex==y）//查找相应数据在表结点中的位置
        {
			if（visited[w->jvex]==0）//判断是否遍历过
			{
			    DFSTree（Gw->jvexvisitedy）;//对该结点深度优先遍历
			}
			w=w->ilink;//指针后移
		}
		else
		{
			if（visited[w->ivex]==0）//判断是否遍历过
			{
			    DFSTree（Gw->ivexvisitedy）;//对该结点深度优先遍历
			}
			w=w->jlink;//指针后移
        }
    }
    return OK;
}
//广度优先生成树
Status BFSTree（AMLGraph &G int s[]）
{
	linkQueue Q;
	int a;
	char y[30];
	EBox *p;
	InitQueue（Q）;
 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2019-09-10 12:15  LGraph\
     文件         158  2015-02-19 10:39  LGraph\City.txt
     文件         184  2018-01-13 11:12  LGraph\Edge.txt
     文件        1229  2018-01-12 11:46  LGraph\LGraph.cbp
     文件        5440  2018-01-17 17:46  LGraph\LGraph.cpp
     文件         356  2019-01-14 16:44  LGraph\LGraph.depend
     文件        1219  2018-01-18 10:19  LGraph\LGraph.h
     文件         505  2019-01-17 10:48  LGraph\LGraph.layout
     文件         544  2018-01-12 11:40  LGraph\Queue.cpp
     文件         517  2018-01-12 11:40  LGraph\Queue.h
     目录           0  2019-09-10 12:15  LGraph\bin\
     目录           0  2019-09-10 12:15  LGraph\bin\Debug\
     文件      978310  2019-01-14 16:44  LGraph\bin\Debug\LGraph.exe
     文件        2555  2018-01-17 16:57  LGraph\main.cpp
     目录           0  2019-09-10 12:15  LGraph\obj\
     目录           0  2019-09-10 12:15  LGraph\obj\Debug\
     文件       10158  2019-01-14 16:44  LGraph\obj\Debug\LGraph.o
     文件        3214  2019-01-14 16:44  LGraph\obj\Debug\Queue.o
     文件       13379  2019-01-14 16:44  LGraph\obj\Debug\main.o