数据结构：图遍历的演示,C\C++交流,编程语言专区,鱼C论坛

SonOmiga 发表于 2015-12-13 12:09:51

数据结构：图遍历的演示

本帖最后由 SonOmiga 于 2015-12-16 19:11 编辑

这是犹豫老师布置的课题作业,
分为两个文件一个为c.cpp 一个为头文件类型graph.h
c文件如下:#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<windows.h>
#include"graph.h"
void main()
{
int i,j,c,n,e,t,x;
MGraph g; //定义图g
ALGraph *G; //定义邻接表G
g.n=21;
g.e=21;
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
g.edges=A; //将A[][]邻接矩阵转换成图g的边信息
printf("\n");
printf("\n");
printf("             图遍历的演示:\n");
printf("    正在从文件中读取 ");
for(i=0;i<3;i++)
{
::Sleep(600);
printf(".");
}
printf("\n");
printf(" 请稍候!\n");
for(i=0;i<3;i++)
{
::Sleep(600);
}
printf("    从文件读取信息完毕!\n");
printf("\n");
MatToList(g,G);          //将邻接矩阵转换成邻接表
{
FILE *fp;
char str;
if((fp=fopen("D:\\C.txt","rt"))==NULL) //打开C文件(C中存放图的信息)
{
printf("\n Cannot open file strike any key exit!");
}
while(fgets(str,200,fp)!=NULL)    //从文件中读取字符串
{
printf("%s",str);
printf("\n");}

}
printf("\n");
printf("\n"); printf("你想通过哪个顶点遍历DFS算法?");
               scanf("%d",&t);
printf("从顶点%d开始实现DFS算法:\n",t);
DFS(G,t);
printf("\n");
system("pause");
printf("\n你想通过哪个顶点遍历BFS算法?");
scanf("%2d",&t);
printf("从顶点%d开始实现BFS算法:\n",t);
BFS(G,t);
system("pause");
for(i=0;i<G->n;i++)
visited=0;

printf("\n你想通过哪个顶点输出深度优先生成树?");
scanf("%2d",&t);
DFS1(G,t);
   printf("\n");
system("pause");
printf("\n你想通过哪个顶点输出广度优先生成树?");
scanf("%2d",&t);
BFS1(G,t);
printf("\n");
   for(i=0;i<G->n;i++)
visited=0;
system("pause");
printf("你想通过哪个顶点凹入表打印树?");
scanf("%d",&t);
printf("从顶点%d开始实现深度优先生凹入表打印树:\n",t);
DFSTest(G,t);
printf("\n");
system("pause");
printf("\n你想通过哪个顶点凹入表打印树?");
scanf("%2d",&t);
printf("从顶点%d开始实现广度优先生凹入表打印树:\n",t);
BFSTest(G,t);
system("pause");

}
graph.h代码如下:#include<stdio.h>
#include<malloc.h>
#define MAXV 21
int visited; //定义全局数组 visited
int A= // 输入A[ ][ ]的邻接矩阵

{
{0,1,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0},
{1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0}
};

结构体类型:

typedef struct
{
int no;
}Vertex; //顶点类型
typedef struct
{
int edges; //图中的边
int n,e; //图中顶点数n 和边数E
Vertex vexs;
}MGraph; //完整的图类型
typedef struct Anode
{
int adjvex;
struct Anode *nextarc;
}ArcNode; //边节点类型
typedef struct Vnode
{
Vertex Vdata; //顶点的数据信息
ArcNode *firstarc; //指向第一条边对应的边节点
}VNode;
typedef VNode AdjList; //定义一个邻接表类型的数组
typedef struct
{
AdjList adjlist; //邻接表
int n,e; //图中顶点数n 和边数E
}ALGraph; //完整的图邻接表类型

函数类型:
void MatToList(MGraph g,ALGraph *&G) // 邻接矩阵转换邻接表
{
int i,j;
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
for(i=0;i<g.n;i++)
G->adjlist.firstarc=NULL;
for(i=0;i<g.n;i++)
for(j=g.n-1;j>=0;j--)
if(g.edges!=0)
{
p=(ArcNode *)malloc(sizeof (ArcNode));
p->adjvex =j;
p->nextarc=G->adjlist.firstarc ;
G->adjlist.firstarc =p;
}
G->n=g.n;G->e=g.e;
}

void DispAdj(ALGraph *G) //输出邻接表
{
int i;
ArcNode *p;
for(i=0;i<G->n;i++)
{
p=G->adjlist.firstarc ;
printf("%3d->",i);
while(p!=NULL)
{
printf("%3d",p->adjvex);
p=p->nextarc ;
}
printf("\n");
}
}

