C++ 数据结构(六)图(1)概述
in C/C++ with 0 comment, Views is 81

C++ 数据结构(六)图(1)概述

in C/C++ with 0 comment, Views is 81

上一篇:《C++ 数据结构(五)二叉树(7)层次遍历》

邻接、关联

G = (V; E)

vertex: n = |V|

edge|arc : e = |E|

邻接关系(adjacency):相邻接的两个顶点之间的关系

关联关系(incideace):顶点与邻接边之间的关系

1.png

无向、有向

若邻接顶点 UV次序无所谓

(U, V) 为无向边(undirected edge)

例:若 UV 的好友,则 V 也必是 U 的好友

所有边都是无向的图,即无向图(undigraph)

反之,有向图(digraph)中均为有向边(directed edge)

UV 分别称作边 (U, V) 的尾(tail)、头(head)

例:U 欠 V 的钱V 欠 U 的钱

2.png

路径、环路

路径:π = <V(0), V(1), ..., V(k)>

长度:|π| = k

简单路径:V(i) = V(j) 除非 i = j

环/环路:V(0) = V(k)

有向无环图(DAG)

3.png

下一篇:《C++ 数据结构(六)图(2)邻接矩阵》

Responses
选择表情