Question

用邻接表表示的图的输出(PrintGraph)的算法(C语言)

详细的回答,可以运行;

Answer 1

单链表类中的输出流函数重载，输出链表
图类中再次重载输出流函数。
一次顶点表的循环，输出。
结果：<<start,dest,weight>,<。。。>>

Answer 2

DFS算法源程序
/* dfs算法 */
#include<alloc.h>
#include<stdio.h>
#include<malloc.h>
#include<conio.h>

/* 函数结果状态代码 */
#define True 1
#define False 0
#define Ok 1
#define Error 0
#define Infeasible -1
#define Overflow -2
#define Null 0
#define STACK_INIT_SIZE 100
#define Stackincrement 10

#define INFINITY 10000 /* 最大值10000 */
#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */
#define Status int
typedef char TElemType; /* 抽象元素类型为char类型 */

typedef struct ArcNode{
int adjvex; /* 该弧所指向的顶点的位置 */
int weight; /* 边的权值 */
struct ArcNode *nextarc; /* 指向下一条弧的指针 */
}ArcNode;

typedef struct VNode{
char data; /* 顶点向量 */
ArcNode *firstarc; /* 指向第一条依附该顶点的弧的指针 */
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct {
AdjList vertices;
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
}ALGraph;

struct STU{
char data;
};
typedef struct STU SElemType;

struct STACK
{
SElemType *base;
SElemType *top;
int stacksize;
};

typedef struct STACK SqStack;
int visited[MAX_VERTEX_NUM]; /* visited[MAX_VERTEX_NUM]为全局变量，记录相应顶点是否被访问过，访问过则为1，否则为0 */

Status InitStack(SqStack *S)
/* 构造一个空栈 */
{
S->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemTy pe));
if(!S->base)
exit(Overflow); /* 存储分配失败 */
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return Ok;
} /* InitStack() */

Status StackEmpty(SqStack *S)
/* 判断栈S是否为空 */
{
if(S->top==S->base) return True;
else
return False;
} /* StackEmpty() */

Status GetTop(SqStack *S,SElemType **e)
/* 若栈不空，则用e返回S的栈顶元素，并返回Ok，否则返回Error */
{
if(S->top==S->base)
return Error;
else
{
*e=S->top-1;
return Ok;
} /* else */
} /* GetTop() */

Status Push(SqStack *S,char e)
/* 插入元素e为新的栈顶元素 */
{
if(S->top-S->base>=S->stacksize) /* 栈满，追加存储空间 */
{
S->base=(SElemType*)realloc(S->base,(S->stacksize+S tackincrement)*sizeof(SElemType));
if(!S->base)exit(Overflow);
S->top=S->base+S->stacksize;
S->stacksize+=Stackincrement;
} /* if */
S->top->data=e;
++S->top;
} /* Push() */

Status Pop(SqStack *S,SElemType **e)
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回Ok；否则返回Error */
{
if(S->top==S->base)
return Error;
else
{
(*e)->data=(S->top-1)->data;
--S->top;
} /* else */
return Ok;
} /* Pop() */

void CreateGraph(ALGraph *G)
/* 生成G的存储结构-邻接表 */
{
int w,i,j,k;
char sv,tv;
ArcNode *pi,*pj;

printf("Please input the number of the vertex and arc:\n");
printf("vertex:"); /* 输入顶点数 */
scanf("%d",&G->vexnum);
printf("arc:"); /* 输入弧数 */
scanf("%d",&G->arcnum);
printf("Please input the vertex:");
getchar();

for(i=0;i<G->vexnum;i++) /* 构造顶点数组 */
{
scanf("%c",&G->vertices.data); /* 输入顶点 */
G->vertices.firstarc=Null; /* 初始化链表头指针为空 */
}

getchar();
for(k=0;k<G->arcnum;k++) /* 输入各边并构造邻接表 */
{
pi=(ArcNode*)malloc(sizeof(ArcNode));
if(!pi)
exit(Overflow); /* 分配存储失败 */
printf("Please input two points of one arc and it's weight:");
scanf("%c%c%d",&sv,&tv,&w); /* 输入一条弧的始点和终点及其权值 */

getchar();
pi->weight=w;
i=LocateVex(G,sv); /* 确定sv和tv在G中位置，即顶点在G->vertices中的序号 */
j=LocateVex(G,tv);
pi->adjvex=j; /* 对弧结点赋邻接点位置 */
pi->nextarc=G->vertices.firstarc;
G->vertices.firstarc=pi; /* 插入链表G->vertices */

pj=(ArcNode*)malloc(sizeof(ArcNode));
if(!pj)
exit(Overflow); /* 分配存储失败 */
pj->adjvex=i; /* 对弧结点赋邻接点位置 */
pj->weight=w;
pj->nextarc=G->vertices[j].firstarc;
G->vertices[j].firstarc=pj; /* 插入链表G->vertices[j] */
} /* for */
} /* CreateGraph() */

