liuxinyancom 2013-12-04 09:23
浏览 848

哪位好心人帮我看下代码吧,深度遍历搜索图的,有点长,麻烦看下吧

//深度遍历搜索图
#include
#include
#define MAX_VERTEX_NUM 3
typedef enum {DG,DN,UDG,UDN} GraphKind;//图的类型
typedef int OtherInfo; //弧的信息,如权
typedef char VertexData;//图结点的内容为char
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
OtherInfo info;
}ArcNode;//弧结点
typedef struct VertexNode
{
VertexData data;
ArcNode *firstarc;

}VertexNode;//表头结点
typedef struct
{
VertexNode vertex[MAX_VERTEX_NUM];
int arcnum;
int vexnum;
GraphKind kind;
}AdjList;//邻接表(图)

int visited[MAX_VERTEX_NUM];//全局变量:访问标志数组
void CreateAdjList(AdjList *G);
int Locate(AdjList *G, char v);
void TraverseGraph(AdjList *G);
void DepthFirstSearch(AdjList*G,int v0);

void CreateAdjList(AdjList *G)//建立邻接表
{

char v1;char v2;//v1,v2为一条弧上的两个端点,一个为起始端点,一个为尾端点
ArcNode *s;
int i,j,k;
char ch;
printf(" 输入图结点:");
for(i=0;i<G->vexnum;i++)//表头结点初始化
{


    scanf("%c",&ch);
    G->vertex[i].data=ch;
    G->vertex[i].firstarc=NULL;
    fflush(stdin);


}


for(k=0;k<G->arcnum;k++)
{
    printf("输入连接弧端点值,如“A,B”");
    scanf("%c,%c",&v1 ,&v2 );
    //v1=getchar();
    //v2=getchar();

    i=Locate(G,v1);printf("%d",i);//定位v1在表头结点里的数组下标,即第几个
    j=Locate(G,v2);printf("#");
    s=(ArcNode*)malloc(sizeof(ArcNode));
    s->adjvex=j;
    s->nextarc=G->vertex[i].firstarc;
    G->vertex[i].firstarc=s;//头结点插入法
    s=(ArcNode*)malloc(sizeof(ArcNode));
    s->adjvex=i;
    s->nextarc=G->vertex[j].firstarc;
    G->vertex[j].firstarc=s;
}

}
//定位,查找v1,v2的相应数组下标
int Locate(AdjList *G,char v)
{
for(int i=0;ivexnum;i++)

    if(G->vertex[i].data==v)
        return i;
    else
        return 0;

}
//深度优先搜索邻接表

void TraverseGraph(AdjList *G)
{
int vi=0;//没访问过的置0,访问过的置1;
for(vi=0;vivexnum;vi++)
visited[vi]=0;
for(vi=0;vivexnum;vi++)
if(visited[vi]==0)
DepthFirstSearch(G,vi);
}
void DepthFirstSearch(AdjList*G,int v0)//DFS
{
ArcNode*p;
printf("%c",v0);
visited[v0]=1;//访问过后标志数组置为1;
p=G->vertex[v0].firstarc;
while(p!=NULL)
{
if(visited[p->adjvex]==0)
DepthFirstSearch(G,p->adjvex);
p=p->nextarc;
}
}

int main()
{
AdjList * G;

G=(AdjList*)malloc(sizeof(AdjList));
printf("输入图结点数目,弧数目,如“4,3”\n");
scanf("%d,%d",&G->vexnum,&G->arcnum );

CreateAdjList(G);
TraverseGraph(G);
free(G);
return 0;

}

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 完成下列问题完成下列问题
    • ¥15 C#算法问题, 不知道怎么处理这个数据的转换
    • ¥15 YoloV5 第三方库的版本对照问题
    • ¥15 请完成下列相关问题!
    • ¥15 drone 推送镜像时候 purge: true 推送完毕后没有删除对应的镜像,手动拷贝到服务器执行结果正确在样才能让指令自动执行成功删除对应镜像,如何解决?
    • ¥15 求daily translation(DT)偏差订正方法的代码
    • ¥15 js调用html页面需要隐藏某个按钮
    • ¥15 ads仿真结果在圆图上是怎么读数的
    • ¥20 Cotex M3的调试和程序执行方式是什么样的?
    • ¥20 java项目连接sqlserver时报ssl相关错误