数据结构：图遍历的演示

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 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[i][j]=A[i][j]; //将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[200];
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[i]=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[i]=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[MAXV]; //定义全局数组 visited
int A[MAXV][MAXV]= // 输入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[MAXV][MAXV]; //图中的边
int n,e; //图中顶点数n 和边数E
Vertex vexs[MAXV];
}MGraph; //完整的图类型
typedef struct Anode
{
int adjvex;
struct Anode *nextarc;
}ArcNode; //边节点类型
typedef struct Vnode
{
Vertex Vdata; //顶点的数据信息
ArcNode *firstarc; //指向第一条边对应的边节点
}VNode;
typedef VNode AdjList[MAXV]; //定义一个邻接表类型的数组
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[i].firstarc=NULL;
for(i=0;i<g.n;i++)
for(j=g.n-1;j>=0;j--)
if(g.edges[i][j]!=0)
{
p=(ArcNode *)malloc(sizeof (ArcNode));
p->adjvex =j;
p->nextarc=G->adjlist[i].firstarc ;
G->adjlist[i].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[i].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[MAXV];
int top=-1,w,i;
for(i=0;i<G->n;i++)
visited[i]=0;
printf("%3d",v);
visited[v]=1;
top++;
St[top]=G->adjlist[v].firstarc;
while(top>-1)
{
p=St[top];
top--;
while(p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
{
printf("%3d",w);
visited[w]=1;
top++;
St[top]=G->adjlist[w].firstarc;
}
p=p->nextarc ;
}
}
printf("\n");
}
void BFS(ALGraph *G,int v) //遍历BFS算法
{
ArcNode *p;
int queue[MAXV],front=0,rear=0;
int w,i;
for(i=0;i<G->n;i++)
visited[i]=0;
printf("%2d",v);
visited[v]=1;
rear=(rear+1)%MAXV;
queue[rear]=v;
while(front!=rear)
{
front=(front+1)%MAXV;
w=queue[front];
p=G->adjlist[w].firstarc;
while(p!=NULL)
{
if(visited[p->adjvex]==0)
{
printf("%2d ",p->adjvex);
visited[p->adjvex]=1;
rear=(rear+1)%MAXV;
queue[rear]=p->adjvex;
}
p=p->nextarc;
}
}
printf("\n");
}
void BFS1(ALGraph *G,int v) //深度优先生成树
{
ArcNode *p;
int queue[MAXV],front=0,rear=0;
int w,i;
for(i=0;i<G->n;i++)
visited[i]=0;
visited[v]=1;
rear=(rear+1)%MAXV;
queue[rear]=v;
while(front!=rear)
{
front=(front+1)%MAXV;
w=queue[front];
p=G->adjlist[w].firstarc;
while(p!=NULL)
{
if(visited[p->adjvex]==0)
{
printf("<%d,%d>",w,p->adjvex);
visited[p->adjvex]=1;
rear=(rear+1)%MAXV;
queue[rear]=p->adjvex;
}
p=p->nextarc;
}
}
printf("\n");
}
void DFS1(ALGraph *G,int v) //广度优先生成树
{
ArcNode *p;
visited[v]=1;
p=G->adjlist[v].firstarc;
while(p!=NULL)
{
if(visited[p->adjvex]==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[v] = 1;
int index;
deep++;
for ( index = 0; index < deep; ++index){
printf("***");
}
printf("%3d", v);
printf("\n");
p = G->adjlist[v].firstarc;
while (p != NULL)
{
if (visited[p->adjvex] == 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[MAXV], front = 0, rear = 0;
int w, i;
for (i = 0; i<G->n; i++)
visited[i] = 0;
printf("***%3d", v);
printf("\n");
visited[v] = 1;
rear = (rear + 1) % MAXV;
queue[rear] = v;
deepthTemp = 0;
while (front != rear)
{
front = (front + 1) % MAXV;
if (front > deepthTemp){
deepthTemp = rear;
deepth++;
}
w = queue[front];
p = G->adjlist[w].firstarc;
while (p != NULL)
{
if (visited[p->adjvex] == 0)
{
for (int index = 0; index < deepth; ++index){
printf("******");
}
printf("%2d ", p->adjvex);
printf("\n");
visited[p->adjvex] = 1;
rear = (rear + 1) % MAXV;
queue[rear] = p->adjvex;
}
p = p->nextarc;
}
}
printf("\n");
}

复制代码

以上是使用邻接矩阵转换成邻接表, 另外有手动输入的邻接表函数如下:

结构体类型:
#include<stdio.h>
#include<malloc.h>
#define MAXV 6
int visited[MAXV];
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[MAXV]; //定义一个邻接表类型的数组
typedef struct
{
int n,e;
}Graph; //图信息
typedef struct
{
AdjList adjlist; //邻接表
int n,e; //图中顶点数n 和边数E
}ALGraph; //完整的图邻接表类型
函数类型:
void Creatgraph (VNode adjlist[],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[i].Vdata=i;
adjlist[i].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[begin].firstarc;
adjlist[begin].firstarc=p;
}
}
void DispAdj(VNode adjlist[],Graph &graph) //输出邻接表
{
int i;
ArcNode *p;
for(i=0;i<graph.n;i++)
{
p=adjlist[i].firstarc ;
printf(" %d",adjlist[i].Vdata);
while(p)
{
printf("->");
printf(" %d",adjlist[p->adjvex].Vdata);
p=p->nextarc ;
}
printf("\n");
}
}
void BFS(VNode adjlist[],Graph &graph,int v) //广度优先遍历
{
ArcNode *p;
int queue[MAXV],front=0,rear=0;
int w,i;
for(i=0;i<graph.n;i++)
visited[i]=0;
printf("%2d",v);
visited[v]=1;
rear=(rear+1)%MAXV;
queue[rear]=v;
while(front!=rear)
{
front=(front+1)%MAXV;
w=queue[front];
p=adjlist[w].firstarc;
while(p!=NULL)
{
if(visited[p->adjvex]==0)
{
printf("%2d",p->adjvex);
visited[p->adjvex]=1;
rear=(rear+1)%MAXV;
queue[rear]=p->adjvex;
}
p=p->nextarc;
}
}
printf("\n");
}
void DFS(VNode adjlist[],Graph &graph,int v) //非递归深度优先遍历
{
ArcNode *p;
ArcNode *St[MAXV];
int top=-1,w,i;
for(i=0;i<graph.n;i++)
visited[i]=0;
printf("%2d",v);
visited[v]=1;
top++;
St[top]=adjlist[v].firstarc;
while(top>-1)
{
p=St[top];
top--;
while(p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
{
printf("%2d",w);
visited[w]=1;
top++;
St[top]=adjlist[w].firstarc;
}
p=p->nextarc ;
}
}
printf("\n");
}
主函数:
void main()
{
int i,j,t,c,n,v,e;
VNode adjlist[MAXV];
Graph graph;
FILE *fp;
char str[200];
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:

账号		自动登录	找回密码
密码			立即注册

[技术交流] 数据结构：图遍历的演示

马上注册，结交更多好友，享用更多功能^_^

评分

评分

评分

浏览过的版块