📄 ds7.4.1.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>第一章 绪论</title>
<meta name="Microsoft Theme" content="hounk 010">
</head>
<body background bgcolor="#000099" text="#CCCC99" link="#FF9900" vlink="#996600" alink="#FF3300">
<!--mstheme--><font face="宋体">
<p align="center"><b><span style="mso-bidi-font-size: 10.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><span style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA" lang="EN-US"><font size="6" color="#FFFF00">7.4.1<span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
</span></font></span><font size="6" color="#FFFF00"><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">无向图的连通分量和生成树</span></font></span></b></p>
<!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
<!--msthemelist--><tr>
<!--msthemelist--><td valign="baseline" width="42"><img src="aricebu1.gif" width="15" height="15" hspace="13"></td>
<td valign="top" width="100%"><!--mstheme--><font face="宋体">
<p align="left"><font color="#FFFF00"><b><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; font-size: 167%; text-shadow: auto; layout-flow: vertical; mso-color-index: 3">连通分量</span></b><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; font-size: 167%; text-shadow: auto; layout-flow: vertical; mso-color-index: 3"><b>
(Connected component)</b></span></font><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体"><p:colorscheme
colors="#FFFFFF,#0000FF,#010000,#CC3300,#FFFFCC,#FFFFCC,#CC3300,#FFFFCC"/>
<p align="left" style="text-indent: 0; margin-left: 0; margin-right: 0"><font color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:Arial;mso-fareast-font-family:宋体;
mso-hansi-font-family:Arial;font-size:133%;text-shadow:auto;layout-flow:vertical"><b>
当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访问到该顶点所在的最大连通子图</b></span><span style="font-family:Arial;mso-ascii-font-family:Arial;mso-fareast-font-family:
宋体;mso-hansi-font-family:Arial;font-size:133%;text-shadow:auto;layout-flow:
vertical"><b>(</b></span><span style="font-family:宋体;mso-ascii-font-family:
Arial;mso-fareast-font-family:宋体;mso-hansi-font-family:Arial;font-size:133%;
text-shadow:auto;layout-flow:vertical"><b>连通分量</b></span><span style="font-family:Arial;mso-ascii-font-family:Arial;mso-fareast-font-family:
宋体;mso-hansi-font-family:Arial;font-size:133%;text-shadow:auto;layout-flow:
vertical"><b>)</b></span><span style="font-family:宋体;mso-ascii-font-family:
Arial;mso-fareast-font-family:宋体;mso-hansi-font-family:Arial;font-size:133%;
text-shadow:auto;layout-flow:vertical"><b>的所有顶点。</b></span></font></p>
<p:colorscheme
colors="#FFFFFF,#0000FF,#010000,#CC3300,#FFFFCC,#FFFFCC,#CC3300,#FFFFCC"/>
<p align="left"> <span style="font-family:宋体;mso-ascii-font-family:Arial;mso-fareast-font-family:宋体;
mso-hansi-font-family:Arial;font-size:133%;text-shadow:auto;layout-flow:vertical"><b><font color="#FFFFFF">
若从无向图的每一个连通分量中的一个顶点出发进行遍历，可求得无向图的所有连通分量。</font></b></span> </p>
<p align="center"> <img border="0" src="ds7.4.1.gif" width="562" height="331"> </p>
<p align="left"><span style="font-family:宋体;mso-ascii-font-family:Arial;mso-fareast-font-family:宋体;
mso-hansi-font-family:Arial;font-size:133%;text-shadow:auto;layout-flow:vertical"><b><font color="#FFFFFF">
对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。</font></b></span></p>
<b><!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
<!--msthemelist--><tr>
<!--msthemelist--><td valign="baseline" width="42"><img src="aricebu1.gif" width="15" height="15" hspace="13"></td>
<td valign="top" width="100%"><!--mstheme--><font face="宋体"><font size="5" color="#FFFF00"><font FACE="楷体_GB2312" LANG="ZH-CN">重连通分量</font>
<font FACE="Times New Roman">(Biconnected Component)</font></font><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p style="text-indent: 0; margin-left: 0; margin-right: 0"><font color="#FFFFFF"><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">
在无向连通图</font><font FACE="Times New Roman" SIZE="5">G</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">中，当且仅当删去</font><font FACE="Times New Roman" SIZE="5">G</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">中的顶点</font><font FACE="Times New Roman" SIZE="5"><i>v</i></font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">及所有依附于</font><i><font FACE="Times New Roman" SIZE="5">v</font></i><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">的所有边后，可将图分割成两个或两个以上的连通分量，则称顶点</font><i><font FACE="Times New Roman" SIZE="5">v</font></i><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">为关节点。</font></font></p>
<p style="text-indent: 0; margin-left: 0; margin-right: 0"><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5" color="#FFFFFF">
没有关节点的连通图叫做重连通图。</font></p>
<p style="text-indent: 0; margin-left: 0; margin-right: 0"><font color="#FFFFFF"><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">
在重连通图上</font><font FACE="Times New Roman" SIZE="5">, </font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">任何一对顶点之间至少存在有两条路径</font><font FACE="Times New Roman" SIZE="5">,
</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">在删去某个顶点及与该顶点相关联的边时</font><font FACE="Times New Roman" SIZE="5">,
</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">也不破坏图的连通性。</font></font></p>
<p style="text-indent: 0; margin-left: 0; margin-right: 0"><font color="#FFFFFF"><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">
一个连通图</font><font FACE="Times New Roman" SIZE="5">G</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">如果不是重连通图，那么它可以包括几个重连通分量。</font></font></p>
<p style="text-indent: 0; margin-left: 0; margin-right: 0" align="left"><font color="#FFFFFF"><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">
在一个无向连通图</font><font FACE="Times New Roman" SIZE="5">G</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">中</font><font FACE="Times New Roman" SIZE="5">,
</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">重连通分量可以利用深度优先生成树找到。</font></font></p>
<p style="text-indent: 0; margin-left: 0; margin-right: 0" align="center"><font color="#FFFFFF"><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5"><img border="0" src="ds7.4.2.gif" width="681" height="592"></font></font></p>
</b>
<p align="center"><img border="0" src="ds7.4.3.gif" width="319" height="331"></p>
<p align="left"><font size="5" color="#FFFFFF"><b>
假设以孩子兄弟链表作生成森林的存储结构，则建立无向图的深度优先生成森林的算法如下：</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>Void
DFSForest(Graph G, CSTree &T)</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>{</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
T=NULL;</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
for(v=0;v<G.vexnum; ++V)</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
visited[v]=FALSE;</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
for(v=0;v<G.vexnum; ++v)</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
if(!visited[V])</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
{</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
p=(CSTree) malloc (Sizeof(CSNode));</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
*p={GetVex(G,v),NULL,NUll};</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
if(!T) T=p;</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
else q->nextsibling=p;</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
q=p;</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
DFSTree(G,v,p);</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
}</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>}</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>void
dfstree(graph g,int v,cstree &t)</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>{</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"> visited[v]=true;</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"> first=true;</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"> for(w=fisrtadjvex(g,v);w>=0;w=nextadjvex(g,v,w))</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF">
if(!visited[w])</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF">
{</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF">
p=(cstree)malloc(sizeof(csnode));</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF">
*p={getvex(g,w),NULL,NULL};</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF">
if(first)</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF">
{</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF">
t->lchild=p;</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF">
first=false;</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF">
}</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF">
else</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF">
{</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF">
q->nextsibling=p;</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF">
}</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF">
q=p;</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF">
dfstree(g,w,q);</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"> }</font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">}</font></b></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"> </p>
<p align="center" style="margin-top: 0; margin-bottom: 0"><b><a href="ds7.4.htm"><font size="5" color="#FFFF00">返回</font></a></b></p>
<!--mstheme--></font>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -