要求寫出圖的存儲結構定義

Ⅰ 圖的存儲結構有多少種

1、鄰接矩陣：邏輯結構分為兩部分：V和E集合。因此，用一個一維數組存放圖中所有頂點數據；用一個二維數組存放頂點間關系的數據，這個二維數組稱為鄰接矩陣。鄰接孝答矩陣又分為有向圖鄰接矩陣和無向圖鄰接巧畢慧矩陣。

2、鄰接表：是由單鏈表的表頭形成的頂點表和單鏈表其餘結點形成的邊表兩部分組成。

3、十字鏈表：是有向圖數基的另一種鏈式存儲結構。該結構可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的。

4、鄰接多重表：主要用於存儲無向圖。

Ⅱ 圖的存儲結構

鄰接矩陣:
有向圖的鄰接矩陣
具有n個頂點的有向圖可以用一個n′n的方形矩陣表示。假設該矩陣的名稱為M，則當<vi,vj>是該有向圖中的一條弧時，M[i,j]=1；否則M[i,j]=0。第i個頂點的出度為矩陣中第i行中"1"的個數；入度為第i列中"1"的個數，並且有向圖弧的條數等於矩陣中"1"的個數。
無向圖的鄰接矩陣
具有n個頂點的無向圖也可以用一個n′n的方形矩陣表示。假設該矩陣的名稱為M，則當（vi,vj）是該無向圖中的一條邊時，M[i,j]=M[j,i]=1；否則，M[i,j]=M[j,j]=0。第i個頂點的度為矩陣中第i 行中"1"的個數或第i列中"1"的個數。圖中邊的數目等於矩陣中"1"的個數的一半，這是因為每條邊在矩陣中描述了兩次。
在C 語言中，實現鄰接矩陣表示法的類型定義如下所示： #defineMAX_VERTEX_NUM20typedefstructgraph{Elemtypeelem[MAX_VERTEX_NUM][MAX_VERTEX_NUM];intn;}Graph;鄰接表
邊結點的結構為：
adjvex是該邊或弧依附的頂點在數組中的下標，next是指向下一條邊或弧結點的指針
elem是頂點內容，firstedge是指向第一條邊或弧結點的指針。
在C語言中，實現鄰接表表示法的類型定義如下所示： #defineMAX_VERTEX_NUM30//最大頂點個數typestructEdgeLinklist{//邊結點intadjvex;structEdgeLinklist*next;}EdgeLinklist;typedefstructVexLinklist{//頂點結點Elemtypeelem;EdgeLinklist*firstedge;}VexLinklist,AdjList[MAX_VERTEX_NUM];創建有向圖和無向圖鄰接表的演算法實現：
（1） 創建有向圖鄰接表 voidCreate_adj(AdjListadj,intn){for(i=0;i<n;i++){//初始化頂點數組scanf(&adj.elem);adj.firstedge=NULL;}scanf(&i,&j);//輸入弧while(i){s=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));//創建新的弧結點s->adgvex=j-1;s->next=adj[i-1].firstedge;//將新的弧結點插入到相應的位置adj[i-1].firstegde=s;scanf(&i,&j);//輸入下一條弧}}（2）創建無向圖的鄰接表 voidCreate_adj(AdjListadj,intn){for(i=0;i<n;i++){//初始化鄰接表scanf(&adj.elem);adj.firstedge=NULL;}scanf(&i,&j);//輸入邊while(i){s1=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));s1->adgvex=j-1;s2=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));s2->adgvex=i-1;s1->next=adj[i-1].firstedge;adj[i-1].firstegde=s1;s2->next=adj[j-1].firstedge;adj[j-1].firstegde=s2;scanf(&i,&j);}}

Ⅲ 圖的存儲結構是什麼

由於圖的結構比較復雜，任意兩個頂點之間都可能存在關系（邊），無法通過存儲位置表示這種任意的邏輯關系，所以，圖無法採用順序存儲結構。這一點同其他數據結構（如線性表、樹）不同。考慮圖的定義，圖是由頂點和邊組成的，所以，分別考慮如何存儲頂點和邊。圖常用的存儲結構有鄰接矩陣、鄰接表、十字鏈表和鄰接多重表。

Ⅳ 圖的存儲結構——所存儲的信息有哪些

一、鄰接矩陣存儲方法

鄰接矩陣是表示頂點之間相鄰關系的矩陣。

設G=(V，E)是具有n（n＞0）個頂點的圖，頂點的順序依次為0～n-1，則G的鄰接矩陣A是n階方陣，其定義如下：

（1）如果G是無向圖，則：

A[i][j]=1：若(i,j)∈E(G) 0:其他

（2）如果G是有向圖，則：

A[i][j]=1：若<i,j>∈E(G) 0:其他

（3）如果G是帶權無向圖，則：

A[i][j]= wij ：若i≠j且(i,j)∈E(G) 0：i=j ∞：其他

（4）如果G是帶權有向圖，則：

A[i][j]= wij ：若i≠j且<i,j>∈E(G) 0：i=j∞：其他

注意：帶權圖和不帶權圖表示的元素類型不同。

帶權圖（不論有向還是無向圖）A[i][j]用double表示，不帶權圖（不論有向還是無向圖）A[i][j]用int表示。

用一維數組G[ ]存儲有4個頂點的無向圖如：G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }

則頂點2和頂點0之間是有邊的。

如：

鄰接矩陣的特點如下：

（1）圖的鄰接矩陣表示是唯一的。

（2）無向圖的鄰接矩陣一定是一個對稱矩陣。因此，按照壓縮存儲的思想，在具體存放鄰接矩陣時只需存放上（或下）三角形陣的元素即可。

（3）不帶權的有向圖的鄰接矩陣一般來說是一個稀疏矩陣。因此，當圖的頂點較多時，可以採用三元組表的方法存儲鄰接矩陣。

（4）對於無向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數正好是第i個頂點的度。

（5）對於有向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數正好是第i個頂點的出度（或入度）。

（6）用鄰接矩陣方法存儲圖，很容易確定圖中任意兩個頂點之間是否有邊相連。但是，要確定圖中有多少條邊，則必須按行、按列對每個元素進行檢測，所花費的時間代價很大。這是用鄰接矩陣存儲圖的局限性。

鄰接矩陣的數據類型定義如下：

#define MAXV <最大頂點個數>

typedef struct

{ int no; //頂點編號

InfoType info; //頂點其他信息

} VertexType; //頂點類型

typedef struct //圖的定義

{ int edges[MAXV][MAXV]; //鄰接矩陣

int n，e; //頂點數，弧數

VertexType vexs[MAXV]; //存放頂點信息

} MGraph; //圖的鄰接矩陣表示類型

二、 鄰接表存儲方法

圖的鄰接表存儲方法是一種順序分配與鏈式分配相結合的存儲方法。

在鄰接表中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中的節點表示依附於頂點i的邊（對有向圖是以頂點i為尾的邊）。每個單鏈表上附設一個表頭節點。

其中，表節點由三個域組成，adjvex指示與頂點i鄰接的點在圖中的位置，nextarc指示下一條邊或弧的節點，info存儲與邊或弧相關的信息，如權值等。

表頭節點由兩個域組成，data存儲頂點i的名稱或其他信息，firstarc指向鏈表中第一個節點。

typedef struct ANode

{ int adjvex; //該邊的終點編號

struct ANode *nextarc; //指向下一條邊的指針

InfoType info; //該邊的相關信息

} ArcNode; //邊表節點類型

typedef struct Vnode

{ Vertex data; //頂點信息

ArcNode *firstarc; //指向第一條邊

} VNode; //鄰接表頭節點類型

typedef VNode AdjList[MAXV]; //AdjList是鄰接表類型

typedef struct

{ AdjList adjlist; //鄰接表

int n,e; //圖中頂點數n和邊數e

} ALGraph; //完整的圖鄰接表類型

鄰接表的特點如下：

（1）鄰接表表示不唯一。這是因為在每個頂點對應的單鏈表中，各邊節點的鏈接次序可以是任意的，取決於建立鄰接表的演算法以及邊的輸入次序。

（2）對於有n個頂點和e條邊的無向圖，其鄰接表有n個頂點節點和2e個邊節點。顯然，在總的邊數小於n(n-1)/2的情況下，鄰接表比鄰接矩陣要節省空間。

（3）對於無向圖，鄰接表的頂點i對應的第i個鏈表的邊節點數目正好是頂點i的度。

（4）對於有向圖，鄰接表的頂點i對應的第i個鏈表的邊節點數目僅僅是頂點i的出度。其入度為鄰接表中所有adjvex域值為i的邊節點數目。

例， 給定一個具有n個節點的無向圖的鄰接矩陣和鄰接表。

（1）設計一個將鄰接矩陣轉換為鄰接表的演算法；

（2）設計一個將鄰接表轉換為鄰接矩陣的演算法；

（3）分析上述兩個演算法的時間復雜度。

解：

（1）在鄰接矩陣上查找值不為0的元素，找到這樣的元素後創建一個表節點並在鄰接表對應的單鏈表中採用前插法插入該節點。

void MatToList(MGraph g，ALGraph *&G)

//將鄰接矩陣g轉換成鄰接表G

{ int i，j，n=g.n; ArcNode *p; //n為頂點數

G=(ALGraph *)malloc(sizeof(ALGraph));

for (i=0;i<n;i++) //給所有頭節點的指針域置初值

G->adjlist[i].firstarc=NULL;

for (i=0;i<n;i++) //檢查鄰接矩陣中每個元素

for (j=n-1;j>=0;j--)

if (g.edges[i][j]!=0)

{ p=(ArcNode *)malloc(sizeof(ArcNode));

//創建節點*p

p->adjvex=j;

p->nextarc=G->adjlist[i].firstarc;

//將*p鏈到鏈表頭

G->adjlist[i].firstarc=p;

}

G->n=n;G->e=g.e;

}

（2）在鄰接表上查找相鄰節點，找到後修改相應鄰接矩陣元素的值。

void ListToMat(ALGraph *G，MGraph &g)

{ int i，j，n=G->n;ArcNode *p;

for (i=0;i<n;i++)

{ p=G->adjlist[i].firstarc;

while (p!=NULL)

{ g.edges[i][p->adjvex]=1;

p=p->nextarc;

}

}

g.n=n;g.e=G->e;

}

（3）演算法1的時間復雜度均為O(n2)。演算法2的時間復雜度為O(n+e)，其中e為圖的邊數。

Ⅳ 圖的定義與存儲

圖狀結構是一種比樹形結構更復雜的非線性結構。在樹形結構中，結點間具有分支層次關系，每一層上的結點只能和上一層的至多一個結點相關，但可能和下一層的多個結點相關。而在圖狀結構中，任意兩個結點之間都可能相關，即結點之間的鄰接關系可以是任意的。因此，圖是 比樹更一般、更復雜的非線性結構，常被用於描述各種復雜的數據對象，在自然科學、社會科學和人文科學等許多領域有著非常廣泛的應用。

圖（Graph）是由非空的頂點集合和一個描述頂點之間的關系——邊（或者弧）的集合組成的，其形式化定義為：G=(V,E)、V={v1|v1包含data object}、E={(v1,vj)|(vi,vj 包含V^P(vj,vj)。其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合，集合E中P(vi,vj)表示頂點vi和頂點vj之間有一條直接連線，即偶對(v1,vj）表示一條邊。如：G2=(V2,E2)、V2={v1,v2,v3,v4}、E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。

1、無向圖：在一個圖中，如果任意兩個頂點構成的偶對(vi,vj）包含E是無序的，即頂點之間的連線是沒有方向的，則稱該圖為無向圖。

2、有向圖：在一個圖中，如果任意兩個頂點構成的偶對<vj,vj>包含E是有序的（有序對常常用尖括弧「<>」表示），即頂點之間的連線是有方向的，則稱該圖為有向圖。

6、頂點的度、入度、出度：頂點的度（Degree）是指依附於某頂點v的邊數，通常記為TD(v)。頂點v的入度是指以頂點v為終點的弧的數目，記為ID(V)；出度是指以頂點v為始點的弧的數目，記為OD(V)。有TD(V)=ID(v)+OD(v)。

7、邊的權、網：與邊有關的數據信息稱為權(Weight)。在實際應用中，權值可以有某種含義。例如，在一個反映城市交通線路的圖中，邊上的權值可以表示該條線路的長度或等級；對於一個電子線路圖，邊上的權值可以表示兩個端點之間的電阻、電流或電壓值；對於反映工程進度的圖而言，邊上的權值可以表示從前一個工程到後一個工程所需要的時間或其他代價等。邊上帶權的圖稱為網或網路（network）。

8、路徑、路徑長度：頂點vp到頂點vq之間的路徑（path）是指頂點序列vp、vi1、vi2、···、vim、vq。其中，（vp，vi1）、（vi1，vi2）、···、（vim，vq）分別為圖中的邊。路徑上邊的數目稱為路徑長度。

9、簡單路徑、迴路、簡單迴路：序列中頂點不重復出現的路徑稱為簡單路徑。路徑中第一個頂點與最後一個頂點相同的 路徑稱為迴路或環（Cycle）。除第一個頂點與最後一個頂點之外，其他頂點不重復出現的迴路稱為簡單迴路，或者簡單環。

10、子圖：對於圖G=（V，E），G'=（V',E'），若存在 V'是V的子集， E'是E的子集，則稱圖 G'是G的的一個子圖。

11、連通、連通圖、連通分量：在無向圖中，如果從一個頂點vi到另一個頂點vj(i=!j)存在路徑，則稱頂點vi和vj是連通的。如果圖中任意兩個頂點都是連通的，則稱該圖是連通圖。無向圖的極大連通子圖稱為連通分量，極大連通子圖是指在保證連通與子圖的條件下，包含原圖中所有的頂點與邊。 如下圖：

12、強連通圖、強連通分量：對於有向圖來說，若圖中任意一對頂點vi和vj（i=!j）均存在從一個頂點vi到另一個頂點vj和從vj到vi的路徑，則稱該有向圖是強連通圖。有向圖的極大強連通子圖稱為強連通分量，極大強連通子圖的含義同上。

13、生成樹：所謂連通圖G的生成樹，是G的包含其全部n個頂點的一個極小連通子圖，所謂極小連通子圖是指在包含所有頂點且保證連通的前提下盡可能少地包含原圖中的邊。生成樹必定包含且僅包含連通圖G的n-1條邊。在生成樹中添加任意一條屬於原圖中的邊必定會產生迴路，因為新添加的邊使其所依附的兩個頂點之間有了第二條路徑。若生成樹中減少任意一條邊，則必然成為非連通的。

14、生成森林：在非連通圖中，由每個連通分量都可得到一個極小連通子圖，即一棵生成樹。這些連通分量的生成樹就組成了一個非連通圖的生成森林。

將上圖存儲到計算機中，請設計一個數據結構並將其合理存儲起來？

所謂鄰接矩陣（Adjacency Matrix）的存儲結構，就是用一維數組存儲圖中的頂點信息，用矩陣表示圖中各頂點的信息，用矩陣表示圖中各頂點的信息，用矩陣表示圖中各頂點之間的鄰接關系。假設圖G=(V,E)有n個確定的頂點，即V ={v0,v1，···，vn-1}，則表示G中各頂點相鄰關系的矩陣為一個n×n的矩陣，矩陣的元素為：

A[i][j]={1,若(vi,vj)或<vi,vj>是E(G)中的邊 ；2，若(vi,vj）或<vi,vj>不是E(G)中的邊。

若G是網，則鄰接矩陣可定義為：

A[i][j]={wij,若(vi,vj)或<vi,vj>是E(G)中的邊 ；0或&，若(vi,vj）或<vi,vj>不是E(G)中的邊。

（1）無向圖的鄰接矩陣一定是一個對稱矩陣。因此，在具體存放鄰接矩陣時只需存放上或下三角矩陣的元素即可。

（2）對於無向圖，鄰接矩陣的第i行或第i列非零元素或非&元素的個數正好是第i個頂點的度TD(vi)。

（3）對於有向圖，鄰接矩陣的第i行貨第i列非零元素或非&元素的個數正好是第i個頂點的出度OD(vi)或如度ID(vi)。

（4）用鄰接矩陣方法存儲圖，很容易確定圖中任意兩個頂點之間是否有邊相連；但是，要確定圖中有多少條邊，則必須按行、按列對每個元素進行檢測，所花費的時間代價很大。這是用鄰接矩陣存儲圖的局限性。

在實際應用鄰接矩陣存儲圖時，除了用一個二維數組存儲用於表示頂點間相鄰關系的鄰接矩陣外，還需用一個一維數組來存儲頂點信息，另外，還有圖的頂點樹和邊樹。故可將其形式描述如下：

鄰接表（Adjacency List）是圖的一種順序存儲於鏈式存儲結合的存儲方法。鄰接表表示法類似於樹的孩子鏈表表示法。就是對於圖G中的每個頂點vi，將所有鄰接於vi的頂點vj鏈成一個單鏈表，這個單鏈表就稱為頂點vi的鄰接表，再將所有頂點的鄰接表表頭放到數組中，就構成了圖鄰接表。

在鄰接表表示中有兩種結點結構：一種是頂點表的結點結構，它由頂點域（vertex）和指向第一條鄰接邊的指針域（firstedge）構成。另一種是邊表即鄰接表結點，它由鄰接點域（adjvex）和指向下一條鄰接邊的指針域（next）構成。對於網的邊表需再增設一個存儲邊上的信息（如權值等）的域（info）。

Ⅵ 有關圖的存儲結構

(1)順序存儲方法
該方法把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現。
由此得到的存儲表示稱為順序存儲結構 (Sequential Storage Structure)，通常藉助程序語言的數組描述。
該方法主要應用於線性的數據結構。非線性的數據結構也可通過某種線性化的方法實現順序存儲。 (2)鏈接存儲方法
該方法不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系由附加的指針欄位表示。由此得到的存儲表示稱為鏈式存儲結構(Linked Storage Structure),通常藉助於程序語言的指針類型描述。

Ⅶ 圖的三種存儲結構

設圖G有n (n 1) 個頂點，則鄰接矩陣是一個n階方陣。
當矩陣中的 [i,j] !=0（下標從1開始） ,代表其對應的第i個頂點與第j個頂點是連接的。

為圖G中的每一個頂點建立一個單鏈表，每條鏈表的結點元素為與該頂點連接的頂點。

可以看成是有向圖的鄰接表和逆鄰接表結合起來的一種鏈表。

Ⅷ 圖的五種存儲結構

圖的鄰接矩陣（Adjacency Matrix）： 圖的鄰接矩陣用兩個數組來表示圖。一個一維數組存儲圖中頂點信息，另一個二維數組（一般稱之為鄰接矩陣）來存儲圖中的邊或者弧的信息。從鄰接矩陣中我們自然知道一個頂點的度（對於無向圖）或者有向圖中一個頂點的入度出度信息。

假設圖G有n個頂點，則鄰接矩陣是一個n*n的方陣。
1.對於如果圖上的每條邊不帶權值來說，那麼我們就用真（一般為1）和假（一般為0）來表示一個頂點到另一個頂點存不存在邊。下面是一個圖的鄰接矩陣的定義：

鄰接矩陣法實現帶權值的無向圖的創建如下：

按照如圖輸入各邊（不重復）

測試程序如下：

結果可得該矩陣，證明創建樹成功。 假設n個頂點e條邊的創建，createGraph演算法的時間復雜度為O（n+n*n+e）。如果需要創建一個有向圖，那麼和上面一樣一個一個錄入邊下標和權值。

鄰接矩陣這種存儲結構的優缺點： 缺點是對於邊數相對頂點較少的稀疏圖來說會存在極大的空間浪費。假設有n個頂點,優點是對於有向完全圖和無向完全圖來說鄰接矩陣是一種不錯的存儲結構，浪費的話也只浪費了n個頂點的容量。

在樹的存儲結構一節中我們提到對於孩子表示法的第三種：用一段連續的存儲單元（數組）存儲樹中的所有結點，利用一個單鏈表來存儲數組中每個結點的孩子的信息。對於圖的存儲結構來說，我們也可以利用這種方法實現圖的存儲

鄰接表(Adjacency List): 這種數組與鏈表相結合的存儲方法叫做鄰接表。1.為什麼不也用單鏈表存儲圖的結點信息呢？原因就是數組這種順序存儲結構讀取結點信息速率快。對於頂點數組中，每個數據元素還需要存儲一個指向第一個鄰接頂點的指針，這樣才可以查找邊的信息2.圖中每個頂點Vi(i > 0)的所有鄰接點構成一個線性表 （在無向圖中這個線性表稱為Vi的邊表，有向圖中稱為頂點作為弧尾的出邊表） ，由於鄰接點的不確定性，所以用鏈表存儲，有多少個鄰接點就malloc一個空間存儲鄰接點，這樣更不會造成空間的浪費（與鄰接矩陣相比來說）。3.對於鄰接表中的某個頂點來說，用戶關心的是這個頂點的鄰接點，完全可以遍歷用單鏈表設計成的邊表或者出邊表得到，所以沒必要設計成雙鏈表。

鄰接表的存儲結構：
假設現在有一無向圖G，如下圖：

從鄰接表結構中，知道一個頂點的度或者判斷兩個頂點之間是否存在邊或者求一個頂點的所有鄰接頂點是很容易的。

假設現在有一有向圖G，如下圖：

無向圖的鄰接表創建示例如下：

假設在上圖（無向圖）中的V0V1V2V3頂點值為ABCD，則依據下面測試程序可得結果：

鄰接表的優缺點： 優點是：鄰接表存儲圖，既能夠知道一個頂點的度和頂點的鄰接結點的信息，並且更不會造成空間的浪費。缺點是鄰接表存儲有向圖時，如果關心的是頂點的出度問題自然用鄰接表結構，但是想了解入度需要遍歷圖才知道（需要考慮逆鄰接表）。

十字鏈表(Orthogonal List) ：有向圖的一種存儲方法，它把鄰接表和逆鄰接表結合起來，因此在十字鏈表結構中可以知道一個頂點的入度和出度情況。
重新定義頂點表的結點如下圖：

現在有一有向圖如下圖：

則它的存儲結構示意圖為：

其定義如下：

十字鏈表是用來存儲有向圖的，這樣可以看出一個頂點的出入度信息。對於無向圖來說完全沒必要用十字鏈表來存儲。

在無向圖中，因為我們關注的是頂點的信息，在考慮節約空間的情況下我們利用鄰接表來存儲無向圖。但是如果我們關注的是邊的信息，例如需要刪除某條邊對於鄰接表來說是挺繁瑣的。它需要操作兩個單鏈表刪除兩個結點。因此我們仿照十字鏈表的方式對邊表結點結構重新定義如下圖：

它的鄰接多重表結構為：

多重鄰接表的優點：對於邊的操作相比於鄰接表來說更加方便。比如說我們現在需要刪除(V0,V2)這條邊，只需將69步驟中的指針改為nullptr即可。

邊集數組(edgeset array)： 邊集數組是由兩個數組組成，一個存儲頂點信息，另一個存儲邊的信息，這個邊數組中的每個數據元素由起點下標，終點下標，和權組成（如果邊上含有權值的話）。
邊數組結構如下圖：

邊集數組實現圖的存儲的優缺點：優點是對於邊的操作方便快捷，操作的只是數組元素。比如說刪除某條邊，只需要刪除一個數組元素。缺點是：對於圖的頂點信息，我們只有遍歷整個邊數組才知道，這個費時。因此對於關注邊的操作來說，邊集數組更加方便。

Ⅸ 圖的兩種存儲結構是什麼

二樓說錯了，方向有誤。
這兩個分別叫剖面符號和斷面符號，他們剖段的方向都是縱向的，觀察的方向是指向數字的方向，從網頁上來看，就是L1是從左往右，而1┃則表示從右往左看。

這兩種符號的區別是斷面圖與剖面圖的區別在於：
斷面圖只畫形體被剖開後斷面的投影，而剖面圖要畫出形體被剖開後整個餘下部分的投影如圖。

1)剖面圖是形體剖切之後剩下部分的投影，是體的投影。斷面圖是形體剖切之後斷面的投影，是面的投影。 剖面圖中包含斷面圖。

2)剖面圖用剖切位置線、投射方向線和編號來表示。斷面圖則只畫剖切位置線與編號，用編號的注寫位置來代表投射方向。

3)剖面圖可用兩個或兩個以上的剖切平面進行剖切，斷面圖的剖切平面通常只能是單一的。

Ⅹ 圖-圖頂點與邊的關系-圖的存儲結構

圖：

定義：由頂點的有窮非空集合和頂點之間邊春森的集合組成，通常表示為G(V,E)，其中，G表示一個圖，V是圖中頂點的集合，E是G中邊的集合

數據元素：線性表-元素，樹-結點，表-頂點

沒有數據元素：空表、空樹、有窮非空

關系：線性表-相鄰元素線性關系，樹-相鄰兩層層次關系，圖-任意兩個定點都可能有關系

無向邊：頂點Vj和Vi之間的邊沒有方向；無序偶（Vi,Vj）來表示

有向邊（弧）頂點Vj和Vi之間的邊有方向；有序偶<Vi,Vj>表示，<弧尾，弧頭>，尾->頭

簡單圖：圖中不存在頂點到其自身的邊，且同一條邊不重復出現

無向完全圖：無向圖中，任意兩個頂點之間都存在邊；邊數：n*(n-1)/2

有向完全圖：有向圖中，任意兩個頂點之間都存在相反的兩條弧；邊數：n*(n-1)

稀疏圖和稠密圖：相對的，邊或弧長以n*logn（n是頂點個數）區分

網：帶權的圖

子圖：兩個圖G1=(V1,E1)，G2=(V2,E2),有V1是V2的子集，且E1是E2的子集，則G1是G2的子圖

圖的頂點與邊之間的關系：

鄰接點：頂點V1和V2，邊（V1,V2）屬於E；邊依附於兩個頂點，或是說邊與兩個頂點相關聯

度：與頂點V相關聯的邊的數目，記為TD(V)

對於有向圖--V1鄰接到V2--入讀ID(V)、出度OD(V)--TD(V)=ID(V)+OD(V)

圖中V1到V2的路徑（怎麼走--最優路徑）

路徑的長度：邊或弧的個數

迴路或環：第一個頂點到最後一個頂點（就是走一圈，所有的頂點都走過）

連通圖：無向圖中任意兩個頂點都是連通的（連通：V1到V2有路徑）

連通分量：無向圖中的極大連通子圖

有向圖中--強連通圖--強連通分量

一個連通圖的生成樹是一個極小的連通子圖--n個頂點n-1條邊

如果一個有向圖恰有一個頂點入度為0，其他頂點入度為1，則是一棵有向樹

圖的存儲結構扒判畝：

任意兩個頂點之間都可能存在聯系，因此無法以數據元素在內存中的物理位置來表示元素之間的關系（內存物理位置是線性的，圖的元素關系是平面的）

1.鄰接矩陣：

一維數組放頂點+二維數組放邊或弧  n階和n*n

#二維數組，存在邊為1，不存在為0

#有向圖--行-列：尾-頭  //無向圖二維數組是對稱的

具有權時：可以直接填寫權值，無弧用正無窮，自身到自身還是0

2.鄰接表：

對於邊數比較少的圖，鄰接矩陣浪費

將數據和鏈表相結合--鄰接表

處理方法：

圖中頂點用一維數組，每個頂點的所有臨界點構成一個線性表（單鏈表）

#一維數組中有兩個元素-數據+指針，指針指向單鏈表 //單鏈表上表示出度或是入度-入度為逆鄰接表

權：增加一個數據域（放在單鏈表中）

3.十字鏈表：

把鄰接表和逆鄰接表結合起來

頂點結點結構：數據+入邊表指針+出邊表指針

邊表結點結構：弧起點下標+弧終點下標+頭指針+尾指針

#頭指針是鄰接表順序的指針，尾指針是逆鄰接表的指針

4.鄰接多重表：

如果關注的是邊，而非頂點

邊表結構：與某條邊依附的兩個頂點在頂點表中的下沖賣標2個+指向依附倆個頂點的下一條邊的指針2個（指針會有一些為空）

5.邊集數組

兩個一維數組：點的信息+邊的信息

邊數組每個數據元素由一條邊的起點下標、終點下標、權組成