C++实现图的邻接矩阵存储和广度、深度优先遍历实例分析

本文实例讲述了C++实现图的邻接矩阵存储和广度、深度优先遍历的方法。分享给大家供大家参考。具体如下:

示例:建立如图所示的无向图

由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边.
示例输入(按照这个格式输入):

5
6
abcde
0 1 1
0 2 1
0 3 1
2 3 1
2 4 1
1 4 1

输入结束(此行不必输入)

注:0 1 1表示该图的第0个顶点和第1个定点有边相连,如上图中的a->b所示
      0 2 1表示该图的第0个顶点和第2个定点有边相连,如上图中的a->c所示
      2 3 1表示该图的第2个顶点和第3个定点有边相连,如上图中的c->d所示

实现代码如下:

#include <stdio.h>
#define MAX_GRAPH 100
#define MAX_QUEUE 30
typedef struct
{
 char vex[MAX_GRAPH]; /* 顶点 */
 int edge[MAX_GRAPH][MAX_GRAPH]; /* 邻接矩阵 */
 int n; /* 当前的顶点数 */
 int e; /* 当前的边数 */
}GRAPH;
void Create(GRAPH *G); /* 图的邻接矩阵表示法 */
void BFS(GRAPH *G,int k); /* 广度优先遍历 */
void DFS(GRAPH *G,int k); /* 深度优先遍历 */
int visited[MAX_GRAPH];
int main(int argc, char *argv[])
{
 int i;
 for(i = 0 ; i < MAX_QUEUE ; ++i)
  visited[i] = 0;
 GRAPH G;
 Create(&G);
/* BFS(&G,0);*/
 DFS(&G,0);

 return 0;
}
void BFS(GRAPH *G,int k)
{
 int queue[MAX_QUEUE]; /* 队列 */
 int front = -1,rear = -1,amount = 0;
 int visited[MAX_GRAPH]; /* 标记已经访问过的元素 */
 int i,j;

 for(i = 0 ; i < MAX_GRAPH ; ++i)
  visited[i] = 0;

 printf("访问顶点%c\n",G->vex[k]);
 visited[k] = 1;

 rear = (rear + 1) % MAX_QUEUE; /* 入队操作 */
 queue[rear] = k;
 front = rear;
 ++amount;

 while(amount > 0)
 {
  i = queue[front]; /* 出队操作 */
  front = (front + 1) % MAX_QUEUE;
  --amount;

  for(j = 0 ; j < G->n ; ++j)
  {
   if(G->edge[i][j] != 0 && visited[j] == 0)
   {
    printf("访问顶点%c\n",G->vex[j]);
    visited[j] = 1;

    rear = (rear + 1) % MAX_QUEUE; /* 入队 */
    queue[rear] = j;
    ++amount;
   }
  }
 }
 printf("遍历结束\n");
}
void DFS(GRAPH *G,int k)
{
 int j;
 printf("访问顶点:%c\n",G->vex[k]);
 visited[k] = 1;

 for(j = 0 ; j < G->n ; ++j)
 {
  if(G->edge[k][j] != 0 && visited[j] == 0)
   DFS(G,j);
 }
}
void Create(GRAPH *G)
{
 printf("输入顶点数:\n");
 scanf("%d",&G->n);
 printf("输入边数:\n");
 scanf("%d",&G->e);

 getchar();

 int i,j,k,w;
 printf("请输入端点(char型):\n");
 for(i = 0 ; i < G->n ; ++i) /* 建立表头 */
  scanf("%c",&G->vex[i]);

 for(i = 0 ; i < G->n ; ++i) /* 初始化邻接矩阵 */
  for(j = 0 ; j < G->n ; ++j)
   G->edge[i][j] = 0;

 printf("请输入边:\n");
 for(k = 0 ; k < G->e ; ++k)
 {
  scanf("%d%d%d",&i,&j,&w); /* 输入(vi,vj)上的权w */
  G->edge[i][j] = w;
  G->edge[j][i] = w;
 }
}