void DFS2(ALGraph *G,int v) //非递归遍历BFS算法
{
ArcNode *p;
ArcNode *St;
int top=-1,w,i;
for(i=0;i<G->n;i++)
visited=0;
printf("%3d",v);
visited=1;
top++;
St=G->adjlist.firstarc;
while(top>-1)
{
p=St;
top--;
while(p!=NULL)
{
w=p->adjvex;
if(visited==0)
{
printf("%3d",w);
visited=1;
top++;
St=G->adjlist.firstarc;

}
p=p->nextarc ;

}
}
printf("\n");
}

void BFS(ALGraph *G,int v) //遍历BFS算法
{
ArcNode *p;
int queue,front=0,rear=0;
int w,i;
for(i=0;i<G->n;i++)
visited=0;
printf("%2d",v);
visited=1;
rear=(rear+1)%MAXV;
queue=v;
while(front!=rear)
{
front=(front+1)%MAXV;
w=queue;
p=G->adjlist.firstarc;
while(p!=NULL)
{
if(visited==0)
{
printf("%2d ",p->adjvex);
visited=1;
rear=(rear+1)%MAXV;
queue=p->adjvex;
}
p=p->nextarc;
}
}
printf("\n");
}
void BFS1(ALGraph *G,int v) //深度优先生成树
{
ArcNode *p;
int queue,front=0,rear=0;
int w,i;
for(i=0;i<G->n;i++)
visited=0;
visited=1;
rear=(rear+1)%MAXV;
queue=v;
while(front!=rear)
{
front=(front+1)%MAXV;
w=queue;
p=G->adjlist.firstarc;
while(p!=NULL)
{
if(visited==0)
{
printf("<%d,%d>",w,p->adjvex);
visited=1;
rear=(rear+1)%MAXV;
queue=p->adjvex;
}
p=p->nextarc;
}
}
printf("\n");
}
void DFS1(ALGraph *G,int v)    //广度优先生成树
{
ArcNode *p;
visited=1;
p=G->adjlist.firstarc;
while(p!=NULL)
{
if(visited==0)
{
printf("<%d,%d>",v,p->adjvex);
DFS1(G,p->adjvex);
}
p=p->nextarc ;
}
}

int deep = 0;    //定义深度为0
void DFSTest(ALGraph *G, int v) //凹入法输出广度优先生成树
{
ArcNode *p;
visited = 1;
int index;
deep++;
for ( index = 0; index < deep; ++index){
   printf("***");
}
printf("%3d", v);
printf("\n");
p = G->adjlist.firstarc;
while (p != NULL)
{
   if (visited == 0)
         DFSTest(G, p->adjvex);
   p = p->nextarc;
}
deep--;
}

void BFSTest(ALGraph *G, int v) //凹入法输出深度优先生成树
{
int deepth=0;
int deepthTemp = 0;
ArcNode *p;
int queue, front = 0, rear = 0;
int w, i;
for (i = 0; i<G->n; i++)
   visited = 0;
printf("***%3d", v);
printf("\n");
visited = 1;
rear = (rear + 1) % MAXV;
queue = v;
deepthTemp = 0;
while (front != rear)
{
   front = (front + 1) % MAXV;
   if (front > deepthTemp){
         deepthTemp = rear;
         deepth++;
   }
   w = queue;
   p = G->adjlist.firstarc;
   while (p != NULL)
   {
         if (visited == 0)
         {
            for (int index = 0; index < deepth; ++index){
               printf("******");
            }
            printf("%2d ", p->adjvex);
            printf("\n");
            visited = 1;
            rear = (rear + 1) % MAXV;
            queue = p->adjvex;
         }
         p = p->nextarc;
   }
}
printf("\n");
}
以上是使用邻接矩阵转换成邻接表, 另外有手动输入的邻接表函数如下:
结构体类型:
#include<stdio.h>
#include<malloc.h>
#define MAXV 6
int visited;
typedef struct
{
int no;
}Vertex; //顶点信息
typedef struct Anode
{
int adjvex;
struct Anode *nextarc;
int info;

}ArcNode; //边节点信息
typedef struct Vnode
{
int Vdata; //顶点的数据信息
ArcNode *firstarc; //指向第一条边对应的边节点

}VNode;

typedef VNode AdjList; //定义一个邻接表类型的数组
typedef struct
{
int n,e;
}Graph; //图信息
typedef struct
{
AdjList adjlist; //邻接表
int n,e; //图中顶点数n 和边数E
}ALGraph; //完整的图邻接表类型

