Question

从键盘输入的数据创建图（图的存储结构采用邻接表）进行深度优先搜索和广度优先搜 求一条C语言编的程序

Answer 1

数据结构这个东西，你的定义不同写出来的东西也就不同了,好吧，这是我写的一个东西，写的有点仓促有点丑哈····
#define MAXSIZE 100
typedef char elemtype;

typedef struct arc
{
int index;
arc *nextarc;
}ARCNODE,*ARC;

typedef struct VER
{
elemtype data;
ARC firstarc;
}VERNODE;

typedef struct
{
VERNODE vertex[MAXSIZE];
int numVer;
int numArc;
}ADJGRAPH;

//递归实现深度优先
void dfs(ADJGRAPH *g,int pos,int *visit,void (*pf)(elemtype))
{
ARCNODE *p = g->vertex[pos].firstarc;
visit[pos] = 1;
pf(g->vertex[pos].data);
while(p)
{
if (!visit[p->index])
{
dfs(g,p->index,visit);
}
p = p->nextarc;
}
}
void dfs_traverse(ADJGRAPH *g,int pos)
{
int *visit = (int *)malloc(sizeof(int)*(g->numVer));
for (int i = 0;i<g->numVer;i++)
{
visit[i] = 0;
}
dfs(g,pos,visit);
for (int i = 0;i<g->numVer;i++)
{
if (!visit[i])
{
dfs(g,i,visit);
}
}
}

//栈实现深度优先
void dfs_traverse_inrecursion(ADJGRAPH *g,void (*pf)(elemtype))
{
ARCNODE *p;
ARCNODE *stack[MAXSIZE];//链栈更好
int visit[MAXSIZE] = {0};
int top = 0;
for (int pos = 0;pos < g->numVer;pos++)
{
if (!visit[pos])
{
p = g->vertex[pos].firstarc;
pf(g->vertex[pos].data);
visit[pos] = 1;
while (p||top)
{
while (p&&!visit[p->index])
{
pf(g->vertex[p->index].data);
visit[p->index] = 1;
stack[top++] = p;
p = g->vertex[p->index].firstarc;
}
if(top)
p = stack[--top]->nextarc;
else
p = p->nextarc;
}
}
}
}

//广度优先
void bfs_traverse(ADJGRAPH *g,void (*pf)(elemtype))
{
ARCNODE *queue[MAXSIZE];//链队列更好
ARCNODE *p;
int rear = 0,front = 0;
int visit[MAXSIZE] = {0};
for(int pos = 0;pos<g->numVer;pos++)
{
p = g->vertex[pos].firstarc;
if(!visit[pos])
{
pf(g->vertex[pos].data);
visit[pos] = 1;
}
while(p||rear != front)
{
while(p)
{
queue[front++] = p;
p = p->nextarc;
}
if(rear != front)
{
p = queue[rear++];
if(!visit[p->index])
{
pf(g->vertex[p->index].data);
visit[p->index] = 1;
}
p = g->vertex[p->index].firstarc;
}
else
p = g->vertex[p->index].firstarc;
}
}
}