希望本文所述对大家的C++程序设计有所帮助。

时间: 2015-04-17

C++实现图的邻接表存储和广度优先遍历实例分析

本文实例讲述了C++实现图的邻接表存储和广度优先遍历方法.分享给大家供大家参考.具体如下: 示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6 abcde 0 1 0 2 0 3 2 3 2 4 1 4 输入结束(此行不必输入) 注:0 1表示该图的第0个顶点和第1个定点有边相连,如上图中的a->b所示       0 2表示该图的第0个顶点和第2个定点有边相连,如上图中的a->c所示       2 3表示该图的

c语言 汉诺塔算法代码

复制代码 代码如下: #include<stdio.h> void move(char a,char b) {     printf("%c->%c\n",a,b); } void han(int n,char a,char b,char c) {     if(n>0)     {         han(n-1,a,c,b);         move(a,b);         han(n-1,c,b,a);     } } int main() {   

C语言使用回溯法解旅行售货员问题与图的m着色问题

旅行售货员问题 1.问题描述: 旅行售货员问题又称TSP问题,问题如下:某售货员要到若干个城市推销商品,已知各城市之间的路程(或旅费),他要选定一条从驻地出发,经过每个城市一遍最后回到驻地的路线,使总的路线(或总的旅费)最小.数学模型为给定一个无向图,求遍历每一个顶点一次且仅一次的一条回路,最后回到起点的最小花费. 2.输入要求: 输入的第一行为测试样例的个数T( T < 120 ),接下来有T个测试样例.每个测试样例的第一行是无向图的顶点数n.边数m( n < 12,m < 100 )

C语言实现图的搜索算法示例

本文实例讲述了C语言实现图的搜索算法.分享给大家供大家参考,具体如下: 在游戏中,常常遇到路径规划问题,用到图的相关算法,我们以简单图来学习. 图通常有两种表示方式,矩阵和邻接表.矩阵表示简单,运算快,但当矩阵是稀疏矩阵的时候就存在空间浪费的问题,并且效率也会下降,而邻接表节约空间,并且由于边是连续访问,时间效率也比较高.在本文中,我们将以邻接表来表示图. #include<queue> #include<stack> using namespace std; struct SE{

对C语言中递归算法的深入解析

许多教科书都把计算机阶乘和菲波那契数列用来说明递归,非常不幸我们可爱的著名的老潭老师的<C语言程序设计>一书中就是从阶乘的计算开始的函数递归.导致读过这本经书的同学们,看到阶乘计算第一个想法就是递归.但是在阶乘的计算里,递归并没有提供任何优越之处.在菲波那契数列中,它的效率更是低的非常恐怖. 这里有一个简单的程序,可用于说明递归.程序的目的是把一个整数从二进制形式转换为可打印的字符形式.例如:给出一个值4267,我们需要依次产生字符'4','2','6',和'7'.就如在printf函数中使用

C语言位图算法详解

本文详细讲述了位图算法的定义与C语言实现方法,分享给大家供大家参考之用.具体如下: 位图法定义: 位图法就是bitmap的缩写,所谓bitmap,是用每一位来存放某种状态,适用于大规模数据,但数据状态又不是很多的情况.通常是用来判断某个数据存不存在的. 例如,要判断一千万个人的状态,每个人只有两种状态:男人,女人,可以用0,1表示.那么就可以开一个int数组,一个int有32个位,就可以表示32个人.操作的时候可以使用位操作.   数据结构: unsigned int bit[N]; 在这个数组

c语言实现冒泡排序、希尔排序等多种算法示例

