文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 连通无向图的遍历-算法简便
侵权投诉

连通无向图的遍历-算法简便

利用连通无向图的优势,设计了该算法、极其简便

#include<iostream>

using namespace std;

#define MAX_VERTEX_NUM 30 //设定结点数不超过30
bool visit[MAX_VERTEX_NUM];
int judge=0;
typedef struct ArcNode{
int adjvex;
struct ArcNode* nextarc;
}ArcNode;

typedef struct VNode{
int data;
int number; //用于记忆某一结点所连接的其余结点的个数
ArcNode * firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;

typedef struct Queue{
int element;
Queue *next;
}Queue,*Head;

void initvisit(ALGraph *g){ //初始化visit的值
for(int i=0;i<g->vexnum;i++)
visit[i]=0;
}
void EnQueue(Queue *Head,int vex) //将元素压入队列
{
Queue *s;
s=(Queue*)malloc(sizeof(Queue));
s->element=vex;
s->next=NULL;
while(Head->next!=NULL)
{
Head=Head->next;
}
Head->next=s;
}
int isEmpty(Queue *Head){ //判断队列是否为空
if(Head->next==NULL)
return 0;
return 1;
}
int DeQueue(Queue *Head) //将元素从队列中取出,并返回该值
{
Queue *p;
int e;
p=(Queue*)malloc(sizeof(Queue));
if(isEmpty(Head)){
p=Head->next;
e=Head->next->element; //用一个变量来保存队列头(top)的元素
Head->next=p->next;
Head=p;
return e; //返回top值
}
}

//建立图
void CreatGraph(ALGraph *g){
int i,j;
char b;
ArcNode *s;
cout<<"输入图的顶点数: "<<endl;
cin>>i;
g->vexnum=i;
cout<<"输入图的边数: "<<endl;
cin>>j;
g->arcnum=j;
cout<<"顶点的编号分别为1。。。n"<<endl;
for(int k=0;k<g->vexnum;k++){ //首先对于各结点进行初始化
g->vertices[k].data=k+1;
g->vertices[k].number=0;
g->vertices[k].firstarc=NULL;
cout<<"顶点"<<k+1<<"的编号为:"<<k+1<<endl;
}

for(int k=0;k<g->arcnum;k++) // 建立图,边的输入方式为v1,v2
{
cout<<"输入第"<<k+1<<"条边的两个顶点,输入方式为:v1,v2"<<endl; //由于图为无向连通图,所以当一个结点与某一结点连接时
cin>>i>>b>>j;
s=(ArcNode*)malloc(sizeof(ArcNode)); //某一节点也应该同时建立与该结点的联系,同时结点的number值也同时加一
s->adjvex=j;
s->nextarc=g->vertices[i-1].firstarc;
g->vertices[i-1].firstarc=s;
g->vertices[i-1].number++;
s=(ArcNode*)malloc(sizeof(ArcNode));
s->adjvex=i;
s->nextarc=g->vertices[j-1].firstarc;
g->vertices[j-1].firstarc=s;
g->vertices[j-1].number++;
}
}

void DFS(ALGraph *g,int v){
visit[v-1]=true;
cout<<g->vertices[v-1].data<<" ";
ArcNode *p;
p=(ArcNode*)malloc(sizeof(ArcNode));
p=g->vertices[v-1].firstarc;
int w;
for(;p;p=p->nextarc){
w=p->adjvex;
if(visit[w-1]==false)
DFS(g,w);
}
}
void BFS(ALGraph *g,int v,Queue *Head)
{
int recept; //用来接收

第1页

你可能喜欢

热门文档

相关文档

  • 连通无向图的遍历

    连通无向图的遍历_工学_高等教育_教育专区。以邻接多重表为存储结构,实现连通... 搞笑图片乐翻人 cs3简单制作动态搞笑图片80份文档 家装材料选购攻略...

  • 19图的遍历图的连通性问题

    熟练掌握图的两种搜索路径的遍历。要掌握遍历的 逻辑定义,深度优先搜索和广度优先搜索的算法。 ? 掌握图的算法,学会手工计算:求无向图的连通分 量的方法;求最小...

  • 掌握图的两种遍历算法深度优先搜索和广度优先搜索算

    Graph).图的遍历算法是求解图 的连通性问题,拓扑排序和求关键路径等算法的基础...5.5.3 求图的连通分量 图的连通分量求图的连通分量是图的遍历的一种简单...

  • 无向图的遍历可视化

    7页 免费 连通无向图的遍历-算法简... 2页 1下载券喜欢此文档的还喜欢 ... 用java语言编写的无向图...

  • 图的遍历和连通性

    // DFS 4 对于无向图,这个算法可以遍历到 遍历到v 对于无向图,这个算法可以遍历到v顶点所在的连通 分量中的所有顶点,而与v顶点不在一个连通分量中的 分量...

  • 实验四 图的遍历算法

    (即从源点可达的所有顶点)都已被访问过,若图 G 是 连通图, 则遍历过程结束...优先搜索)是最简便的图的搜索算法之一,这 一算法也是很多重要的图的算法的原型...

  • 图与遍历算法 习题参考答案

    图的建立及遍历算法的实... 2页 2下载券 图的优先遍历算法(C语言... 3...3. G 是具有 n 个顶点和 m 条边的无向图, 设 如果 G 是连通的, 而且...

  • 第三章 图与遍历算法

    第三章 图与遍历算法§1 图的基本概念和术语 无向图(undirected graph) ...边连接的简单图,这样的图的边数为 n(n-1)/2.以下是 1-4 阶的完全图: ...

  • 数据结构与算法第6章图答案

    H 树状 G 环状 ⑶含 n 个顶点的连通图中的任意一条简单路径,其长度不可能...A 求关键路径的方法 C 广度优先遍历算法 【解答】D 【分析】当有向图中无...

  • 算法设计与分析 第三章 图与遍历算法

    第三章 图与遍历算法§1 图的基本概念和术语 无向图(undirected graph) ...边连接的简单图,这样的图的边数为 n(n-1)/2.以下是 1-4 阶的完全图: ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email