實驗3圖的基本操作課件

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

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

3、行=請輸入您的選擇(0,1,2,3,4,5,6,7) 00132(a) 無向圖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.結束程序運行=請輸入您的選擇(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é)點 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.結束程序運行); printf(n=); printf(n 請輸入您的選擇(0,1,2,3

6、,4,5,6,7); scanf(%d,&k);建立鄰接表 函數(shù)CreateGraph構造一個有n個頂點，但不包含邊的有向圖。由于圖的頂點數(shù)事先并不知道，所以我們使用動態(tài)存儲分配的一維指針數(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的邊結點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+)