#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_VER 100//最大顶点数
typedef struct edgnode{//邻接点域
int vertex;
struct edgnode *next;
}enode;
typedef struct vnode{
char data;
enode *link;
}vlist[MAX_VER];
typedef struct node2{
int v;
struct node2 *next;
}qnode;
typedef struct {
qnode *front,*rear;
}linkQueue;
int n;
int visited[MAX_VER];//用于标志顶点是否被访问过
vlist g;
linkQueue queue;
void Init(linkQueue *q)
{
q->front=q->rear=NULL;
}
void InsertQueue(linkQueue * &q,int e)
{
qnode * node;
node=(qnode*)malloc(sizeof(qnode));
node->v=e;
node->next=NULL;
if(NULL==q->front)
{
q->front=q->rear=node;
}
else
{
q->rear->next=node;
q->rear=node;
}
}
int outQueue(linkQueue * &q)
{
int e;
qnode *temp;
if(NULL==q->front)
e=NULL;
else
{
temp=q->front;
e=temp->v;
q->front=temp->next;
free(temp);
}
return e;
}
//创建无向图
void createGraphic(vlist g)
{
int e,i=1,start,end;
enode *p;
printf("请输入顶点数(n)和边数(e):\n");
scanf("%d%d",&n,&e);
while(i<=n) //初始化顶点表
{
fflush(stdin);
printf("请输入第 %d 个顶点:",i);
g[i].data=getchar();
g[i].link=NULL;
i++;
}
i=1;
while(i<=e)//采用头插法初始化邻接点域
{
fflush(stdin);
printf("请输入第 %d 条边的起点和终点:",i);//无向图是双向的 1-2 2-1
scanf("%d%d",&start,&end);
p=(enode *)malloc(sizeof(enode));
p->vertex=end;
p->next=g[start].link;
g[start].link=p;
p=(enode *)malloc(sizeof(enode));
p->vertex=start;
p->next=g[end].link;
g[end].link=p;
i++;
}
}
//Breadth First Search 广度优先搜索 相当于树的层次遍历
void BFS(linkQueue *queue,int i)
{
int temp;
enode *p;
InsertQueue(queue,i);
while(NULL!=queue->front)
{
temp=outQueue(queue);
if(!visited[temp])
{
printf("%d ",temp);
visited[temp]=1;
}
p=g[temp].link;
while(NULL!=p)
{
if(!visited[p->vertex])
{
InsertQueue(queue,p->vertex);
}
p=p->next;
}
}
}
//Depth First Search 深度优先搜索 相当于树的先序遍历
void DFS(vlist g,int i)
{
enode *p;
printf("%c ",g[i].data);
visited[i]=1;
p=g[i].link;
while(NULL!=p)
{
if(!visited[p->vertex])
{
DFS(g,p->vertex);
}
p=p->next;
}
}
//遍历每个顶点
void DFSGraphic(vlist g)
{
int i;
memset(visited,0,n);
for(i=1;i<=n;i++)
{
if(!visited[i])
{
//DFS(g,i);
BFS(&queue,i);
}
}
printf("\n");
}
int main()
{
Init(&queue);
createGraphic(g);
DFSGraphic(g);
return 0;
}
分享到:
相关推荐
实现无向图的建立,深度优先、广度优先遍历及遍历序列的输出
实现无向图的建立,深度优先和广度优先遍历,输出遍历序列
建立图的邻接表存储结构,输入或存储任意一个无向图,显示图的深度优先搜索遍历路径和广度优先搜索遍历路径。
用字符文件提供数据建立连通无向图邻接表存储结构。编写程序,实现DFS与BFS算法,输出DFS与BFS生成树的每条边。(边用顶点序号组成的无序偶表示) 实验目的:掌握图的邻接表存储结构;掌握图的遍历算法与生成树。
图的遍历方式包括DFS BFS,这个工程文件是俩种遍历方式的实现,适合学习用,工程实践还得加工,具体分析 在我的博客 数据结构练习 10
无向图主要包括双方面内容,图的遍历和寻找联通分量。 无向图的遍历 无向图的遍历有两种方式—广度优先搜索(BFS)和深度优先搜索(DFS)。广度优先搜索在遍历一个顶点的全部节点时,先把当前节点全部相邻节点遍历了。...
与图相关的操作,采用邻接矩阵或邻接表作为存储结构,完成有向图和无向图的DFS和BFS操作
有向无环图的判断 深度优先遍历 广度优先遍历 图的着色问题 BFS DFS
图的DFS实现,Description 请定一个无向图,顶点编号从0到n-1,用广度优先搜索(BFS),遍历并输出。遍历时,先遍历节点编号小的。
设计一个有向图和一个无向图,使用邻接矩阵和邻接表存储结构,完成在这两种存储结构下有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。 三、实验要求: 1. 根据实验内容编程,画出你所设计的图,...
头歌数据结构图的邻接表存储及遍历操作 第1关图的邻接表存储及求邻接点操作 第2关图的深度遍历 第3关图的广度遍历 稳过
以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 [测试数据] 由学生依据软件工程的测试技术自己确定。注意测试边界...
(1)无向图用邻接矩阵,邻接表,十字链表法实现存储。 (2)图的DFS,BFS算法的实现。 (3)最小生成树(两种算法)的实现。 (4)求图的连通分量。
广度优先遍历(BFS)和深度优先遍历(DFS)是图结构中最常用的遍历方式。其中广度优先遍历配合上队列能够找到两点之间的最短路径,同时也能解决一些其他的问题(比如寻找迷宫的最短逃离路线)。广度优先遍历寻找两点之间...
数据结构课程中的深度优先搜索算法、广度优先搜索算法的C语言程序,在Turbo C 2.0上调试通过。
该算法为有向无环图(DAG)的DFS遍历提供了不超过3次BFS访问的有效解决方案,从而可以找到DAG节点之间的前序,后序和父级关系。 BFS的首次访问旨在将DAG转换为DT(图B); 下次访问是在DT上完成的,它的作用是为...
设计一个有向图和一个无向图,使用基于邻接矩阵的存储结构,完成有向图和无向图的DFS(深度优先)和BFS(广度优先)遍历操作。 课后使用基于邻接表的存储结构,完成有向图和无向图的遍历操作。
深度优先遍历(dfs) 访问标记避免重复vis[N]、add_edge(起点,终点){G[v].push_back(u);无向反向} 广度优先遍历(bfs) 队列、优先队列(字典序) 拓扑排序 判定有向无环图(DAG)
图的概念和操作 图的存储:邻接矩阵,邻接表 图的遍历:宽度优先,深度优先 生成树:DFS 生成树,BFS 生成树 最小生成树:Prim 算法,Kruskal 算法 最短路径问题: 单源点最短路径和 Dijkstra 算法 所有顶点之间的...
对于断开连接的无向图,定义类似,桥接是一种边移除,它增加了断开连接的组件的数量。 与连接点一样,网桥代表连接网络中的漏洞,对于设计可靠的网络非常有用。例如,在有线计算机网络中,铰接点表示关键计算机,桥...