专栏首页米扑专栏图的深度优先和广度优先算法(DFS递归与非递归)

图的深度优先和广度优先算法(DFS递归与非递归)

本博客前面文章已对图有过简单的介绍,本文主要是重点介绍有关图的一些具体操作与应用

阅读本文前,可以先参考本博客 各种基本算法实现小结(四)—— 图及其遍历   和  图的一些基本算法

无向图——邻接矩阵的深度优先和广度优先算法实现

测试环境:VS2008(C)

#include "stdafx.h"
#include <stdlib.h>
#include <malloc.h>
#define INFINITY INT_MAX
#define MAX_VEX 20
#define VRType int
#define VertexType char
#define InfoType int
int *visited;
/********************************/
/****      图的结构定义      ****/
/********************************/
typedef enum
{
	DG, 
	DN,
	UDG,
	UDN
}GraphKind;
struct _ArcCell
{
	VRType adj; /* note weight */
	InfoType *info;
};
typedef struct _ArcCell ArcCell, AdjMatrix[MAX_VEX][MAX_VEX];
struct _MGraph
{
	VertexType vexs[MAX_VEX];
	AdjMatrix arcs;
	int vexnum, arcnum;
	GraphKind kind;
};
typedef struct _MGraph MGraph;
/********************************/
/****      栈的结构定义      ****/
/********************************/
struct _node
{
	int ivex;
	struct _node *next;
};
typedef struct _node node, *pnode;
struct _stack
{
	int size;
	pnode ptop;
};
typedef struct _stack stack, *pstack;
/********************************/
/****      堆的结构定义      ****/
/********************************/
struct _queue
{
	pnode front;
	pnode rear;
};
typedef struct _queue queue, *pqueue;
/********************************/
/****         栈的实现       ****/
/********************************/
pstack init_stack(int size)
{
	pnode pn=NULL;
	pstack ps=NULL;
	pn=(pnode)malloc(sizeof(node));
	ps=(pstack)malloc(sizeof(stack));
	pn->ivex=-1;
	pn->next=NULL;
	ps->size=size;
	ps->ptop=pn;
	return ps;
}
int empty_stack(pstack ps)
{
	if(ps->ptop->next==NULL)
		return 1;
	else
		return 0;
}
void push_stack(pstack ps, int ivex)
{
	pnode pn=NULL;
	pn=(pnode)malloc(sizeof(node));
	pn->ivex=ivex;
	pn->next=ps->ptop;
	ps->ptop=pn;
}
int pop_stack(pstack ps)
{
	int ivex=-1;
	pnode pn=NULL;
	if(!empty_stack(ps))
	{
		pn=ps->ptop;
		ps->ptop=ps->ptop->next;
		ivex=pn->ivex;
		free(pn);
	}
	return ivex;
}
/********************************/
/****         堆的实现       ****/
/********************************/
queue init_queue()
{
	pnode pn=NULL;
	queue qu;
	pn=(pnode)malloc(sizeof(node));
	pn->next;
	pn->ivex=-1;
	qu.front=qu.rear=pn;
	return qu;
}
int empty_queue(queue qu)
{
	if(qu.front==qu.rear)
		return 1;
	else
		return 0;
}
void en_queue(queue qu, int ivex)
{
	pnode pn=NULL;
	pn=(pnode)malloc(sizeof(node));
	pn->ivex=ivex;
	pn->next=qu.rear->next;
	qu.rear=pn;
}
int de_queue(queue qu)
{
	int ivex=-1;
	pnode pn=NULL;
	if(!empty_queue(qu))
	{
		pn=qu.front;
		qu.front=qu.front->next;
		ivex=pn->ivex;
		free(pn);
	}
	return ivex;
}
/********************************/
/****         图的实现       ****/
/********************************/
int LocateVex(MGraph g, char ch)
{
	int i;
	for(i=1; i<=g.vexnum; i++)
		if(ch==g.vexs[i])
			return i;
	return -1;
}
MGraph Create_UDG()
{
	int i, j, w, p1, p2;
	char ch1, ch2;
	MGraph g;
	printf("Enter vexnum arcnum: ");
	scanf("%d %d", &g.vexnum, &g.arcnum);
	getchar();
	for(i=1; i<=g.vexnum; i++)
		for(j=1; j<=g.vexnum; j++)
			g.arcs[i][j].adj=g.arcs[j][i].adj=INFINITY; /* UDG should define i-j and j-i */
	printf("Enter %d vex.../n", g.vexnum);
	for(i=1; i<=g.vexnum; i++)
	{
		printf("vex %d: ", i);
		scanf("%c", &g.vexs[i]);
		getchar();
	}
	printf("Enter %d arc.../n", g.arcnum);
	for(i=1; i<=g.arcnum; i++)
	{
		printf("arc %d: ", i);
		scanf("%c %c %d", &ch1, &ch2, &w);
		getchar();
		p1=LocateVex(g, ch1);
		p2=LocateVex(g, ch2);
		g.arcs[p1][p2].adj=g.arcs[p2][p1].adj=w;
	}
	return g;
}
int FirstVex(MGraph g, int i)
{
	int k;
	if(i>=1 && i<=g.vexnum)
		for(k=1; k<=g.vexnum; k++)
			if(g.arcs[i][k].adj!=INFINITY)
				return k;
	return -1;
}
int NextVex(MGraph g, int i, int j)
{
	int k;
	if(i>=1 && i<=g.vexnum && j>=1 && j<=g.vexnum)
		for(k=j+1; k<=g.vexnum; k++)
			if(g.arcs[i][k].adj!=INFINITY)
				return k;
	return -1;
}
void DFS(MGraph g, int i)
{
	int j;
	if(!visited[i])
	{
		visited[i]=1;
		printf("%3c", g.vexs[i]);
		for(j=FirstVex(g, i); j>=1; j=NextVex(g, i, j))
			if(!visited[j])
				DFS(g, j);
	}
}
void DFS_Graph(MGraph g)
{
	int i;
	visited=(int *)malloc((g.vexnum+1)*sizeof(int));
	for(i=1; i<=g.vexnum; i++)
		visited[i]=0;
	for(i=1; i<=g.vexnum; i++)
		if(!visited[i])
			DFS(g, i);
}
void DFS2_Graph(MGraph g)
{
	int i, j, k;
	pstack ps=NULL;
	ps=init_stack(g.vexnum);
	visited=(int *)malloc((g.vexnum+1)*sizeof(int));
	for(i=1; i<=g.vexnum; i++)
		visited[i]=0;
	for(i=1; i<=g.vexnum; i++)
		if(!visited[i])
		{
			visited[i]=1;
			printf("%3c", g.vexs[i]);
			push_stack(ps, i);
			k=i;
			while (!empty_stack(ps))
			{		
				for(j=FirstVex(g, k); j>=1; j=NextVex(g, k, j))
				{
					if(!visited[j])
					{
						visited[j]=1;
						printf("%3c", g.vexs[j]);
						push_stack(ps, j); /* push all visited ivex */
						k=j; /* newer node */
					}					
				}
				k=pop_stack(ps);
			}
		}
}
void BFS_Graph(MGraph g)
{
	int i, j, k;
	queue qu;
	qu=init_queue();
	visited=(int *)malloc((g.vexnum+1)*sizeof(int));
	for(i=1; i<=g.vexnum; i++)
		visited[i]=0;
	for(i=1; i<=g.vexnum; i++)
		if(!visited[i])
		{
			visited[i]=1;
			printf("%3c", g.vexs[i]);
			en_queue(qu, i);
			while (!empty_queue(qu))
			{
				k=de_queue(qu);
				for(j=FirstVex(g, k); j>=1; j=NextVex(g, k, j))
					if(!visited[j])
					{
						visited[j]=1;
						printf("%3c", g.vexs[j]);
						en_queue(qu, j);
					}
			}
		}
}
/********************************/
/****          主函数        ****/
/********************************/
int _tmain(int argc, _TCHAR* argv[])
{
	MGraph g;
	g=Create_UDG();
	printf("/nDFS: "); 
	DFS_Graph(g);       /* recursion */
	printf("/nDFS: "); 
	DFS2_Graph(g);      /* non recursion */
	printf("/nBFS: ");
	BFS_Graph(g);
	printf("/n");
	return 0;
}

