第7章圖(基礎知識)習題練習答案

在圖所示的各無向圖中

　　　　

　()找出所有的簡單環
　()哪些圖是連通圖?對非連通圖給出其連通分量
　()哪些圖是自由樹(或森林)?

答:
　()所有的簡單環(同一個環可以任一頂點作為起點)
　　　(a)
　　　(b)無
　　　(c)
　　　(d)無

　()連通圖
　　　(a)(c)(d)是連通圖
　　　(b)不是連通圖因為從到沒有路徑具體連通分量為
　　　　　

　()自由樹(森林)自由樹是指沒有確定根的樹無回路的連通圖稱為自由樹
　　　(a)不是自由樹因為有回路
　　　(b)是自由森林其兩個連通分量為兩棵自由樹
　　　(c)不是自由樹
　　　(d)是自由樹

在圖(下圖)所示的有向圖中
　　　
　　　　　
　() 該圖是強連通的嗎? 若不是則給出其強連通分量
　() 請給出所有的簡單路徑及有向環
　() 請給出每個頂點的度入度和出度
　() 請給出其鄰接表鄰接矩陣及逆鄰接表

答
　()該圖是強連通的所謂強連通是指有向圖中任意頂點都存在到其他各頂點的路徑

　()簡單路徑是指在一條路徑上只有起點和終點可以相同的路徑
　　有vvvvvvvvvvvvvvvvvvvvvvvvvvvv另包括所有有向環有向環如下
　　　　　vvvvvvvv(這兩個有向環可以任一頂點作為起點和終點)

　()每個頂點的度入度和出度
　　　D(v)=　 ID(v)=　 OD(v)=
　　　D(v)= 　ID(v)=　 OD(v)=
　　　D(v)= 　ID(v)=　 OD(v)=
　　　D(v)= 　ID(v)=　 OD(v)=

　()鄰接表(注意邊表中鄰接點域的值是頂點的序號這裡頂點的序號是頂點的下標值)
   vertex firstedge  next
　　　┌─┬─┐  ┌─┬─┐  ┌─┬─┐
　 　│v│　─→│ │　─→│ │∧│
      ├─┼─┤  ├─┼─┤  └─┴─┘
     │v│　─→│ │∧│
      ├─┼─┤  ├─┼─┤
     │v│　─→│ │∧│
      ├─┼─┤  ├─┼─┤
     │v│　─→│ │∧│
      └─┴─┘  └─┴─┘

  逆鄰接表
    ┌─┬─┐  ┌─┬─┐
   │v│　─→│ │∧│
    ├─┼─┤  ├─┼─┤
   │v│　─→│ │∧│
    ├─┼─┤  ├─┼─┤  ┌─┬─┐
   │v│　─→│ │　─→│ │∧│
    ├─┼─┤  ├─┼─┤  └─┴─┘
   │v│　─→│ │∧│
    └─┴─┘  └─┴─┘

  鄰接矩陣
   
   
   
   

假設圖的頂點是AB請根據下述的鄰接矩陣畫出相應的無向圖或有向圖

　　　　　　　　 ┌　　　　┓
  ┌       ┓   | |
  | |   | | 
  | |   | | 
  | |   | | 
  | |   | |
  ┕       ┙　 ┕　       ┙
      (a)               (b) 

答:
   

假設一棵完全二叉樹包括ABC等七個結點寫出其鄰接表和鄰接矩陣

解
  鄰接表如下

　　┌─┬─┐  ┌─┬─┐  ┌─┬─┐
　 │A │　─→│ │  ─→│ │∧│
    ├─┼─┤  ├─┼─┤  ├─┼─┤  ┌─┬─┐
   │B │　─→│ │　─→│ │　─→│ │∧│
    ├─┼─┤  ├─┼─┤  ├─┼─┤  ├─┼─┤
   │C │　─→│ │　─→│ │　─→│ │∧│
    ├─┼─┤  ├─┼─┤  └─┴─┘  └─┴─┘
   │D │　─→│ │∧│
    ├─┼─┤  ├─┼─┤
   │E │　─→│ │∧│
    ├─┼─┤  ├─┼─┤
   │F │　─→│ │∧│
    ├─┼─┤  ├─┼─┤
   │G │　─→│ │∧│
    └─┴─┘  └─┴─┘

  鄰接矩陣如下
       
       
         
       
         
       
       

對n個頂點的無向圖和有向圖采用鄰接矩陣和鄰接表表示時如何判別下列有關問題?

  () 圖中有多少條邊?
  ()任意兩個頂點i和j是否有邊相連?
  () 任意一個頂點的度是多少?

答
    對於n個頂點的無向圖和有向圖用鄰接矩陣表示時

  ()設m為矩陣中非零元素的個數 
　　　無向圖的邊數=m/
　　　有向圖的邊數=m

　()無論是有向圖還是無向圖在矩陣中第i行第j列的元素若為非零值則該兩頂點有邊相連

　()對於無向圖任一頂點i的度為第i行中非零元素的個數
　　對於有向圖任一頂點i的入度為第i列中非零元素的個數出度為第i行中非零元素的個數度為入度出度之和

　　當用鄰接表表示時

　()對於無向圖圖中的邊數=邊表中結點總數的一半
　　　對於有向圖圖中的邊數=邊表中結點總數

　()對於無向圖任意兩頂點間是否有邊相連可看其中一個頂點的鄰接表若表中的adjvex域有另一頂點位置的結點則表示有邊相連
　　　對於有向圖則表示有出邊相連

　()對於無向圖任意一個頂點的度則由該頂點的邊表中結點的個數來決定
　　對於有向圖任意一個頂點的出度由該頂點的邊表中結點的個數來決定入度則需遍歷各頂點的邊表(用逆鄰接表可容易地得到其入度)

n個頂點的連通圖至少有幾條邊?強連通圖呢?

答
　　n個頂點的連通圖至少有n條邊強連通圖至少有(n)條邊

DFS和BFS遍歷各采用什麼樣的數據結構來暫存頂點?當要求連通圖的生成樹的高度最小應采用何種遍歷?

答
　　DFS遍歷采用棧來暫存頂點BFS采用隊列來暫存頂點當要求連通圖的生成樹的高度最小時應采用BFS遍歷

畫出以頂點v為初始源點遍歷圖（下圖）所示的有向圖所得到的DFS 和BFS生成森林

　　　　

答

　　

按順序輸入頂點對()()()()()()()()()()()根據第節中算法CreatALGraph畫出相應的鄰接表並寫出在該鄰接表上從頂點開始搜索所得的DFS和BFS序列及DFS和BFS生成樹 

答
　　相應的鄰接表如下

　　 ┌─┬─┐  ┌─┬─┐  ┌─┬─┐  ┌─┬─┐  ┌─┬─┐  ┌─┬─<
From:http://tw.wingwit.com/Article/program/sjjg/201311/23765.html