當前位置：首頁 > 编程语言 > C# >内容正文

C#

数据结构与算法：终于可以用三种语言（C，C#，JavaScript）把图的广度优先遍历讲清楚了（推荐收藏）

發布時間：2023/12/4 C# 26 豆豆

生活随笔收集整理的這篇文章主要介紹了数据结构与算法：终于可以用三种语言（C，C#，JavaScript）把图的广度优先遍历讲清楚了（推荐收藏）小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

文章目錄

鄰接矩陣存儲圖的廣度優先遍歷過程分析
C語言實現隊列編程
程序中加入圖的處理函數
結果的再次分析
C#語言實現圖的廣度優先遍歷、并顯示廣度優先遍歷生成樹
JavaScript語言實現圖的廣度優先遍歷、并顯示廣度優先遍歷生成樹

鄰接矩陣存儲圖的廣度優先遍歷過程分析

對圖1這樣的無向圖，要寫成鄰接矩陣，則就是下面的式子
一般要計算這樣的問題，畫成表格來處理是相當方便的事情，實際中計算機處理問題，也根本不知道所謂矩陣是什么，所以畫成表格很容易幫助我們完成后面的編程任務。在我們前面介紹的內容中，有不少是借助著表格完成計算任務的，如Huffman樹。

為了記錄那些頂點是已經走過的，還要設計一個表來標記已經走過的頂點，在開始，我們假設未走過的是0，走過的是1，于是有：

對廣度優先遍歷，還需要補充一個隊列、來記錄一個頂點可以抵達到的其他頂點。

廣度優先遍歷過程如下：

結果分析

從上面的過程可以看出：僅僅就頂點訪問到的次序而言，圖1的廣度優先遍歷結果是：

V1->V2->V3>V4->V5->V6->7->V8

但實際執行過程中我們可以發現：所謂圖的廣度優先遍歷、其結果應該是一個樹：

在C語言中，顯示這個結果并不容易，所以大多C語言的教材中并不會給出這樣的結果。

C語言實現隊列編程

根據上面的分析，我們可以知道：要廣度優先遍歷圖，首先要一個隊列系統。

隊列在C語言上只能自己構造，好在我們前面有鏈表、有順序表，我們可以復制過來一個鏈表程序構造一個隊列，于是從鏈表程序中復制過來b5.c或者b6.c即可，我們分析隊列的ADT可知，最需要的隊列功能需求是：

QueueInit()、EnQueue、DeQueue()、QueueEmpty()這4個函數，于是有以下隊列定義：

struct Queue {struct LinkedList * LinkQueue;int Count; };

由于我們已經確定使用鏈表做隊列，所以隊列實際就是鏈表的換名包裝，所以我們可以理解為隊列就是鏈表的另一種應用，表3的程序就是這樣的做法，所以對隊列的初始化，就是：

struct Queue * QueueInit() {struct Queue *q;q=(struct Queue *)malloc(sizeof(struct Queue));q->LinkQueue=LinkedListInit(); q->Count=0; return q; }

有了隊列的初始化，則進入隊列、實際相當于給這個鏈表追加一條記錄，就是Append()的另類包裝：

int EnQueue(struct Queue *Q,struct ElemType *E) {if(Q==NULL) return -1;if(E==NULL) return -2;Append(Q->LinkQueue,E);Q->Count++; return 0; }

注意數據出隊列，出隊列總是把鏈表中第一個結點的數據給出來、并刪除第一個結點，所以出隊列就是：

int DeQueue(struct Queue *Q,struct ElemType *E) {struct ElemType *pE;if(Q==NULL) return -1;if(E==NULL) return -2;pE=LinkedListGet(Q->LinkQueue,1);ElemCopy(pE,E); LinkedListDel(Q->LinkQueue,1); Q->Count--;return 0; }

出隊列函數總是把第一個結點刪除掉，注意隊列完全可能數據出完后再次有數據進入隊列，則原來的結點刪除函數有Bug，這在程序開發中很正常，修改后就是：

