ds7.1.2.htm

这是清华大学所用的数据结构的电子版教材

mso-hansi-font-family:&quot;Times New Roman&quot;">）依附于顶点</span><span lang="EN-US">vi</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">与顶点</span><span lang="EN-US">vj</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">；弧用顶点的有序偶对</span><span lang="EN-US">&lt;vi, 
      vj&gt;</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">来表示，有序偶对的第一个结点</span><span lang="EN-US">vi</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">被称为始点（或</font><font size="5" color="#FFFF00">弧尾</font><font size="5" color="#FFFFFF">），在图中就是不带箭头的一端；有序偶对的第二个结点</font></span><font size="5" color="#FFFFFF"><span lang="EN-US">vj</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">被称为终点（或</font><font size="5" color="#FFFF00">弧头</font><font size="5" color="#FFFFFF">），在图中就是带箭头的一端。</font></span></b><!--mstheme--></font><!--msthemelist--></td>
  </tr>
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p class="MsoNormal"><b><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;"><font size="5" color="#FFFF00">无向完全图</font><font size="5" color="#FFFFFF">:在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以证明，在一个含有</font></span><font size="5" color="#FFFFFF"><span lang="EN-US">n</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">个顶点的无向完全图中，有</span><span lang="EN-US">n(n-1)/2</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">条边。</span></font></b><!--mstheme--></font><!--msthemelist--></td>
  </tr>
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p class="MsoNormal"><b><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;"><font size="5" color="#FFFF00">有向完全图</font><font size="5" color="#FFFFFF">:在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有</font></span><font size="5" color="#FFFFFF"><span lang="EN-US">n</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">个顶点的有向完全图中，有</span><span lang="EN-US">n(n-1)</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">条边。</span></font></b><!--mstheme--></font><!--msthemelist--></td>
  </tr>
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p class="MsoNormal"><b><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;"><font size="5" color="#FFFF00">稠密图、稀疏图</font><font size="5" color="#FFFFFF">:若一个图接近完全图，称为稠密图；称边数很少的图为稀疏图。</font></span></b><!--mstheme--></font><!--msthemelist--></td>
  </tr>
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p class="MsoNormal"><b><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;"><font size="5" color="#FFFF00">顶点的度、入度、出度</font><font size="5" color="#FFFFFF">:顶点的</font><font size="5" color="#FFFF00">度</font><font size="5" color="#FFFFFF">（</font></span><font size="5" color="#FFFFFF"><span lang="EN-US">degree</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">）是指依附于某顶点</span><span lang="EN-US">v</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">的边数，通常记为</span><span lang="EN-US">TD 
      (v)</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">。在有向图中，要区别顶点的入度与出度的概念。顶点</span><span lang="EN-US">v</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">的</font><font size="5" color="#FFFF00">入度</font><font size="5" color="#FFFFFF">是指以顶点</font></span><font size="5" color="#FFFFFF"> 
      <span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">为终点的弧的数目。记为</span><span lang="EN-US">ID 
      (v)</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">；顶点</span><span lang="EN-US">v</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;"></span></font><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;"><font size="5" color="#FFFF00">出度</font><font size="5" color="#FFFFFF">是指以顶点</span><span lang="EN-US">v</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">为始点的弧的数目，记为</span><span lang="EN-US">OD 
      (v)</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">。有</span><span lang="EN-US">TD (v)=ID (v)</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">＋</span><span lang="EN-US">OD (v)</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">。</span></font></b><!--mstheme--></font><!--msthemelist--></td>
  </tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体"><b><font size="5" color="#FFFFFF"><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><span lang="EN-US" 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">G1</span><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></b>
<p class="MsoNormal" style="text-indent: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font size="5" color="#FFFFFF"><b>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
TD(v1)=2<span style="mso-spacerun: yes">&nbsp;&nbsp; </span>TD(v2)=3<span style="mso-spacerun: yes">&nbsp;&nbsp; 
</span>TD(v3)=3<span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;</span></b></font></span></p>
<p class="MsoNormal" style="text-indent: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font size="5" color="#FFFFFF"><b>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
TD(v4)=2<span style="mso-spacerun: yes">&nbsp;&nbsp; </span>TD(v5)=2</b></font></span></p>
<p class="MsoNormal" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><span style="font-family:宋体;
mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;"><font color="#FFFFFF"><b><font size="5">在</font></b></font></span><font color="#FFFFFF"><b><font size="5"><span lang="EN-US">G2</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">中有：</span></font></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font size="5" color="#FFFFFF"><b><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
</span>ID(v1)=1<span style="mso-spacerun: yes">&nbsp; &nbsp;</span>OD(v1)=2 <span style="mso-spacerun:
yes">&nbsp;</span><span style="mso-spacerun: yes">&nbsp;</span>TD(v1)=3</b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun:
yes"><font color="#FFFFFF"><b><font size="5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
</font></b></font></span><font color="#FFFFFF"><b><font size="5">ID(v2)=1<span style="mso-spacerun: yes">&nbsp;&nbsp;