nullChapter12 图Chapter12 图中国地质大学信息工程学院*内容提要内容提要12.1 图的基本概念和基本术语
12.2 图的应用示例
12.4 抽象数据类型Graph和Diagraph
12.5 无向图、有向图及网络的描述
12.7 图的类定义
12.8 图的遍历
12.10 图的搜索算法
12.11 图的应用12.7 类定义12.7 类定义无权有向图和无向图可以看作每条边的权是1的加权有向图和无向图。
无向图可以看作：
可以看作边(i, j) 和边(j,i) 都存在的有向图；
也可以看作所有边的权均为1 的加权图；
或者看作所有边的权为1，若边(i, j) 存在，则边(j, i) 也存在的加权有向图。邻接矩阵描述的图类关系邻接矩阵描述的图类关系AdjacencyWDigraphAdjacencyWGraphAdjacencyDigraphAdjacencyGraph AdjacencyWDigraph（加权有向图的耗费邻接矩阵）
AdjacencyWGraph（加权图）
AdjacencyDigraph（有向图）
AdjacencyGraph（无向图）12.7.2 邻接矩阵类
——加权有向图的耗费邻接矩阵（程序12-1）template
class AdjacencyWDigraph {
friend AdjacencyWGraph;
public:
AdjacencyWDigraph (int Vertices = 10, T noEdge = 0);
~AdjacencyWDigraph() { Delete2DArray(a,n+1); }
bool Exist(int i, int j) const;
int Edges( ) const { return e; }
int Vertices( ) const { return n; }
AdjacencyWDigraph& Add (int i, int j, const T& w);12.7.2 邻接矩阵类
——加权有向图的耗费邻接矩阵（程序12-1）null AdjacencyWDigraph& Delete(int i, int j);
int OutDegree(int i) const;
int InDegree(int i) const;
private :
T NoEdge; // 用于没有边存在的情形
int n; // 顶点数目
int e; // 边数
T **a; // 二维数组
} ;AdjacencyWDigraph构造函数AdjacencyWDigraph构造函数templateAdjacencyWDigraph::
AdjacencyWDigraph(int Vertices, T noEdge)
{ // 构造函数
n = Vertices;
e = 0;
NoEdge = noEdge;
Make2DArray(a, n+1, n+1);
//初始化为没有边的图
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j] = NoEdge;
}Θ( n2 )判断边是否存在Exist(int i, int j) 判断边是否存在Exist(int i, int j) template
bool AdjacencyWDigraph::Exist(int i, int j) const
{ // 边(i, j)存在吗?
if (i < 1 || j < 1 || i > n || j > n || a[i][j] == NoEdge)
return false;
return true;
} 函数Exist 的代码不能区分下面两种情况：
－ i 或j 是否为有效顶点；
－边(i, j) 是否存在。添加边: Add添加边: AddtemplateAdjacencyWDigraph&
AdjacencyWDigraph ::Add(int i, int j, const T& w)
{ // 如果边(i,j) 不存在，则将该边加入有向图中
if (i < 1 || j < 1 || i > n || j > n || i == j || a[i][j] != NoEdge)
throw BadInput();
a[i][j] = w;
e++;
return *this;
}Θ (1 )删除边: Delete删除边: Deletetemplate AdjacencyWDigraph&
AdjacencyWDigraph ::Delete(int i, int j)
{ //删除边( i , j ) .
if (i < 1 || j < 1 || i > n || j > n || a[i][j] == NoEdge)
throw BadInput();
a[i][j] = NoEdge;
e-- ;
return *this;
}Θ ( 1 )求顶点出度: OutDegree求顶点出度: OutDegreetemplate
int AdjacencyWDigraph::OutDegree(int i) const
{// 返回顶点i的出度
if (i < 1 || i > n) throw BadInput();
// 计算顶点i的出度
int sum = 0;
for (int j = 1; j <= n; j++)
if (a[i][j] != NoEdge) sum++;
return sum;
}Θ ( n )遍历第i行中
有效边的条数求顶点入度: InDegree求顶点入度: InDegreetemplate
int AdjacencyWDigraph::InDegree(int i) const
{// 返回顶点i的入度
if (i < 1 || i > n) throw BadInput();
// 计算顶点i的入度
int sum = 0;
for (int j = 1; j <= n; j++)
if (a[j][i] != NoEdge) sum++;
return sum;
}Θ ( n)遍历第i列中
有效边的条数无向加权图的定义（程序12-2）无向加权图的定义（程序12-2）template
class AdjacencyWGraph : public AdjacencyWDigraph
{
public :
AdjacencyWGraph(int Vertices = 10, T noEdge = 0) : AdjacencyWDigraph(Vertices, noEdge) { }
AdjacencyWGraph& Add(int i, int j, const T& w)
{
AdjacencyWDigraph< T > :: Add(i,j,w) ;
a[j][i]=w;
return *this;
}
AdjacencyWGraph& Delete(int i, int j)
{
AdjacencyWDigraph ::Delete(i , j) ;
a[j][i] = NoEdge;
return *this;
}
int Degree(int i) const {return OutDegree(i); }
} ;1）无向图的邻接矩阵
是对称的
2）派生类中如何解决
同名函数的屏蔽问题无向图的定义（程序12-4）无向图的定义（程序12-4）class AdjacencyGraph : public AdjacencyWGraph
{
public :
AdjacencyGraph(int Vertices = 10) :
AdjacencyWGraph(Vertices, 0) {}
AdjacencyGraph& Add(int i, int j)
{
AdjacencyWGraph ::Add (i, j, 1) ;
return *this;
}
AdjacencyGraph& Delete(int i, int j)
{
AdjacencyWGraph::Delete(i, j) ;
return *this;
}
} ;有向图的定义（程序12-3）有向图的定义（程序12-3）class AdjacencyDigraph : public AdjacencyWDigraph
{
public :
AdjacencyDigraph(int Vertices = 10) :
AdjacencyWDigraph(Vertices, 0) {}
AdjacencyDigraph& Add(int i, int j)
{
AdjacencyWDigraph::Add(i, j,1) ;
return *this;
}
AdjacencyDigraph& Delete(int i, int j)
{
AdjacencyWDigraph::Delete(i, j) ;
return *this;
}
} ;12.7.3 扩充Chain类-删除元素template
Chain& Chain::Delete(T& x)
{ // 删除与x匹配的元素
// 如果不存在相匹配的元素，则引发异常BadInput
ChainNode *current = first,
*trail = 0; // 指向current之前的节点
//搜索匹配元素
while (current && current->data != x)
{
trail = current;
current = current->link;
}12.7.3 扩充Chain类-删除元素删除元素（续）删除元素（续） if (!current) throw BadInput( ); // 不存在匹配元素
//在节点current中找到匹配元素
x = current->data; // 保存匹配元素
// 从链表中删除current 节点
if (trail)
trail->link = current->link;
else
first = current->link;
delete current; // 释放节点
return *this;
}邻接表描述的图类关系邻接表描述的图类关系LinkedBaseLinkedDigraphLinkedWDigraphLinkedGraphLinkedWGraph LinkedDigraph
LinkedWDigraph
LinkedGraph
LinkedWGraph链表节点的
结构不同12.7.4 类LinkedBase 无权和加权图的派生路径之所以不同，其原因在于加权有向图和无向图的链表节点中有一个权值域，而无权有向图和无向图中则没有。
对于后者，使用int 类型的链节点就足够了；而对于前者，链节点必须包含一个权值域和一个顶点域。尽管节点结构存在这种差别，但某些基本函数的代码仍然是一样的。
因此，引入一个新类LinkedBase，它包含了构造函数、析构函数、Edges和OutDegree函数。12.7.4 类LinkedBase邻接链描述的基类
（程序12-6）邻接链描述的基类
（程序12-6）template class LinkedBase
{ …友元类
public:
LinkedBase(int Vertices = 10)
{ n = Vertices ;
e = 0;
h = new Chain [n+1]; }
~LinkedBase( ) { delete [] h; }
int Edges( ) const { return e; }
int Vertices( ) const { return n; }
int OutDegree(int i) const
{if (i < 1 || i > n) throw OutOfBounds();
return h[i].Length(); }
private:
int n; //顶点数
int e; // 边数
Chain *h; //边节点链表表头指针数组
} ;nullint OutDegree(int i) const
{
if (i < 1 || i > n) throw OutOfBounds();
return h[i].Length();
}
某个节点的出度：统计第i行链表中结点的个数Θ ( diout)12.7.5 链接类
——有向图的邻接链表（程序12-7）12.7.5 链接类
——有向图的邻接链表（程序12-7）class LinkedDigraph : public LinkedBase
{
public:
LinkedDigraph(int Vertices = 10) : LinkedBase (Vertices) {}
bool Exist(int i, int j) const;
LinkedDigraph& Add(int i, int j);
LinkedDigraph& Delete(int i, int j);
int InDegree(int i) const;
protected :
LinkedDigraph& AddNoCheck(int i, int j);
} ;判断边( i, j )是否存在判断边( i, j )是否存在bool LinkedDigraph::Exist(int i, int j) const
{// 边( i , j )存在吗?
if (i < 1 || i > n) throw OutOfBounds( );
return (h[i].Search(j)) ? true : false;
}Θ ( diout)把边(i, j) 加入到图中把边(i, j) 加入到图中LinkedDigraph& LinkedDigraph::Add(int i, int j)
{ // 把边(i,j) 加入到图中
if (i < 1 || j < 1 || i > n || j > n || i == j || Exist(i, j))
throw BadInput();
return AddNoCheck(i, j);
}LinkedDigraph& LinkedDigraph::AddNoCheck(int i, int j)
{ // 增加边但不检查可能出现的错误
h[i].Insert(0,j); // 把j 添加到顶点i 的表中
e++;
return *this;
}Θ ( diout)删除边( i , j )删除边( i , j )LinkedDigraph& LinkedDigraph::Delete(int i, int j)
{ // 删除边( i , j )
if (i < 1 || i > n) throw OutOfBounds();
h[i].Delete( j ) ; //找到并删除节点
e--;
return *this;
}O (e)返回顶点i的入度返回顶点i的入度int LinkedDigraph::InDegree(int i) const
{ // 返回顶点i的入度
if (i < 1 || i > n) throw OutOfBounds();
// 计算到达顶点i的边
int sum = 0;
for (int j = 1; j <= n; j++)
if (h[j].Search(i)) sum++;
return sum;
}某个节点的入度：统计所有链表中满足data=i的结点个数O ( ne)无向图的邻接链表类（程序12-8）无向图的邻接链表类（程序12-8）class LinkedGraph : public LinkedDigraph
{
public:
LinkedGraph(int Vertices = 10) : LinkedDigraph (Vertices) {}
LinkedGraph& Add(int i, int j);
LinkedGraph& Delete(int i, int j);
int Degree(int i) const { return InDegree(i); }
int OutDegree(int i) const { return InDegree(i); }
protected :
LinkedGraph& AddNoCheck(int i, int j);
} ;向图中添加边( i , j )向图中添加边( i , j )LinkedGraph& LinkedGraph::Add(int i, int j)
{ // 向图中添加边( i , j )
if (i < 1 || j < 1 || i > n || j > n || i ==j || Exist(i, j))
throw BadInput();
return AddNoCheck(i, j);
}Θ ( diout)添加边(i, j), 不检查可能出现的错误添加边(i, j), 不检查可能出现的错误LinkedGraph& LinkedGraph::AddNoCheck(int i, int j)
{// 添加边(i,j), 不检查可能出现的错误
h[i].Insert (0, j) ;
try { h[j].Insert(0,i); } 对称加入！
// 若出现异常, 则取消第一次插入，并引发同样的异常
catch (...) { h[i].Delete(j); throw; }
e++;
return *this;
}1423删除边( i , j )删除边( i , j )LinkedGraph& LinkedGraph::Delete(int i, int j)
{ //删除边( i , j )
LinkedDigraph::Delete( i , j ) ; 对称删除(隐含e--)
e++; // 补偿，边只需减少一条！
LinkedDigraph::Delete( j , i ) ;
return *this;
}GraphNode类GraphNode类template class GraphNode
{
friend LinkedWDigraph;
friend LinkedWGraph;
friend Chain;
public :
int operator !=(GraphNode y) const
{ return ( vertex != y.vertex ) ; }
void Output(ostream& out) const
{ out << vertex << " " << weight << " "; }
private :
int vertex; // 边的第二个顶点
T weight; // 边的权重
} ;
template
ostream& operator<<(ostream& out, GraphNode x)
{ x.Output(out); return out; }权值结点加权有向图邻接链表类（程序12-9）加权有向图邻接链表类（程序12-9）template
class LinkedWDigraph : public LinkedBase >
{
public :
LinkedWDigraph(int Vertices = 10) : LinkedBase > (Vertices) {}
bool Exist(int i, int j) const;
LinkedWDigraph& Add(int i, int j, const T& w);
LinkedWDigraph& Delete(int i, int j);
int InDegree(int i) const;
protected :
LinkedWDigraph < T > &
AddNoCheck(int i, int j, const T& w);
} ;是否存在边(i, j) 是否存在边(i, j) template
bool LinkedWDigraph::Exist(int i, int j) const
{ // 存在边(i,j) 吗?
if (i < 1 || i > n) throw OutOfBounds();
GraphNode x;
x.vertex = j;
return h[i].Search(x);
} 加权图边节点结构GraphNodeΘ ( diout)添加边( i , j )添加边( i , j )templateLinkedWDigraph&
LinkedWDigraph ::Add(int i, int j, const T& w)
{ // 添加边( i , j )
if (i < 1 || j < 1 || i > n || j > n || i == j|| Exist(i, j))
throw BadInput();
return AddNoCheck(i, j, w);
}Θ ( diout)添加边( i , j )，不检查可能出现的错误添加边( i , j )，不检查可能出现的错误 template LinkedWDigraph&
LinkedWDigraph ::AddNoCheck(int i, int j, const T& w)
{ // 添加边( i , j )，不检查可能出现的错误
GraphNode x;
x.vertex = j;
x.weight = w;
h [i] .Insert (0 , x ) ;
e++ ;
return *this;
}删除边( i , j )删除边( i , j )templateLinkedWDigraph& LinkedWDigraph ::Delete(int i, int j)
{ //删除边( i , j )
if (i < 1 || i > n) throw OutOfBounds();
GraphNode x;
x.vertex = j;
h [i] . Delete (x) ;
e - - ;
return *this;
}O (e)返回顶点i的入度返回顶点i的入度template
int LinkedWDigraph::InDegree(int i) const
{// 返回顶点i的入度
if (i < 1 || i > n) throw OutOfBounds( );
int sum = 0;
GraphNode x;
x.vertex = i;
// 检查所有的( j , i )
for (int j = 1; j <= n; j++)
if (h[j].Search(x)) sum++;
return sum;
}O (ne)12.8 图的遍历12.8 图的遍历 图的遍历定义：从图中某一顶点出发，按照一定
规则
编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf
，通过边或弧对图中所有顶点访问一次且只访问一次。 图的遍历比树的遍历复杂，主要表现在以下方面：（1）出发点的选取与图的连通性；（2）回路的判断及处理：（3）下一个要访问的顶点的选取。 设置一个访问的标记数组reach[n]，初值为0，一旦访问了某顶点vi，便置reach[i]为1或被访问时的序号。几个主要操作：使用遍历器几个主要操作：使用遍历器Begin(i) ：返回第一个与顶点i邻接的顶点。
对于邻接表，返回顶点i 所对应表中的第一个顶点；
对于邻接矩阵，返回邻接于顶点i 的最小（即第一个）顶点。
在两种情况中，如果没有邻接顶点，都将返回零值。
NextVertex (i) ：返回下一个与顶点i邻接的顶点。
即返回顶点i 对应邻接表中的下一个顶点或返回邻接于顶点i的下一个最小顶点。
当没有下一个顶点时函数返回零。G1A＝几个主要操作几个主要操作InitializePos() ：初始化用来跟踪每一个邻接表或(耗费)邻接矩阵每一行中当前位置的存储配置。
DeactivatePos() ：释放InitializePos( )所产生的存储配置。12.8.2 邻接矩阵的遍历函数12.8.2 邻接矩阵的遍历函数邻接矩阵的遍历函数可以作为基类AdjacencyWDigraph的一个public函数来加以实现。
由于其他3种邻接类都是从这个类派生出来的，因此它们可以从AdjacencyDigraph类中继承该函数。
由于可能处在邻接矩阵不同行的不同位置，因此用一个数组pos来
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
每一行中的位置，这个变量是AdjacencyWDigraph的私有成员，定义如下：
int *pos;Pos的初始化与释放Pos的初始化与释放template
void AdjacencyWDigraph::InitializePos( )
{ pos = new int [n+1]; }
template
void AdjacencyWDigraph::DeactivatePos( )
{ delete [] pos; }邻接矩阵中返回第一个与顶点i邻接的顶点邻接矩阵中返回第一个与顶点i邻接的顶点template
int AdjacencyWDigraph::Begin(int i)
{ //返回第一个与顶点i邻接的顶点
if (i < 1 || i > n) throw OutOfBounds();
// 查找第一个邻接顶点
for (int j = 1; j <= n; j++)
if (a[i][j] != NoEdge) //第i行第一个顶点
{
pos[i] = j; return j;
}
pos[i] = n + 1; // 没有邻接顶点
return 0;
}邻接矩阵中返回下一个与顶点i邻接的顶点邻接矩阵中返回下一个与顶点i邻接的顶点template
int AdjacencyWDigraph::NextVertex(int i)
{// 返回下一个与顶点i邻接的顶点
if (i < 1 || i > n) throw OutOfBounds();
// 寻找下一个邻接顶点
for (int j = pos[i] + 1; j <= n; j++)
if (a[i][j] != NoEdge) // j 是下一个顶点
{
pos[i] = j; return j;
}
pos[i] = n + 1; // 不存在下一个顶点
return 0; }使用示例使用示例AdjacencyWDigraph wd;
加入边信息…，wd.Add(i, j, weight)
遍历：
int pos= wd.Begin(i);
while(pos!=0)
{ …
pos=wd.NextVertex(i);
} 12.8.3 邻接链表的遍历函数12.8.3 邻接链表的遍历函数 对于用邻接链表描述的图和网络，需要将程序12-12中定义的共享成员函数Initialize和DeactivatePos加入到LinkedBase类中，并且，还需要定义一个私有变量pos：
ChainIterator *pos；参见P92-P93
此外，还需要将余下的两个遍历函数加入到LinkedDigraph和LinkedWDigraph类中。void InitializePos( )
{ pos = new ChainIterator [n+1]; }
void DeactivatePos( ) { delete [] pos; }邻接链表中返回第一个与顶点i邻接的顶点邻接链表中返回第一个与顶点i邻接的顶点int LinkedDigraph::Begin(int i)
{// 返回第一个与顶点i邻接的顶点
if (i < 1 || i > n) throw OutOfBounds( );
int *x = pos[i].Initialize(h[i]); 返回fisrt指针
return (x) ? *x : 0;
}邻接链表中返回下一个与顶点i邻接的顶点邻接链表中返回下一个与顶点i邻接的顶点int LinkedDigraph::NextVertex(int i)
{ // 返回下一个与顶点i邻接的顶点
if (i < 1 || i > n) throw OutOfBounds();
int *x = pos[i].Next();
return (x) ? *x : 0;
}返回第一个与顶点i邻接的顶点返回第一个与顶点i邻接的顶点template
int LinkedWDigraph::Begin(int i)
{ // 返回第一个与顶点i邻接的顶点
if (i < 1 || i > n) throw OutOfBounds();
GraphNode *x = pos[i].Initialize(h[i]);
return (x) ? x->vertex : 0;
}返回下一个与顶点i邻接的顶点返回下一个与顶点i邻接的顶点template
int LinkedWDigraph::NextVertex(int i)
{ // 返回下一个与顶点i邻接的顶点
if (i < 1 || i > n) throw OutOfBounds();
GraphNode *x = pos[i].Next();
return (x) ? x->vertex : 0;
}后续程序类派生层次图：P392后续程序类派生层次图：P392遍历器虚基类无向图和网络类的基类12.10 图的搜索算法12.10 图的搜索算法宽（广）度优先搜索（横向）：BFS
深度优先搜索（纵向）：DFS
图的宽（广）度优先搜索（Breadth First Search，BFS）图的宽（广）度优先搜索（Breadth First Search，BFS）（1）访问指定的起始顶点v0，然后依次访问与v0相邻接的所有顶点w1，w2，…，wk；（2）按w1，w2，…，wk的顺序，依次访问它们每一个顶点的所有未被访问过的邻接点
设w1未被访问过的邻接点为w11，w12，…，w1m
wk未被访问过的邻接点为wk1，wk2，…，wkn（3）再按w11，w12，…，w1m ， wk1 ，wk2，…，wkn的顺序，依次去访问它们的所有未被访问过的邻接点；（4）依此类推，直到图中所有被访问过的顶点的邻接点都被访问过为止；（5）如果此时图中还有未被访问过的顶点，则从其中一个未被访问过的顶点出发，重复（1）-（5）直到图中所有顶点都被访问过为止。宽度优先搜索（BFS）示例宽度优先搜索（BFS）示例 判断从顶点1出发可到达的所有顶点的一种方法是首先确定邻接于顶点1的顶点集合，这个集合是{ 2 , 3 , 4 }。
然后确定邻接于{ 2 , 3 , 4 }的新的顶点集合，这个集合是{ 5 , 6 , 7 }。邻接于{ 5 , 6 , 7 }的顶点集合为{ 8 , 9 }，而不存在邻接于{ 8 , 9 }的顶点。
因此从顶点1出发可到达的顶点集合为{ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }。宽度优先搜索示例宽度优先搜索示例 宽度优先搜索遍历的结果序列为：V8V1V2V3V4V5V6V7 先访问的顶点其邻接点先被访问——队列。BFS算法思想BFS算法思想 为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。 为避免重复访问，需要一个辅助数组 reach [ ]，给被访问过的顶点加标记。 广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，类似于树的层次遍历。宽度优先搜索（BFS）伪码算法宽度优先搜索（BFS）伪码算法nullvoid Network::BFS(int v, int reach[], int label)
{ // 宽度优先搜索
LinkedQueue Q;
InitializePos( ); //初始化图遍历器数组
reach[v] = label;
Q . Add ( v ) ;
while (!Q.IsEmpty( )) {
int w;
Q.Delete(w); // 获取一个已标记的顶点
int u = Begin(w);
while (u) {// 访问w的邻接顶点
if (!reach[u]) { // 一个未曾到达的顶点
Q.Add ( u ) ;
reach[u] = label; } // 标记已到达该顶点
u = NextVertex(w); // 下一个与w邻接的顶点
}
}
DeactivatePos( ); // 释放遍历器数组
}邻接矩阵描述中B F S的直接实现邻接矩阵描述中B F S的直接实现template
void AdjacencyWDigraph::BFS (int v, int reach[], int label)
{ // 宽度优先搜索
LinkedQueue Q;
reach[v] = label;
Q . Add ( v ) ;
while (!Q.IsEmpty()) {
int w;
Q.Delete(w); // 获取一个已标记的顶点
// 对尚未标记的、邻接自w的顶点进行标记
for (int u = 1; u <= n; u++)
if (a[w][u] != NoEdge && !reach[u]) {
Q.Add(u); // u 未被标记
reach[u] = label;}
}
}O (sn)链接图和有向图中B F S的直接实现链接图和有向图中B F S的直接实现void LinkedDigraph::BFS(int v, int reach[], int label)
{ // 宽度优先搜索
LinkedQueue Q;
reach[v] = label;
Q . Add ( v ) ;
while (!Q.IsEmpty()) {
int w;
Q.Delete(w); // 获取一个已标记的顶点
// 使用指针p沿着邻接表进行搜索
ChainNode *p;
for (p = h[w].First(); p; p = p->link) {
int u = p->data;
if (!reach[u]) { // 一个尚未到达的顶点
Q . Add ( u ) ;
reach[u] = label; }
}
}
}BFS算法分析BFS算法分析【注意】只有当选取的出发点、采用的存储结构以及遍历方式都确定时遍历，遍历的结果才是唯一的。图的深度优先搜索（Depth First Search，DFS）图的深度优先搜索（Depth First Search，DFS）（1）首先访问指定的起始顶点v0，再访问与v0邻接的任一未访问过的顶点w1；（2）从w1出发，访问与w1邻接的任一未访问过的顶点w2；（3）从w2出发，重复与（2）类似的访问，直到遇到一个所有邻接点都被访问过的顶点为止；（4）依次回退到尚有邻接点未被访问过的顶点，重复与（3）类似的访问，直到图中所有和v0有路径相通的顶点都被访问过；（5）如果图中存在未被访问过的顶点，从其中一个未被访问过的顶点出发，重复（1）-（5），直至图中所有顶点都被访问完。深度优先搜索（DFS）递归算法思想深度优先搜索（DFS）递归算法思想（1）从指定顶点v0出发，访问该顶点v0；（2）从v0的一个未被访问过的邻接点出发，进行深度优先搜索，直到图中与v0有路径相通的顶点都被访问过；（3）若图中还存在未被访问过的顶点，则从其中一个未被访问的顶点出发，重复（1）-（3），直至图中所有顶点都被访问过为止。 图的深度优先搜索类似于树的先根遍历。深度优先搜索示例深度优先搜索示例 深度优先搜索遍历的结果序列为：V7V1V2V4V8V5V6V3 后访问的顶点其邻接点先被访问——栈。深度优先搜索算法－DFS深度优先搜索算法－DFSvoid Network::DFS(int v, int reach[], int label)
{ // 深度优先搜索
InitializePos( ); // 初始化图遍历器数组
dfs ( v, reach, label); // 执行d f s
DeactivatePos( ); // 释放图遍历器数组
}实际执行深度优先搜索的代码－dfs实际执行深度优先搜索的代码－dfsvoid Network::dfs(int v, int reach[], int label)
{ //实际执行深度优先搜索的代码
reach[v] = label;
int u = Begin(v);
while (u)
{ // u邻接至v
if (!reach[u]) dfs(u, reach, label);
u = NextVertex ( v ) ;
}
}思考：DFS的非递归算法思考：DFS的非递归算法 设置一个栈结构，
在遍历时，每访问一个顶点w，就将w压入栈中，然后访问w的一个未被访问的邻接顶点……
如果在遍历过程中某顶点的所有邻接顶点都已被访问过，就从栈顶删去该顶点，
然后继续访问当前栈顶元素的一个未被访问过的邻接顶点，当栈为空时，遍历操作结束。能使DFS和BFS产生最好和最坏性能的图例能使DFS和BFS产生最好和最坏性能的图例课堂练习课堂练习 选择题：如图所示，给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的顶点序列是 （1） ；而进行宽度优先遍历得到的序列是（2）。 （1）A. 1354267 （2）A. 1534267
B. 1347625 B. 1726453
C. 1534276 C. 1354276
D. 1247653 D. 1247653√√12.11 应用 寻找路径
连通图及连通分量
生成树12.11 应用12.11.1 寻找路径12.11.1 寻找路径若从顶点v 开始搜索（宽度或深度优先）且到达顶点w 时终止搜索，则可以找到一条从顶点v 到达顶点w 的路径。
要实际构造这条路径，需要记住从一个顶点到下一个顶点的边。
对于路径问题，所需要的边的集合已隐含在深度优先的递归过程中，因此可以很容易地利用深度优先策略设计一个寻找路径程序。完成顶点w 的标记之后展开递归，可以反向建立起从w 到v 的路径。nullFindPath 的代码如程序12 - 21。这个程序要求把Vertices( )定义为Network 的一个虚拟成员。findPath的输入参数是路径的开始顶点( v )和目标顶点( w )。如果没有从v到w的路径， findPath返回false；否则返回true。当找到路径时，用参数length 返回路径长度（路径中边的条数），用顶点数组p [ 0：length] 返回路径，其中p[0]=v 且p [length ] = w。
findPath首先检验v=w 情况。在这种情况下，返回一个长度为0的路径。如果v≠w，则调用图的遍历函数InitializePos，然后FindPath 产生并初始化一个数组reach，路径的DFS实际上是由Network的私有成员findPath完成的，当且仅当没有路径时， findPath返回false。null函数findPath是一个修改过的DFS，它对
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
的DFS作了如下两点修改：
1) 一旦到达了目标顶点w， findPath将不再继续搜索可到达顶点；
2) findpath 将开始顶点v 到当前顶点u 路径中的顶点记录到数组path 中。
findPath与DFS具有相同的复杂性。nullbool Network::FindPath (int v, int w, int &length, int path[])
{// 寻找一条从v 到w的路径, 返回路径的长度，并将路径存入数组p a t h [ 0 : l e n g t h ]
//如果不存在路径，则返回false
//路径中的第一个顶点总是v
path[0] = v;
length = 0; //当前路径的长度
if (v == w) return true;
//为路径的递归搜索进行初始化
int n = Vertices ( ) ;
InitializePos( ); // 遍历器
int *reach = new int [n+1];
for (int i = 1; i <= n; i++) reach[i] = 0;
// 搜索路径
bool x = findPath(v, w, length, path, reach);
DeactivatePos ( ) ;
delete [] reach;
return x;
}nullbool Network::findPath(int v, int w, int &length, int path[], int reach[])
{ // 实际搜索v到w的路径，其中v != w.
// 按深度优先方式搜索一条到达w的路径
reach[v] = 1;
int u = Begin(v);
while (u) {
if (!reach[u]) {
length++;
path[length] = u; // 将u 加入path
if (u == w) return true;
if (findPath(u, w, length, path, reach))
return true;
// 不存在从u 到w的路径
length--; //删除u
}
u = NextVertex(v) ;
}
return false; }12.11.2 连通图及连通分量12.11.2 连通图及连通分量通过从任意顶点开始执行DFS或BFS，并且检验所有顶点是否被标记为已到达顶点，可以判断一个无向图G是否连通。
假设i 是搜索的开始顶点并且搜索到达了图中的所有顶点，利用i 到u 的反向路径及i 到v的路径，可以构造任意两个顶点u 和v 之间的路径。如果图不连通，则函数Connected返回false，否则返回true。
由于连通的概念仅针对无向图和网络而言，因此，可以定义一个新类Undirected，函数Connected是Undirected的一个成员。null确定无向图是否连通
class Undirected : virtual public Network {
public :
bool Connected();
} ;
bool Undirected::Connected()
{ // 当且仅当图是连通的，则返回true
int n = Vertices( ) ;
// 置所有顶点为未到达顶点
int *reach = new int [n+1];
for (int i = 1; i <= n; i++)
reach[i] = 0;
// 对从顶点1出发可到达的顶点进行标记
DFS(1, reach, 1);
// 检查是否所有顶点都已经被标记
for (int i = 1; i <= n; i++)
if (!reach[i]) return false;
return true; }连通分量 (Connected component)连通分量 (Connected component) 当无向图为非连通图时，从图中某一顶点出发，一次调用深度优先搜索算法或广度优先搜索算法不可能访问到图中的所有顶点，只能访问到该顶点所在的最大连通子图（连通分量）的所有顶点。 若从无向图的每一个连通分量中的一个顶点出发进行遍历，可求得无向图的所有连通分量。 在实际求连通分量的算法中，需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍
浙公网安备 33021202002483