实现以下排序 插入排序O(n^2) 冒泡排序 O(n^2) 选择排序 O(n^2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 希尔排序 O(n^1.25) 1.插入排序 O(n^2) 一般来说,插入排序都采用in-place在数组上实现.具体算法描述如下:⒈ 从第一个元素开始,该元素可以认为已经被排序⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置⒋ 重复步骤3,直到找到已排序的元素

C语言实现魔方阵算法(幻方阵 奇魔方 单偶魔方实现)

例如三阶魔方阵为: 魔方阵有什么的规律呢? 魔方阵分为奇幻方和偶幻方.而偶幻方又分为是4的倍数(如4,8,12--)和不是4的倍数(如6,10,14--)两种.下面分别进行介绍. 2 奇魔方的算法 2.1 奇魔方的规律与算法 奇魔方(阶数n = 2 * m + 1,m =1,2,3--)规律如下: 数字1位于方阵中的第一行中间一列:数字a(1 < a  ≤ n2)所在行数比a-1行数少1,若a-1的行数为1,则a的行数为n:数字a(1 < a  ≤ n2)所在列数比a-1列数大1,若a-1的列

C语言实现图的遍历之深度优先搜索实例

DFS(Depth-First-Search)深度优先搜索算法是图的遍历算法中非常常见的一类算法.分享给大家供大家参考.具体方法如下: #include <iostream> #include <algorithm> #include <iterator> using namespace std; #define MAX_VERTEX_NUM 10 struct Node { int adjvex; struct Node *next; int info; }; typ

C语言经典算法例题求100-999之间的“水仙花数

题目:打印出所有的 "水仙花数 ",所谓 "水仙花数 "是指一个三位数,其各位数字立方和等于该数本身. 例如:153是一个 "水仙花数 ",因为153=1的三次方+5的三次方+3的三次方. 实现代码如下 #include <iostream> #include <Cmath> using namespace std; /* 求100-999之间的水仙花数 */ int main() { int number,hun,ten

详解约瑟夫环问题及其相关的C语言算法实现

约瑟夫环问题 N个人围成一圈顺序编号,从1号开始按1.2.3......顺序报数,报p者退出圈外,其余的人再从1.2.3开始报数,报p的人再退出圈外,以此类推.   请按退出顺序输出每个退出人的原序号 算法思想 用数学归纳法递推. 无论是用链表实现还是用数组实现都有一个共同点:要模拟整个游戏过程,不仅程序写起来比较烦,而且时间复杂度高达O(nm),若nm非常大,无法在短时间内计算出结果.我们注意到原问题仅仅是要求出最后的胜利者的序号,而不是要读者模拟整个过程.因此如果要追求效率,就要打破常规,实

C语言实现的排列组合问题的通用算法、解决方法

尽管排列组合是生活中经常遇到的问题,可在程序设计时,不深入思考或者经验不足都让人无从下手.由于排列组合问题总是先取组合再排列,并且单纯的排列问题相对简单,所以本文仅对组合问题的实现进行详细讨论.以在n个数中选取m(0<m<=n)个数为例,问题可分解为: 1. 首先从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止. 2. 从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m. 很明显,上述方法是一个递归的过程,也

Go语言实现的排列组合问题实例(n个数中取m个)

本文实例讲述了Go语言实现的排列组合问题.分享给大家供大家参考,具体如下: (一)组合问题 组合是一个基本的数学问题,本程序的目标是输出从n个元素中取m个的所有组合. 例如从[1,2,3]中取出2个数,一共有3中组合:[1,2],[1,3],[2,3].(组合不考虑顺序,即[1,2]和[2,1]属同一个组合) 本程序的思路(来自网上其他大神): (1)创建有n个元素数组,数组元素的值为1表示选中,为0则没选中. (2)初始化,将数组前m个元素置1,表示第一个组合为前m个数. (3)从左到右扫描数

Python实现的排列组合、破解密码算法示例

本文实例讲述了Python实现的排列组合.破解密码算法.分享给大家供大家参考,具体如下: 排列组合(破解密码) 1.排列 itertools.permutations(iterable,n) 参数一:要排列的序列, 参数二:要选取的个数 返回的是一个迭代对象,迭代器中的每一个元素都是一个元组 import itertools #概念:从n个不同元素中取出m(m≤n)个元素,按照一定的顺序排成一列,叫做从n个元素中取出m个元素的一个排列(Arrangement).特别地,当m=n时,这个排列被称作

java数组排列组合问题汇总

面试或笔试中,多次遇到以下4个关于排列组合的手撕算法,这里做个笔记,方法日后查阅: 1. 无重复元素的数组,求全排列: 2. 有重复元素的数组,求全排列: 3. 无重复元素的数组,求组合[子集]: 4. 有重复元素的数组,求组合: 以上四类题,可以用统一的模板实现,如下所示: /* *[组合&&排列] *把一个数组里的数组合全部列出,比如1和2列出来为1,2,12,21. *这个题目可以扩展成四个: *1.无重复数字的数组,求组合 *2.有重复数字的数组,求组合 *3.无重复数字的数组,求

IIS6 中&quot;ASP 0201 错误 无效的默认脚本语言&quot; 的解决方法

今天突然打开任意Asp文件,都会提示: Active Server Pages 错误 'ASP 0201' 无效的默认脚本语言 为此应用程序指定的默认脚本语言无效. 平台: Windows 2003 IIS 6.0 解决方法(对我的电脑适用,不知对别人是否有效,仅作参考): 1.在控制面板里,删除IIS组件. 2.删除C:\Inetpub目录. 3.重新安装IIS. 4.如果不行就试一下IIS管理器里的"重新启动IIS"

浅谈c语言中一种典型的排列组合算法

c语言中的全排列算法和组合数算法在实际问题中应用非常之广,但算法有许许多多,而我个人认为方法不必记太多,最好只记熟一种即可,一招鲜亦可吃遍天 全排列: #include<stdio.h> void swap(int *p1,int *p2) { int t=*p1; *p1=*p2; *p2=t; } void permutation(int a[],int index,int size) { if(index==size) { for(int i=0;i<size;i++) print

Golang排列组合算法问题之全排列实现方法

本文实例讲述了Golang排列组合算法问题之全排列实现方法.分享给大家供大家参考,具体如下: [排列组合问题] 一共N辆火车(0<N<10),每辆火车以数字1-9编号,要求以字典序排序输出火车出站的序列号. 输入: 包括N个正整数(0<N<10),范围为1到9,数字之间用空格分割,字符串首位不包含空格. 输出: 输出以字典序排序的火车出站序列号,每个编号以空格隔开,每个输出序列换行. 样例输入: 1 2 3 样例输出: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3

Python实现的简单排列组合算法示例

本文实例讲述了Python实现的简单排列组合算法.分享给大家供大家参考,具体如下: 1.python语言简单.方便,其内部可以快速实现排列组合算法,下面做简单介绍 2.一个列表数据任意组合 主要是利用自带的库: #_*_ coding:utf-8 _*_ #__author__='dragon' import itertools list1 = [1,2,3,4,5] list2 = [] for i in range(1,len(list1)+1): iter = itertools.comb

关于各种排列组合java算法实现方法

一.利用二进制状态法求排列组合,此种方法比较容易懂,但是运行效率不高,小数据排列组合可以使用 复制代码 代码如下: import java.util.Arrays; //利用二进制算法进行全排列//count1:170187//count2:291656 public class test {    public static void main(String[] args) {        long start=System.currentTimeMillis();        count

Python实现的排列组合计算操作示例

本文实例讲述了Python实现的排列组合计算操作.分享给大家供大家参考,具体如下: 1. 调用 scipy 计算排列组合的具体数值 >> from scipy.special import comb, perm >> perm(3, 2) 6.0 >> comb(3, 2) 3.0 2. 调用 itertools 获取排列组合的全部情况数 >> from itertools import combinations, permutations >>