运行结果:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 图的基本算法实现(邻接矩阵与邻接表两种方法)

    ==========================================================

    阳光岛主
  • 【leetcode】Longest Consecutive Sequence

    Given an unsorted array of integers, find the length of the longest consecutive ...

    阳光岛主
  • 各种基本算法实现小结(四)—— 图及其遍历

    ====================================================================

    阳光岛主
  • 恢复删除的数据

    老七Linux
  • CVE-2017-8464远程命令执行漏洞(震网漏洞)复现

    2017年6月13日,微软官方发布编号为CVE-2017-8464的漏洞公告,官方介绍Windows系统在解析快捷方式时存在远程执行任意代码的高危漏洞,黑客可以...

    伍尚国
  • 冒泡排序简单操作模版及实例分析

    1 #include <bits/stdc++.h> 2 using namespace std; 3 inline int read() 4 { 5...

    Angel_Kitty
  • MSBuild入门(续)

    MSBuild基本概念(续) 在上一篇简单的介绍了下MSBuild中的四个基本块,每块介绍比较单薄,在这里对在大多数的项目模版生成的*.*proj文件中比较常见...

    blackheart
  • 三维凸包

    所以本文来学习一下三维空间中凸包的一种直观算法——增量算法(increment algorithm)

    ACM算法日常
  • 洛谷 2634&&BZOJ 2152: 聪聪可可【点分治学习+超详细注释】

    2152: 聪聪可可 Time Limit: 3 Sec  Memory Limit: 259 MB Submit: 3435  Solved: 1776 [S...

    Angel_Kitty
  • 1098: C语言实验题――素数

    描述:输出100->200之间的素数的个数,以及所有的素数。 输入:无 输出:100->200之间的素数的个数,以及所有的素数。 样例输入: 样例输出:...

    bboysoul

扫码关注云+社区

领取腾讯云代金券