數(shù)據(jù)結(jié)構(gòu)教程第二十六課圖的定義與術(shù)語

教學(xué)目的： 掌握圖的定義及常用術(shù)語
    教學(xué)重點： 圖的常用術(shù)語
    教學(xué)難點： 圖的常用術(shù)語
    授課內(nèi)容：
    一、圖的定義
    圖是一種數(shù)據(jù)元素間為多對多關(guān)系的數(shù)據(jù)結(jié)構(gòu)，加上一組基本操作構(gòu)成的抽象數(shù)據(jù)類型。
    ADT Graph{
    數(shù)據(jù)對象V ：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。
    數(shù)據(jù)關(guān)系R：
    R={VR}
    VR={|v,w(-V且P(v,w),表示從v到w的弧，謂詞P(v,w)定義了弧的意義或信息}
    基本操作P：
    CreateGraph(&G,V,VR);
    初始條件：V是圖的頂點集，VR是圖中弧的集合。
    操作結(jié)果：按V和VR的定義構(gòu)造圖G
    DestroyGraph(&G);
    初始條件：圖G存在
    操作結(jié)果：銷毀圖G
    LocateVex(G,u);
    初始條件：圖G存在，u一G中頂點有相同特征
    操作結(jié)果：若G中存在頂點u, 則返回該頂點在圖中位置；否則返回其它信息。
    GetVex(G,v);
    初始條件：圖G存在，v是G中某個頂點
    操作結(jié)果：返回v的值。
    PutVex(&G,v,value);
    初始條件：圖G存在，v是G中某個頂點
    操作結(jié)果：對v賦值value
    FirstAdjVex(G,v);
    初始條件：圖G存在，v是G中某個頂點
    操作結(jié)果：返回v的第一個鄰接頂點。若頂點在G中沒有鄰接頂點，則返回“空”
    NextAdjVex(G,v,w);
    初始條件：圖G存在,v是G中某個頂點,w是v的鄰接頂點。
    操作結(jié)果：返回v的（相對于w的）下一個鄰接頂點。若w是v的后一個鄰接點，則返回“空”