Status STraverse_Nonrecursive(ALGraph *G,int(*Visit)(TElemType))
/* 非递归遍历图G,图G采用邻接表存储方式 */
{
int record=1,i,j,k; /* record记录已经打印的顶点数目 */
SElemType *e;
SqStack *s;

s=(SqStack*)malloc(sizeof(SqStack));
if(!s)
exit(Overflow); /* 存储分配失败 */
InitStack(s);
Push(s,G->vertices[0].data); /* 将第一个顶点入栈 */
Visit(G->vertices[0].data); /* 访问第一个顶点 */
for(i=1;i<G->vexnum;i++)
visited=0; /* 对visited初始化为0 */
visited[0]=1; /* 第一个顶点已访问过 */

while(record<G->vexnum) /* 循环执行直到record=G->vexnum */
{
if(!StackEmpty(s))
{
while(GetTop(s,&e)&&e)
{
j=FirstAdjVex(G,*e);
while(j==-1&&!StackEmpty(s)&&GetTop(s,&e )&&e)
{
j=FirstAdjVex(G,*e);
Pop(s,&e);
}
if(j!=-1&&!visited[j])
{
Visit(G->vertices[j].data);
visited[j]=1;
record++;
Push(s,G->vertices[j].data); /* 向左走到尽头 */
if(record==G->vexnum) /* 如果所有顶点都已被访问过， 则退出 */
return 1;
} /* if */
} /* while */
if(!StackEmpty(s))
{
Pop(s,&e);
GetTop(s,&e);
k=FirstAdjVex(G,*e); /* 向右走一步 */
if(k!=-1&&!visited[k])
{
Visit(G->vertices[k].data);
visited[k]=1;
Push(s,G->vertices[k].data);
record++;
if(record==G->vexnum) /* 如果所有顶点都已被访问过， 则退出 */
return 1;
} /* if */
}
} /* if */
} /* while */
} /* STraverse_Nonrecursive() */

Status FirstAdjVex(ALGraph *G,char v)
/* 图G存在，v是G中的某个顶点,返回v的第一个未被访问的邻接顶点的序号，若顶点再G中没有邻接顶点，则返回-1 */
{
ArcNode *p;
int i;
for(i=0;i<G->vexnum;i++) /* 寻找v所在的邻接表中的序号 */
{
if(v==G->vertices.data)
break;
} /* for */
p=G->vertices.firstarc; /* p指向v的第一个邻接点 */
while(p)
{
if(visited[p->adjvex]) /* 如果此邻接点已被访问则p指向v的下一个邻接点 */
p=p->nextarc;
else
return p->adjvex;
} /* while */
return -1;
} /* FirstAdjVex() */

Status LocateVex(ALGraph *G,char vex)
/* 确定vex在G中的位置 */
{
int i;
for(i=0;i<G->vexnum;i++) /* 确定v1在G中位置 */
if(vex==G->vertices.data)
return i;
} /* LocateVex() */

int PrintGraph(TElemType e)
/* 输出图中的每一个结点 */
{
printf("%c ",e);
return Ok;
}

main()
{
ALGraph *G;
int i;

G=(ALGraph*)malloc(sizeof(ALGraph));
CreateGraph(G);
STraverse_Nonrecursive(G,PrintGraph);
}