實(shí)驗(yàn)3圖的基本操作課件

1、圖 的基本算法實(shí)現(xiàn)實(shí)驗(yàn)?zāi)康? 掌握?qǐng)D的結(jié)構(gòu)特征，以及兩種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍2 圖的查找，插入和刪除算法3 掌握?qǐng)D的深度優(yōu)先遍歷算法4 掌握?qǐng)D的寬度優(yōu)先遍歷算法實(shí)驗(yàn)要求認(rèn)真閱讀和掌握本實(shí)驗(yàn)的程序上機(jī)運(yùn)行程序。保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。按照?qǐng)D的操作需要，重新組合程序并運(yùn)行，打印出文件清單和運(yùn)行結(jié)果。實(shí)驗(yàn)內(nèi)容1 輸入圖的頂點(diǎn)集合和邊集合，建立圖的鄰接矩陣，并打印。2輸入圖的頂點(diǎn)集合和邊集合，建立圖的鄰接表，并打印。3查找指定邊4刪除指定邊5插入指定邊6圖的深度優(yōu)先遍歷算法BFS （遞歸算法） 。7圖的深度優(yōu)先遍歷算法DFS（遞歸算法） 。運(yùn)行結(jié)果：=主菜單= 1.打印圖的

2、鄰接矩陣 2.打印圖的鄰接表 3.插入邊 4.刪除邊 5.查找邊 6.深度優(yōu)先遍歷圖 7.寬度優(yōu)先遍歷圖 0.結(jié)束程序運(yùn)行= 請(qǐng)輸入您的選擇(0,1,2,3,4,5,6,7) 1請(qǐng)輸入圖的節(jié)點(diǎn)編號(hào)（如1）：0，1，2，3請(qǐng)繼續(xù)輸入圖的邊（如1，2） ：0，1請(qǐng)繼續(xù)輸入圖的邊（如1，2） ：0，3請(qǐng)繼續(xù)輸入圖的邊（如1，2） ：1，3請(qǐng)繼續(xù)輸入圖的邊（如1，2） ：1，2請(qǐng)繼續(xù)輸入圖的邊（如1，2） ：2，3請(qǐng)繼續(xù)輸入二叉樹(shù)各結(jié)點(diǎn)的編號(hào)和對(duì)應(yīng)的值：0，#=主菜單= 1.打印圖的鄰接矩陣 2.打印圖的鄰接表 3.插入邊 4.刪除邊 5.查找邊 6.深度優(yōu)先遍歷圖 7.寬度優(yōu)先遍歷圖 0.結(jié)束程序運(yùn)

3、行=請(qǐng)輸入您的選擇(0,1,2,3,4,5,6,7) 00132(a) 無(wú)向圖G1(d) 圖G1的鄰接矩陣 0 1 2 30 0 1 0 11 1 0 1 12 0 1 0 13 1 1 1 0=主菜單= 1.打印圖的鄰接矩陣 2.打印圖的鄰接表 3.插入邊 4.刪除邊 5.查找邊 6.深度優(yōu)先遍歷圖 7.寬度優(yōu)先遍歷圖 0.結(jié)束程序運(yùn)行=請(qǐng)輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10) 201320123 1 3 0 0 2 程序清單 #include#include#define M 100typedef struct enode int AdjVex; T W; struc

4、t enode * NextArc; ENode; /邊節(jié)點(diǎn) typedef struct graph int Vertices ; ENode* A; Graph; /圖/函數(shù)原型聲明BOOL Exist(Graph g, int u, int v)；BOOL Add(Graph *g, int u, int v, T w)；ENode* NewENode( int vex, T weight, ENode* nextarc)；BOOL Delete(Graph *g, int u, int v)；void DFS(Graph g, int v, BOOL *visited)；void BF

5、S(Graph g, T v, BOOL *visited)；/主函數(shù)void main() char ch; int k; do printf(nnn); printf(n=主菜單=); printf(nn 1.打印圖的鄰接矩陣); printf(“nn 2.打印圖的鄰接表); printf(nn 3.插入邊); printf(“nn 4.刪除表); printf(“nn 5.查找邊); printf(“nn 6.深度優(yōu)先遍歷圖); printf(“nn 7.寬度優(yōu)先遍歷圖); printf(nn 0.結(jié)束程序運(yùn)行); printf(n=); printf(n 請(qǐng)輸入您的選擇(0,1,2,3

6、,4,5,6,7); scanf(%d,&k);建立鄰接表 函數(shù)CreateGraph構(gòu)造一個(gè)有n個(gè)頂點(diǎn)，但不包含邊的有向圖。由于圖的頂點(diǎn)數(shù)事先并不知道，所以我們使用動(dòng)態(tài)存儲(chǔ)分配的一維指針數(shù)組。void CreateGraph(Graph* g, int n) int i; g-Vertices=n; g-A=(ENode*)malloc(n*sizeof(ENode*); for(i=0; iAi=NULL; 01.n-1.邊的搜索01232 1 0 3 1 3 1 3 2 0 1,2是否有邊？/搜索邊的函數(shù)BOOL Exist(Graph g, int u, int v) int n; E

7、Node* p; n=g.Vertices; if(un-1) return FALSE; for(p=g.Au; p&p-AdjVex!=v; p=p-NextArc; if (!p) return FALSE; return TRUE; 插入邊的函數(shù)BOOL Add(Graph *g, int u, int v, T w) int n; ENode *p; n=g-Vertices; if (u0 | vn-1 | vn-1 | u=v | Exist(*g, u, v) printf(BadInputn); return FALSE; p=NewENode(v, w, g-Au); g-

8、Au=p; return TRUE; 0123 1 3 0 0 2 p30132插入鄰接表中由指針Au所指示的單鏈表的最前面ENode* NewENode( int vex, T weight, ENode* nextarc)ENode* p; p=(ENode*)malloc(sizeof(ENode); p-AdjVex=vex; p-W=weight; p-NextArc=nextarc; return p; /刪除邊的函數(shù)BOOL Delete(Graph *g, int u, int v) int n=g-Vertices; ENode* p, *q; if(u-1 & uAu; q

9、=NULL; while (p& p-AdjVex!=v) q=p; p=p-NextArc; if (p) if (q) q-NextArc=p-NextArc; else g-Au=p-NextArc; free(p); return TRUE; printf(BadInputn); return FALSE; 0123 1 3 0 0 2 01323Pq=NULL在由指針Au所指示的單鏈表中，搜索AdjVex域的值為v的邊結(jié)點(diǎn)DFS遞歸算法（ 【程序105】 ）。void DFS(Graph g, int v, BOOL *visited) ENode *w; visitedv=TRUE; printf(%d , v); for ( w=g.Av; w; w=w-NextArc) if (!visitedw-AdjVex ) DFS(g, w-AdjVex, visited); void Traversal_DFS(Graph g) BOOL visitedMaxSize; int i, n=g.Vertices; for(i=0; in; i+)