Question

图的建立与深度遍历，邻接表方式，c语言。 具体：有6个点输入，输入关系，遍历。

最简单的方式实现即可

Answer 1

#include <stdio.h>
#include <stdlib.h>

#define INFINITY 65535
#define MAX_VERTEX 20 //最大顶点数

typedef char VertexType; //顶点数据类型
typedef int ArcType; //弧(边)数据类型

typedef struct ArcNode //弧(边)结点的结构
{
int adjvex; //该弧(边)所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧(边)的指针
ArcType arc; //该弧(边)相关信息,如权值
}ArcNode;

typedef struct VexNode //顶点结点的结构
{
VertexType data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的弧(边)的指针
}VexNode;

typedef struct //图的邻接表结构定义
{
VexNode vexs[MAX_VERTEX]; //存放顶点的数组 */
int vexnum, arcnum; //图的当前顶点数和弧(边)数 */
int kind; //图的类型 0-无向图 1-有向图 2-无向网 3-有向网
}ALGraph;

int LocateVex(ALGraph G,VertexType v) //根据顶点值找到数组下标
{
for(int i=0;i<G.vexnum;i++)
if(G.vexs[i].data==v)
return i;
return -1;
}
int CreateGraph(ALGraph &G) //邻接表建立图
{
int i,j,w;
VertexType v1,v2;
ArcNode *p;
printf("输入图的类型（0-无向图 1-有向图 2-无向网 3-有向网）\n");
scanf("%d",&G.kind);
printf("输入图的顶点数\n");
scanf("%d",&G.vexnum);
printf("输入图的弧(边)数\n");
scanf("%d",&G.arcnum);
getchar();
printf("输入顶点:\n");
for(i=0;i<G.vexnum;i++)
{
scanf("%c",&G.vexs[i].data);
G.vexs[i].firstarc = NULL; //首先初始化为NULL
}

for(int k=0;k<G.arcnum;++k)
{ getchar();
printf("输入边依附的两个顶点:\n"); // 输入一条边依附的起点序号和终点序号
scanf("%c%c",&v1,&v2);
if(G.kind==2||G.kind==3)
{
printf("输入此边的权值:\n");
scanf("%d",&w);
}
else
w=1;

i=LocateVex(G,v1);
j=LocateVex(G,v2);

p=(struct ArcNode *)malloc(sizeof(struct ArcNode));
p->adjvex =j ; // 保存该弧(边)所指向的顶点位置
p->nextarc = G.vexs[i].firstarc;
p->arc = w;
G.vexs[i].firstarc = p;
if(G.kind==0||G.kind==2) //无向图，无向网对称建立
{
p=(struct ArcNode *)malloc(sizeof(struct ArcNode));
p->adjvex =i; // 保存该弧(边)所指向的顶点位置
p->arc = w;
p->nextarc = G.vexs[j].firstarc;
G.vexs[j].firstarc = p;
}
}
return 1;
}

int PrintGraph(ALGraph G) //打印图每个结点的单链表
{
int i;
ArcNode *p;
printf("打印邻接表:\n");
for(i=0; i<G.vexnum; i++)
{
p=G.vexs[i].firstarc;
while(p!=NULL)
{
printf("%c->%c(%d) ",G.vexs[i].data,G.vexs[p->adjvex].data,p->arc);
p=p->nextarc;
}
printf("\n");
}
return 1;
}

bool visited[MAX_VERTEX]; //访问标志数组

//深度优先遍历
void DFS(ALGraph G,int k)
{
ArcNode *p;
visited[k]=true;
printf("%c ",G.vexs[k].data); //访问第k个顶点
p=G.vexs[k].firstarc;
while(p!=NULL)
{
if(!visited[p->adjvex])
DFS(G,p->adjvex); //对p的尚未访问的邻接顶点p->adjvex递归调用DFS
p=p->nextarc;
}
}

//---------------------------------------------------
//队列定义
# define MAXSIZE 100
typedef int QDataType ;
typedef struct seqqueue
{
QDataType queue[MAXSIZE];
int front; //队头指针
int rear; //队尾指针
}SeqQueue;

//初始化队列
void InitQueue(SeqQueue *q)
{ q->front=q->rear=0;}

//判断队列空
int EmptyQueue(SeqQueue *q)
{ if(q->front==q->rear)
return 1;
else
return 0;
}

//进队列
int EnQueue (SeqQueue *q, QDataType x)
{ if ((q->rear+1)%MAXSIZE == q->front)
{ printf("overflow!\n");
return 0;
}
else
{q->queue[q->rear]=x;
q->rear=(q->rear+1)%MAXSIZE;
return 1;
}
}

//出队列
int DlQueue(SeqQueue *q , QDataType *qx )
{ if (q->rear==q->front)
{
printf("empty!\n");
return 0;
}
else
{ *qx= q->queue[q->front];
q->front =(q->front+1)%MAXSIZE;
return 1;
}
}

//广度优先遍历
void BFS(ALGraph G,int k)
{

ArcNode *p;
SeqQueue Q; //辅助队列Q
InitQueue(&Q);
visited[k]=true;
printf("%c ",G.vexs[k].data);
EnQueue(&Q,k); //k入列
while(!EmptyQueue(&Q))
{
DlQueue(&Q,&k); //队头元素出列并置为k
p=G.vexs[k].firstarc;
while(p!=NULL)
{
if(!visited[p->adjvex])
{
visited[p->adjvex]=true;
printf("%c ",G.vexs[p->adjvex].data);
EnQueue(&Q,p->adjvex);
}
p=p->nextarc;
}

}
}

void main()
{
int i;
ALGraph G;

CreateGraph(G);
PrintGraph(G);

printf("请输入遍历起始点:\n");
VertexType v;
getchar();
scanf("%c",&v);
int k=LocateVex(G,v);

printf("深度优先遍历序列: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;

DFS(G,k);
for(i=0;i<G.vexnum;i++)
if(!visited[i])
DFS(G,i);
printf("\n");

printf("广度优先遍历序列: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
BFS(G,k);
for(i=0;i<G.vexnum;i++)
if(!visited[i])
BFS(G,i);
printf("\n");
}