没有合适的资源？快使用搜索试试~ 我知道了~

文库首页后端C图的深度优先遍历

图的深度优先遍历

图深度优先

需积分: 11 1 下载量 47 浏览量 2013-05-14 18:51:34 上传评论收藏 508KB PPT 举报

温馨提示

试读

43页

关于图的深度优先的原理和方法，供大家参考！！

资源推荐

资源详情

资源评论

图的深度优先遍历及应用

一、复习图的基本知识

图（ graph ）是图型数据结构，是一种非线性结构。

如图所示是 5 个 (1 、 2 、 3 、 4 、 5) 城市以及他们之

间的航空路线，这里城市我们称为顶点，城市之间的联

系（航空路线）称之为边。我们将顶点、边组成的数据

关联成为“图结构”。  （  ，  ）

1 A

2 5 B E

3 4 C D

图 1 （ G1 ）图 2 （ G2 ）

二、图的存储结构 

(1) 邻接矩阵：此种方法表示顶点之间的相邻关系的矩阵。

若有 n 个顶点（ 1 ， 2 ， 3 ，…… n ）则 n 阶方阵是：对于无向图

（ Vi ,Vj ）或（ Vj , Vi ）∈ E （ G ）

A[I ， J]= 1 ，对于有向图（ Vi ,Vj ）∈ E

（ G ）

0 ，反之

对于图 1 和图 2 ，他们的邻接矩阵分别表示如下的 A1 、 A2 ：

1 2 3 4 5 A B C D E

0 1 0 1 1 1 0 1 0 0 1 A

A1= 1 0 1 1 1 2 A2= 0 0 1 0 0 B

0 1 0 1 1 3 0 0 0 1 0 C

1 1 1 0 1 4 1 1 0 0 1 D

1 1 1 1 0 5 0 0 1 0 0 E

图的邻接矩阵存储结构算法：

 图的顶点数  ；  （图中的边数）

 （设无向不带权的图）

 

!"# 

$%&

'(!!( ) 读顶点信息 *

'(!'+!

#,- ) 初始化 *

'(!!( ) 读顶点信息 *

'!

$

.!(+ ； #,- #-,

! 

(2). 图的邻接表表示

图的邻接表存储方式是：将图中的每个顶点建立一

个邻接关系的单链表，此单向链表称为 Vi 的邻接表，并

将它们的表头指针用数组存储的一种图的表示方法。其基

本方法是： Vi 邻接表中的每个结点用来存储与该顶点有

边的关系的信息；

 表头结点存放顶点的信息以及指针域。

对于图 1 的邻接表结构可以如下图所示：

邻接表结构

建立图 1 的邻接表结构的算法：

const n= 5 { 图的顶点数 } ， e=9 { 图的边数 }

type point=^node; { 定义边结点 }

node=record

adjvex : 1..n { 定义邻接点域 } ；

weight : integer ; { 权值所属类型 }

next :point ; { 链接域 }

end ;

vexnode=record { 定义表头结点 } ；

data : integer ; { 数据类型 }

link : point ;

end ;

adjlist=array[1..n ] of vexnode

剩余42页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

LiangTreeMan

粉丝: 0
资源: 21

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

图的深度优先遍历

JavaScript树的深度优先遍历和广度优先遍历算法示例

C#深度优先遍历实现全排列

MATLAB实现迷宫的递归深度优先遍历算法

邻接矩阵存储图的深度优先遍历.pdf

图的深度优先遍历的实现C/C++ DFS

图的优先遍历

深度优先遍历

图的深度优先遍历及广度优先遍历

图的深度优先遍历和广度优先遍历

图的遍历 广度优先和深度优先

深度优先遍历 深度优先遍 深度优先遍

深度优先遍历和广度优先遍历

深度优先遍历与广度优先遍历

树的深度优先遍历与广度优先遍历

STM32循迹小车（灰度+OpenMV权重判断）

谭浩强C语言程序设计第五版详细答案

基于CAPL的S19文件解析

MQTT协议设备客户端与图传APP.zip

Keil.STM32H7xx-DFP.3.1.1.pack

基于stm32f407的示波器+FFT频谱分析

最新资源

图的遍历广度优先和深度优先

深度优先遍历深度优先遍深度优先遍