函数类型:

void Creatgraph (VNodeadjlist[],Graph &graph ) //手动生成邻接矩阵
{
int i,j,n,e,begin,end;
ArcNode *p; // 定义边节点p
printf("请输入顶点数n=");
scanf("%d",&n);
printf("请输入边数e=");
scanf("%d",&e);
graph.n=n;
graph.e=e;
for(i=0;i<n;i++)
{
adjlist.Vdata=i;
adjlist.firstarc=NULL;
}
for(j=0;j<2*e;j++)
{
printf("\n请输入第%d条边的起始点的序号\n",j);
printf(" 起点编号:");
scanf("%d",&begin);
printf(" 终点编号:");
scanf("%d",&end);
p=(ArcNode*)malloc(sizeof(ArcNode*));
p->adjvex=end;
p->nextarc=NULL;
p->nextarc=adjlist.firstarc;
adjlist.firstarc=p;

}
}

void DispAdj(VNode adjlist[],Graph &graph) //输出邻接表
{
int i;
ArcNode *p;
for(i=0;i<graph.n;i++)
{
p=adjlist.firstarc ;
printf(" %d",adjlist.Vdata);
while(p)
{
printf("->");
printf("%d",adjlist.Vdata);
p=p->nextarc ;
}
printf("\n");
}

}
void BFS(VNodeadjlist[],Graph &graph,int v) //广度优先遍历
{
ArcNode *p;
int queue,front=0,rear=0;
int w,i;

for(i=0;i<graph.n;i++)
visited=0;
printf("%2d",v);
visited=1;
rear=(rear+1)%MAXV;
queue=v;
while(front!=rear)
{
front=(front+1)%MAXV;
w=queue;
p=adjlist.firstarc;
while(p!=NULL)
{
if(visited==0)
{
printf("%2d",p->adjvex);
visited=1;
rear=(rear+1)%MAXV;
queue=p->adjvex;
}
p=p->nextarc;
}
}
printf("\n");
}

void DFS(VNodeadjlist[],Graph &graph,int v) //非递归深度优先遍历
{
ArcNode *p;
ArcNode *St;
int top=-1,w,i;
for(i=0;i<graph.n;i++)
visited=0;
printf("%2d",v);
visited=1;
top++;
St=adjlist.firstarc;
while(top>-1)
{
p=St;
top--;
while(p!=NULL)
{
w=p->adjvex;
if(visited==0)
{
printf("%2d",w);
visited=1;
top++;
St=adjlist.firstarc;

}
p=p->nextarc ;

}
}
printf("\n");
}

主函数:
void main()
{
int i,j,t,c,n,v,e;
VNode adjlist;
Graph graph;
FILE *fp;
char str;
ArcNode *P;
ALGraph *G;
printf("\n");
printf("\n");
printf("             图遍历的演示:\n");
printf("    正在从文件中读取... ");
printf("\n");
printf(" 请稍候!\n");
printf("    从文件读取信息完毕!\n");
if((fp=fopen("D:\\C.txt","rt"))==NULL) //打开C文件(C中存放图的信息)
{
printf("\n Cannot open file strike any key exit!");
}
while(fgets(str,200,fp)!=NULL)    //从文件中读取字符串
{
printf("%s",str);
printf("\n");

}
printf("\n");
printf("无向图的邻接表:\n");
Creatgraph(adjlist,graph);
DispAdj(adjlist,graph);
printf("你想通过哪个顶点遍历DFS算法?");
scanf("%d",&t);
DFS(adjlist,graph,t);

printf("\n你想通过哪个顶点遍历BFS算法?");
scanf("%2d",&t);
BFS(adjlist,graph,t);
}

(手动输入小型矩阵必须把无向图顶点的边都输入进去如 V1顶点连接V2顶点那当你输入起始编号和终点编号的时候都得输入v1 v2
和v2 v1)
若有同学有疑问,可以联系我QQ77325313,我也是学习小组布置的任务,可以互相交流.

～风介～ 发表于 2015-12-14 00:32:25

亲，可以考虑用代码格式发布代码哦~

SonOmiga 发表于 2015-12-14 12:50:15

～风介～发表于 2015-12-14 00:32
亲，可以考虑用代码格式发布代码哦~

怎么用啊

～风介～ 发表于 2015-12-14 17:32:54

SonOmiga 发表于 2015-12-14 12:50
怎么用啊

SonOmiga 发表于 2015-12-18 14:04:52

～风介～发表于 2015-12-14 17:32

好了 ! :loveliness:

页: [1]

鱼C论坛's Archiver

数据结构：图遍历的演示