int LinkedListDel(struct LinkedList *L,int n) {int i;struct Node *p0,*p1;if(L==NULL) return -1;if(n<0||n>L->Count) return -2;p0=L->Head;for(i=0;i<n-1;i++) p0=p0->next;p1=p0->next;p0->next=p1->next;free(p1);L->Count--;if(L->Count==0) L->Tail=L->Head; return 0; }

修改的這個鏈表結點函數、僅僅加了第14行，在過去，所以結點刪除后，最后的尾巴結點指針Tail所指的存儲空間被釋放，導致這個指針變量不可用，現在在結點個數為0的情況下，再次讓尾結點指向頭結點，保證下次進入鏈表的數據依然正確。

而判斷隊列是否為空則相對簡單的多，就是：

int QueueEmpty(struct Queue *Q) {if(Q==NULL) return -1;return !(Q->Count); }

補充main()函數，測試多批次進入隊列、出隊列，全部程序見B0.c

在我們的圖遍歷應用中，我們對隊列的數據僅僅要求一個整數即可，而這個程序進出隊列的數據有三列數據，為加強該程序可靠行，修改ElemType()，就是：

void ElemCopy(struct ElemType *s,struct ElemType *d) {d->sNo=s->sNo;//strcpy(d->sName,s->sName);//d->sAge=s->sAge; }

在一個系統中，類似這樣的修改很正常，使用已有的程序完成自己的工作，會大大加快編程的進度，使得編程工作更加流暢。
而這一切都需要自己有足夠的積累，有這個積累后完成這樣的工作才有基礎，所謂技術水平，就是不斷積累的過程。

下面，在圖的處理中會再次體現這樣的過程。

程序中加入圖的處理函數

我們的隊列系統完成后，記著再復制一個文件，加入圖的鄰接矩陣讀數據程序，我們這里這個程序名稱是b1.c。對鄰接矩陣數據的讀取、并構造圖的過程，在深度優先遍歷程序中已完成，所以直接復制過來即可，回顧廣度優先遍歷算法，就是把第一個頂點先無條件裝進隊列，所以編寫遍歷BFSM函數如下：

四、程序中加入圖的處理函數我們的隊列系統完成后，記著再復制一個文件，加入圖的鄰接矩陣讀數據程序，我們這里這個程序名稱是b1.c。對鄰接矩陣數據的讀取、并構造圖的過程，在深度優先遍歷程序中已完成，所以直接復制過來即可，回顧廣度優先遍歷算法，就是把第一個頂點先無條件裝進隊列，所以編寫遍歷BFSM函數如下： void BFSM(struct Graph *G) {int i,n;struct Queue *Q;struct ElemType *p,E,e;Q=QueueInit(); E.sNo=0; // 設置0進隊列EnQueue(Q,&E);G->Visited[0]=1; // 設置0號頂點已被訪問p=&e;while(!QueueEmpty(Q)){//待補充} }

從第11行開始，則進入真正的遍歷。

有這么個函數后，我們可以補充main()的測試函數就是：

main() {struct Graph *G;G=GraphCreat("p176G719.txt");BFSM(G); }

main()很短，也很簡單，如有不明白的回顧下深度優先遍歷函數。

回顧一下：就是隊列Q里出隊列，然后找與該頂點相連的所有頂點、在進隊列，就是：

void BFSM(struct Graph *G) {int i,n;struct Queue *Q;struct ElemType *p,E,e;Q=QueueInit(); E.sNo=0;EnQueue(Q,&E);G->Visited[0]=1; p=&e;while(!QueueEmpty(Q)){DeQueue(Q,p);n=p->sNo;printf("%s\n",G->pV[n]);for(i=0;i<G->num;i++)if(G->pA[n][i]==1&&G->Visited[i]==0){G->Visited[i]=1; E.sNo=i;EnQueue(Q,&E);}} }

運行這個程序、就會打印出這個圖的廣度優先遍歷結果。

結果的再次分析

有了這個函數后，構造main()開始從第0個頂點遍歷圖1，就是：

進一步測試該函數，按圖1的數據仔細分析下它的執行過程，如有圖的連接分量不為1，則會在第一個連接分量遍歷完成后終止。如下圖4，在B1.C中是無法全部遍歷完成的。這個圖的文件在G4.TXT，修改表23中第5行，從G4.TXT中讀數據，則會發現這個程序僅僅遍歷了A、B、C、D，而沒有到達過E、F、G這三個頂點。

這個圖該如何遍歷呢？請同學們自己修改程序，完成這個圖的遍歷。
廣度優先遍歷到此結束。

C#語言實現圖的廣度優先遍歷、并顯示廣度優先遍歷生成樹

在C#文件夾中可以找到“Graph0.cs”，這個文件中包含著深度優先遍歷、廣度優先遍歷等程序中的所有圖類程序，現在，我們就要在這個類中補充新的方法。
首先復制這個類到Graph.cs，然后用C#建立一個Windows應用程序，然后在資源管理器中添加這個類，這個類和在深度優先遍歷中的類完全一致，但去掉了命名空間說明，這樣，這個類就可以使用在其他工程中了。

首先是再次熟悉這個類中的變量定義：

private int[,] A //鄰接矩陣 private string[] V //頂點矩陣 private int[] Visited //頂點訪問表 private TreeNode[] T //遍歷生成樹 private int num //頂點個數 private int ConnComp //連通分量

找到這個類中的最后一個方法：DSFTraverse()，然后開始在這個方法后補充新方法：DFS()，由于算法和C語言完全一致，此處算法問題不在介紹。

private void BFS(int N) {int n;Queue<int> Q = new Queue<int>();Q.Enqueue(N);Visited[N] = 1; while (Q.Count != 0){n = Q.Dequeue();for (int i = 0; i < num; i++)if (A[n, i] == 1 && Visited[i] == 0){T[n].Nodes.Add(T[i]); Visited[i] = 1; Q.Enqueue(i);}} }

這個方法可以從第N個頂點開始遍歷，同前面涉及的問題一樣，考慮到多次遍歷、以及多連通分量的圖，我們還要補充下面的方法：

public int BFSTraverse(){int i;ConnComp = 0;for (i = 0; i < num; i++){T[i] = new TreeNode(V[i]);Visited[i] = 0;}for (i = 0; i < num; i++)if (Visited[i] == 0){BFS(i);ConnComp++;}return ConnComp; }

補充完類Graph中兩個方法補充后、就可以進行界面設計，設計界面如下：

根據圖1的界面設計，則廣度優先遍歷程序中連通分量為1的圖在button1下，于是有：

private void button1_Click(object sender, EventArgs e) {int m;int[,] A = {{0, 1, 1, 0, 0, 0, 0, 0},{1, 0, 0, 1, 1, 0, 0, 0},{1, 0, 0, 0, 0, 1, 1, 0},{0, 1, 0, 0, 0, 0, 0, 1},{0, 1, 0, 0, 0, 0, 0, 1},{0, 0, 1, 0, 0, 0, 1, 0},{0, 0, 1, 0, 0, 1, 0, 0},{0, 0, 0, 1, 1, 0, 0, 0}};string[] V = { "V1", "V2", "V3", "V4", "V5", "V6", "V7", "V8" };Graph G = new Graph(8);G.Arc = A; G.Vertex = V;m = G.BFSTraverse(); treeView1.Nodes.Clear();treeView1.Nodes.Add(G.DFSResult);textBox1.Text = "該圖連接分量為" + m.ToString(); }

由于類設計中、廣泛使用了原有的代碼，所以這段程序看起來和深度優先遍歷的測試代碼差別很小。同理，在有多個連通分量的情況下，在button2下的代碼是：

private void button2_Click(object sender, EventArgs e){int m;int[,] A = {{0, 1, 1, 0, 0, 0, 0},{1, 0, 0, 1, 0, 0, 0},{1, 0, 0, 1, 0, 0, 0},{0, 1, 1, 0, 0, 0, 0},{0, 0, 0, 0, 0, 1, 1},{0, 0, 0, 0, 1, 0, 1},{0, 0, 0, 0, 1, 1, 0}};string[] V = { "A", "B", "C", "D", "E", "F", "G" };Graph G = new Graph(7);G.Arc = A; G.Vertex = V;m = G.BFSTraverse(); treeView1.Nodes.Clear();G.AddInTreeView(treeView1);textBox1.Text = "該圖連接分量為" + m.ToString(); }

請自行補充button3下的代碼。

程序運行結果就是：
圖的廣度優先遍歷到此結束。通過上述編程我們可以發現：大量使用已有的代碼，可以大大簡化編程的復雜程度。

問題：

我們在C#的程序中、并沒有使用類似C語言那樣的技術：在數據文件中保存圖的數據，這首先是基于我們對C#的使用方式造成的，C#最重要的應用場合是連接數據庫服務器和前端的用戶瀏覽器，這個場合下C#提供一個正確的運算類就足夠了，其數據要來自于數據庫，而結果要給到瀏覽器上的程序。瀏覽器下的程序就是JavaScript，這樣的情況下C#不做數據文件讀取、而要做的是數據庫上數據讀取，至于送到JavaScript，這個對C#、就要通過一種叫WebService的技術，而在JavaScript上、則要用到一種叫Ajax技術讀寫這些數據，而這些都是下學期的重要實驗任務。

JavaScript語言實現圖的廣度優先遍歷、并顯示廣度優先遍歷生成樹

對JavaScript而言，是沒有隊列類的，盡管數組的類型直接泛型，但僅有棧而無隊列。我們需要最低代價完成一個隊列系統，所以要再次查看JavaScript數組的所有方法和屬性：

其中：FF: Firefox, IE: Internet Explorer

而這個對象提供的屬性，則如下表：FF: Firefox, IE: Internet Explorer

回顧棧和隊列的差異，一個是先進后出、一個是先進先出，查找上述數組的方法，有個方法是reverse()，含義是顛倒數組元素的次序，很顯然：

如果進隊列是數組的push()操作，那么出隊列則就是顛倒數組次序、然后pop()操作，有這個思路，按這個算法構造隊列類就是：

一定注意這個類的第13行，顛倒次序出棧后一定要再次顛倒這個數組的次序，保證進棧數據的次序。這樣，我們就用最小代價完成了一個隊列系統，然后補充多次進出隊列的測試網頁，就是：

<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312" /><title>一個調用Ext類庫的模板頁面</title><script type="text/javascript" src="Queue.js"></script><script type="text/javascript" src="ext-3.0.0/adapter/ext/ext-base.js"></script><script type="text/javascript" src="ext-3.0.0/ext-all.js"></script><link rel="stylesheet" type="text/css" href="ext-3.0.0/resources/css/ext-all.css" /> </head><body bgcolor="#FFFFFF"><div id="hello"></div><script type="text/javascript">function fun(){var Q=new Queue();Q.EnQueue(1);Q.EnQueue(2);Q.EnQueue(3);while(Q.Count()>0){document.write(Q.DeQueue()+'<br>');}Q.EnQueue(4);Q.EnQueue(5);while(Q.Count()>0){document.write(Q.DeQueue()+'<br>');}}Ext.onReady(fun);</script></body> </html>

注意第5行一定要引用Queue.js這個文件，否則程序無法運行。

補充廣度優先遍歷程序

根據廣度優先遍歷的算法、以及表1的隊列對象，不難寫出廣度優先遍歷程序，但寫以前我們要回顧深度優先遍歷函數的入口參數：

A[][]: 鄰接矩陣
vCount: 頂點個數
m: 進入遍歷的頂點編號
Visited[] :頂點訪問狀態表
T[]: Ext.tree.TreeNode對象數組，遍歷結果樹

我們回顧這些的原因是：我們新的遍歷函數、也要盡量和舊的方法使用的參數一致，這樣就對后續的編程提供了大量的方便。如果意義相近的方法、其函數入口參數差異很大、這樣對后續的編程造成很多困惑。

//A[][]: 鄰接矩陣 //vCount: 頂點個數 //m: 進入遍歷的頂點編號 //Visited[] :頂點訪問狀態表 //T[]: Ext.tree.TreeNode對象數組，遍歷結果樹 function BFS(A,vCount,m,Visited,T) {var i,n;var Q=new Queue();Q.EnQueue(m);Visited[m]=1;while(Q.Count()>0){n = Q.DeQueue();for (i = 0; i <vCount; i++)if (A[n][i] == 1 && Visited[i] == 0){T[n].appendChild(T[i]);Visited[i] = 1; Q.EnQueue(i);} } }

表3 JavaScript語言圖的廣度優先遍歷，見工程B0.html

該函數算法不在介紹，程序原理和C、C#沒什么差別。

從深度優先遍歷網頁補充廣度優先遍歷程序

從深度優先遍歷網頁G8.html復制文件到B0.html，在F3區域的鄰接矩陣編輯窗口補充命令按鈕“廣度優先遍歷”，就是表4.
對這個表中的程序，注意是一個程序框架，而不是全部。現在就要在合適的位置補充廣度優先遍歷的初始化程序。

var grid=new Ext.grid.EditorGridPanel({renderTo:"GRID",title:"圖的鄰接矩陣編輯",height:400,width:400,cm:colM,store:gstore,tbar: [ { text: "深度優先遍歷圖", handler: function(){ //已有的深度遍歷代碼} },{text:"廣度優先遍歷圖",handler: function(){//以下寫進遍歷的代碼} }] });

注意表4，其第20行就是補充廣度優先遍歷程序的地方，這程序本質就是給BFS()準備合適的數據、并初始化、然后調用BFS()函數，所以這地方和深度優先遍歷的代碼是一致的，于是有：

text:"廣度優先遍歷圖", handler: function() { //以下寫進遍歷的代碼var m=gstore.getCount();var n=gstore.getAt(m-1).get('row')+1;var Visited=Array();var A=Array();var i,j;for(i=0;i<n;i++){Visited[i]=0;A[i]=Array();T[i]=new Ext.tree.TreeNode({id:vstore.getAt(i).get('id'),text:vstore.getAt(i).get('V')});}for(i=0;i<m;i++){var r=gstore.getAt(i).get('row');var c=gstore.getAt(i).get('col');var v=gstore.getAt(i).get('Value');A[r][c]=v;}var Concom=0;for(i=0;i<n;i++)if(Visited[i]==0) {BFS(A,n,i,Visited,T);Concom++;}var TR=new Ext.tree.TreeNode({id:10000,text:'廣度優先遍歷樹，連通分量'+Concom});for(i=0;i<n;i++)if(T[i].parentNode==null)TR.appendChild(T[i]);treeView1.setRootNode(TR); } }

和前面深度優先遍歷的程序完全一致，僅僅是調用了不同的遍歷函數。

遍歷網頁的進一步修改和完善：構造圖類

從B0.html這個網頁程序看，首先在兩個遍歷的命令按鈕程序上有大量重復代碼，其次是有關圖的計算，其鄰接矩陣、頂點矩陣、頂點訪問狀態矩陣、遍歷函數等都是分離的變量和函數，而沒有構成一個類、從而也就沒有圖的對象，這樣對后續的編程也造成很多不利。

為此，我們要構造一個JavaScript的圖類，整體參照C#。

對任何一個語言的類編程而言，都存在數據如何進入對象、以及數據如何從對象里給出這兩個基本問題，在使用Ext過程中，我們熟悉了大量的Ext對象屬性獲得方法，那么我們這里也將按同樣的方法來構造類，詳細的介紹參見json教程。以下類名稱是Graph，其中G是屬性參數：

注意第16行，其中構造函數的參數里：

{A:[[1,2,3],[4,5,6],[7,8,9]],V:['A','B','C'],Visited:[0,0,0]}

整體構成對象G，進入類后，進入表5程序后，由第3到第5行的程序賦值給對象相應的屬性。再次參照表5程序，其中的this，對應在表6的程序是G，廣義上，實例化的對象就是表5中的this。

有了上述分析，我們就可以在表5的程序中加入一個公共方法，用來獲得屬性中V數組的內容，代碼就是：

function Graph(G) { this.A=G.A; this.V=G.V; this.Visited=G.Visited; this.num=G.num; this.T=G.T; this.VName=function(){var i;for(i=0;i<this.num;i++)document.write(this.V[i]);} }

這樣寫的方法類似是C#中的public void VName()，這樣的寫法可以在實例對象中引用這樣方法，如：

<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312" /><title>一個調用Ext類庫的模板頁面</title><script type="text/javascript" src="G1.js"></script><script type="text/javascript" src="ext-3.0.0/adapter/ext/ext-base.js"></script><script type="text/javascript" src="ext-3.0.0/ext-all.js"></script><link rel="stylesheet" type="text/css" href="ext-3.0.0/resources/css/ext-all.css" /> </head><body bgcolor="#FFFFFF"><script type="text/javascript">function fun(){var G=new Graph({A:[[1,2,3],[4,5,6],[7,8,9]],V:['A','B','C'],Visited:[0,0,0],num:3});G.VName();}Ext.onReady(fun);</script></body> </html>

上述過程完成后，可以加入一個求V數組中每行平均值的方法，涉及到求平均值，首先我們需要一個求指定行和的函數，這個函數定義成私有的，如同表9的程序中的Sum()，私有函數定義和普通的JavaScript函數完全一致。

但在實際使用中，錯誤首先在第17行，表示this.num是沒有定義。

造成這樣的結果，主要是私有的函數Sum()并不包含在對象中，這點和C#是完全不一樣，所以私有函數中要引用對象的數據，要首先獲得該對象的實例，就是要有這樣的方法：

通過上述實驗過程，則有兩個遍歷方法的圖類就是：

有了上述圖類后，則相應的界面上“深度優先遍歷”按鈕下的相應程序就是：

text: "深度優先遍歷圖", handler: function() { //以下寫進遍歷的代碼var m=gstore.getCount();var n=gstore.getAt(m-1).get('row')+1;var Visited=Array();var A=Array();var i,j;for(i=0;i<n;i++){Visited[i]=0;A[i]=Array();}//獲得鄰接矩陣數據 for(i=0;i<m;i++){var r=gstore.getAt(i).get('row');var c=gstore.getAt(i).get('col');var v=gstore.getAt(i).get('Value');A[r][c]=v;}//獲得鄰接矩陣數據 var V=new Array();//獲得頂點名稱for(i=0;i<vstore.getCount();i++)V[i]=vstore.getAt(i).get('V');//用變量給對象各個屬性賦值var G=new Graph({A:A,V:V,T:T,num:n,Visited:Visited}); m=G.DSFTraverse();var TR=new Ext.tree.TreeNode({id:10000,text:'深度優先遍歷樹，連通分量'+m});TR.appendChild(G.getTree()); treeView1.setRootNode(TR); }

上面僅僅給出深度優先遍歷的響應程序，廣度優先遍歷的代碼同上述過程基本一樣，僅僅是在第32行處為：m=G.BSFTraverse();

到此，JavaScript的兩種遍歷全部完成，這里，圖的數據來自Ext.data.ArrayStore對象，目前是常數定義或者控件輸入，以后還要加入Ajax方法、從C#讀遠程數據庫的數據，這都是下學期的任務了。

總結

以上是生活随笔為你收集整理的数据结构与算法：终于可以用三种语言（C，C#，JavaScript）把图的广度优先遍历讲清楚了（推荐收藏）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：学妹，你要的C语言版AOE网络数据结构来
下一篇：【ArcGIS微课1000例】0005：