Data structure and algorithm: Finally, the breadth-first traversal of the graph can be explained clearly in three languages ​​(C, C#, JavaScript) (recommended collection)

Article Directory


Analysis of the breadth-first traversal process of the adjacency matrix storage graph

For an undirected graph like Figure 1, if you want to write an adjacency matrix, the following formula is

Insert picture description here
Insert picture description here

generally used to calculate such a problem. It is quite convenient to draw it into a table to deal with. In practice, the computer does not know the so-called matrix. What is it, so it is easy to draw a table to help us complete the programming tasks later. In the content we introduced earlier, many of them use tables to complete calculation tasks, such as Huffman trees.

Insert picture description here


In order to record those vertices that have been traversed, a table is also designed to mark the vertices that have been traversed. At the beginning, we assume that the vertices that have not been traversed are 0, and the ones that have been traversed are 1, so:

Insert picture description here


For breadth-first traversal, a queue needs to be added to record other vertices that a vertex can reach.

The breadth-first traversal process is as follows:

Insert picture description here


Result analysis

From the above process, it can be seen that only in terms of the order in which the vertices are accessed, the breadth-first traversal result of Figure 1 is:

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

But in the actual execution process, we can find that the so-called breadth-first traversal of the graph, the result should be a tree:

Insert picture description here


In the C language, it is not easy to display this result, so most of the C language textbooks will not give such a result.

C language to achieve queue programming

Based on the above analysis, we can know: To breadth-first traversal of the graph, we first need a queue system.

The queue can only be constructed by itself in C language. Fortunately, we have a linked list and an ordered list in front of us. We can copy a linked list program to construct a queue, so we can copy b5.c or b6.c from the linked list program. Analyzing the ADT of the queue, we can see that the most needed queue function requirements are:

QueueInit(), EnQueue, DeQueue(), QueueEmpty() these four functions, so there are the following queue definitions:

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

Since we have determined to use a linked list as a queue, the queue is actually a renamed packaging of the linked list, so we can understand that the queue is another application of the linked list. The program in Table 3 is like this, so the initialization of the queue is:

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

With the initialization of the queue, entering the queue is actually equivalent to appending a record to the linked list, which is an alternative packaging of 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;
}

Note that the data is out of the queue, the out queue always gives the data of the first node in the linked list and deletes the first node, so the out queue is:

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;
}

The out-queue function always deletes the first node. Note that it is entirely possible that data will enter the queue again after the data is out. The original node-delete function has a bug. This is normal in program development. After modification, it is:

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;
}

The modified link list node function only added the 14th line. In the past, after the node was deleted, the storage space pointed to by the last tail node pointer Tail was released, causing the pointer variable to be unavailable, and it is now at the node. When the number is 0, let the tail node point to the head node again to ensure that the data that enters the linked list next time is still correct.

And judging whether the queue is empty is relatively simple, that is:

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

Supplement the main() function to test multiple batches entering and exiting the queue, see B0.c for all procedures

In our graph traversal application, we only require an integer for the data in the queue, and the data in and out of the queue of this program has three columns of data. To enhance the reliability of the program, modify ElemType(), which is:

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

In a system, modifications like this are normal. Using an existing program to complete one's own work will greatly speed up the progress of programming and make the programming work smoother.
And all this requires oneself to have enough accumulation, only after this accumulation is completed can there be a foundation. The so-called technical level is the process of continuous accumulation.

Below, this process will be reflected again in the processing of the figure.

Add the processing function of the graph to the program

After our queuing system is completed, remember to copy another file and add it to the graph's adjacency matrix to read the data program. The program name here is b1.c. The process of reading the adjacency matrix data and constructing the graph has been completed in the depth-first traversal program, so you can copy it directly. Reviewing the breadth-first traversal algorithm is to unconditionally load the first vertex into the queue first, so write The traversal BFSM function is as follows:

四、程序中加入图的处理函数
我们的队列系统完成后,记着再复制一个文件,加入图的邻接矩阵读数据程序,我们这里这个程序名称是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))
	{
    //待补充
	}
}

Starting from line 11, the real traversal is entered.

After having such a function, we can add the test function of main() to be:

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

main() is short and simple. If you don’t understand, review the depth-first traversal function.

To recap: it is to leave the queue in the queue Q, and then find all the vertices connected to the vertex and enter the queue, which is:

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);
			}
	}
}

Running this program will print out the breadth-first traversal results of this graph.

Re-analysis of results

With this function, construct main() to traverse graph 1 from the 0th vertex, which is:

Further test the function, carefully analyze its execution process according to the data in Figure 1. If the connection component of the graph is not 1, it will terminate after the traversal of the first connection component is completed. As shown in Figure 4 below, in B1.C, all traversal cannot be completed. The file in this picture is in G4.TXT, modify the 5th row in Table 23, read the data from G4.TXT, you will find that this program only traversed A, B, C, D, but did not reach E, F, G These three vertices.

Insert picture description here


How should this graph be traversed? Please modify the program yourself to complete the traversal of this graph.
The breadth-first traversal ends here.

C# language implements the breadth-first traversal of the graph and displays the breadth-first traversal of the spanning tree

You can find "Graph0.cs" in the C# folder. This file contains all graph programs in depth-first traversal, breadth-first traversal and other programs. Now, we will add new methods to this class.
First copy this class to Graph.cs, then use C# to build a Windows application, and then add this class in the explorer. This class is exactly the same as the class in the depth-first traversal, but the namespace description is removed. In this way, This class can be used in other projects.

The first is to familiarize yourself with the variable definitions in this class again:

private int[,] A         //邻接矩阵
private string[] V       //顶点矩阵
private int[] Visited    //顶点访问表
private TreeNode[] T     //遍历生成树
private int num          //顶点个数
private int ConnComp     //连通分量

Find the last method in this class: DSFTraverse(), and then start to add a new method after this method: DFS(). Since the algorithm is exactly the same as the C language, the algorithm problem is not introduced here.

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);
                    }
            }
}

This method can be traversed from the Nth vertex. As with the previous problems, considering multiple traversals and graphs with multiple connected components, we need to add the following method:

        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; 
        }

After supplementing the two methods in the Graph class, the interface design can be carried out. The design interface is as follows:

Insert picture description here


According to the interface design of Figure 1, the graph with the connected component of 1 in the breadth-first traversal program is under button1, so there are:

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(); 
}

Due to the extensive use of the original code in the class design, this program looks very different from the depth-first traversal test code. Similarly, in the case of multiple connected components, the code under button2 is:

        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(); 
        }

Please add the code under button3 by yourself.

The result of the program operation is:

Insert picture description here

the breadth-first traversal of the graph ends here. Through the above-mentioned programming, we can find that the extensive use of existing codes can greatly simplify the complexity of programming.

problem:

In our C# program, we did not use a technology similar to the C language: save the data of the graph in the data file, which is firstly based on the way we use C#. The most important application of C# is to connect to the database server and The front-end user browser, in this case, C# provides a correct calculation class is enough, the data must come from the database, and the result must be given to the program on the browser. The program under the browser is JavaScript. In this case, C# does not read data files, but rather reads data from the database. As for sending to JavaScript, this requires a technology called WebService for C#. In JavaScript, you need to use a technology called Ajax to read and write these data, and these are important experimental tasks for the next semester.

JavaScript language implements the breadth-first traversal of the graph and displays the breadth-first traversal of the spanning tree

For JavaScript, there is no queue class. Although the type of array is directly generic, there is only a stack and no queue. We need to complete a queue system at the lowest cost, so we need to review all the methods and properties of the JavaScript array again:

Among them: FF: Firefox, IE: Internet Explorer

Insert picture description here


The attributes provided by this object are as follows: FF: Firefox, IE: Internet Explorer

Insert picture description here


Looking back at the difference between the stack and the queue, one is first-in-last-out and the other is first-in-first-out. One of the methods to find the above array is reverse(), which means to reverse the order of array elements. Obviously:

If entering the queue is the push() operation of the array, then leaving the queue is to reverse the order of the array and then pop(). With this idea, the queue class constructed according to this algorithm is:

		function Queue()
		{
		this.Q=new Array();
		this.EnQueue=function(E)
			{
			this.Q.push(E);
			}
		this.DeQueue=function()
			{
			var E;
			this.Q=this.Q.reverse();
			E=this.Q.pop();
			this.Q=this.Q.reverse();
			return E;
			}
		this.Count=function()
			{
			return this.Q.length;
			}
		}

Be sure to pay attention to the 13th line of this class. After reversing the order, you must reverse the order of the array again to ensure the order of the data on the stack. In this way, we completed a queuing system with minimal cost, and then supplemented the test webpage that enters and exits the queue multiple times, which is:

<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>

Note that line 5 must refer to the Queue.js file, otherwise the program cannot run.

Supplement the breadth-first traversal program

According to the breadth-first traversal algorithm and the queue objects in Table 1, it is not difficult to write a breadth-first traversal program, but before writing we have to review the entry parameters of the depth-first traversal function:

A[][]: adjacency matrix
vCount: number of vertices
m: number of vertices to be traversed
Visited[]: vertex access state table
T[]: array of Ext.tree.TreeNode objects, traversing the result tree

The reason we review these is: Our new traversal function should also be as consistent as possible with the parameters used by the old method, which provides a lot of convenience for subsequent programming. If methods with similar meanings have very different function entry parameters, this will cause a lot of confusion for subsequent programming.

//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);
	                    }			
			}
}

Table 3 Breadth-first traversal of JavaScript language graph, see project B0.html

The function algorithm is not introduced, the principle of the program is no different from C and C#.

Supplement breadth-first traversal program from depth-first traversal of web pages

Copy the file from the depth-first traversal page G8.html to B0.html, and add the command button "breadth-first traversal" in the adjacency matrix editing window of the F3 area, which is Table 4.
For the programs in this table, note that it is a program frame, and not all. Now it is necessary to supplement the breadth-first traversal initialization program at the right place.

var grid=new Ext.grid.EditorGridPanel({
			renderTo:"GRID",
			title:"图的邻接矩阵编辑",
			height:400,
			width:400,
			cm:colM,
			store:gstore,
			tbar: [ 
			{ 
			text: "深度优先遍历图",   
			handler: function()
					{ 
					//已有的深度遍历代码
					} 
			},
			{
			text:"广度优先遍历图",
			handler: function()
					{
			          //以下写进遍历的代码
					} 
			}
			] 
});

Pay attention to Table 4, the 20th line is the place to supplement the breadth-first traversal program. The essence of this program is to prepare suitable data for BFS(), initialize it, and then call the BFS() function, so the code for this place and the depth-first traversal is Consistent, so there are:

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);
} 
}

It is exactly the same as the previous depth-first traversal program, except that a different traversal function is called.

Further modification and improvement of traversing web pages: structure diagram class

From the B0.html webpage program, firstly, there are a lot of repeated codes on the two traversed command button programs, and secondly, the calculation of the graph. Its adjacency matrix, vertex matrix, vertex access state matrix, traversal function, etc. are all separated Variables and functions do not constitute a class and therefore have no graph objects, which also causes many disadvantages to subsequent programming.

To this end, we have to construct a JavaScript graph class, referring to C# as a whole.

For class programming in any language, there are two basic questions about how data enters the object and how data is given from the object. In the process of using Ext, we are familiar with a large number of methods for obtaining Ext object properties, then we The class will be constructed in the same way here. For a detailed introduction, please refer to the json tutorial. The following class name is Graph, where G is the attribute parameter:

function Graph(G)
{
this.A=G.A;
this.V=G.V;
this.Visited=G.Visited;
this.num=G.num;
this.T=G.T;
}

<html>
	<head>
	<meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
	<title>一个调用Ext类库的模板页面</title>
		<script type="text/javascript" src="G0.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 G=new Graph({
			      A:[[1,2,3],[4,5,6],[7,8,9]],V:['A','B','C'],Visited:[0,0,0]
			      });
	     }
 	     Ext.onReady(fun);
	</script>
	</body>
</html>

Pay attention to line 16, where in the parameter of the constructor:

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

The whole constitutes the object G. After entering the class, after entering the program in Table 5, the program in lines 3 to 5 is assigned to the corresponding attribute of the object. Refer to the program in Table 5 again, where this corresponds to the program in Table 6 as G. In a broad sense, the instantiated object is this in Table 5.

With the above analysis, we can add a public method to the program in Table 5 to obtain the contents of the V array in the attribute. The code is:

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]);
	}
}

The method written in this way is similar to the public void VName() in C#. This way of writing can reference such methods in the instance object, such as:

<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>

After the above process is completed, you can add a method to find the average value of each row in the V array. When it comes to finding the average value, first we need a function to calculate the sum of the specified rows. This function is defined as private, as in the program in Table 9. Sum(), the private function definition is exactly the same as the ordinary JavaScript function.

But in actual use, the error first appears on line 17, indicating that this.num is not defined.

This result is mainly because the private function Sum() is not included in the object. This is completely different from C#. Therefore, the data of the object must be referenced in the private function. The instance of the object must be obtained first. Such a method:

var Ob=this;
function Sum()
{
…
for(i=0;i<Ob.num;i++)
…
}

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]);
	}
function Sum(n)
{
var s=0,i;
for(i=0;i<this.num;i++)  //私有方法中错误引用对象数据
	s+=this.A[n][i];
return s;
}
this.AVG=function(n)
	{
	var s;
	s=Sum(n)/this.num;	
	}
}

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]);
	}
function Sum(n)
{
var s=0,i;
for(i=0;i<this.num;i++)  //私有方法中错误引用对象数据
	s+=this.A[n][i];
return s;
}
this.AVG=function(n)
	{
	var s;
	s=Sum(n)/this.num;	
	}
}

function Graph(G)
{
this.A=G.A;
this.V=G.V;
this.Visited=G.Visited;
this.num=G.num;
this.T=G.T;
var Ob=this;
//公共方法
this.VName=function()
	{
	var i;
	for(i=0;i<this.num;i++)
		document.write(this.V[i]);
	}
//私有方法
function Sum(n)
{
var s,i;
s=0;
for(i=0;i<Ob.num;i++)
	s+=Ob.A[n][i];
return s;
}
//公共方法
this.AVG=function(n)
	{
	var a;
	a=Sum(n)/this.num;	
	return a;
	}
}

Through the above experimental process, the graph class with two traversal methods is:

function Graph(G)
{
this.A=G.A;
this.V=G.V;
this.Visited=G.Visited;
this.num=G.num;
this.T=G.T;
var Ob=this;
//私有方法:深度优先遍历
function DFS(m)
{
var i;
Ob.Visited[m]=1;
for(i=0;i<Ob.num;i++)
	{
	if(Ob.A[m][i]!=0&&Ob.Visited[i]!=1) 
		{
		Ob.T[m].appendChild(Ob.T[i]);
		DFS(i);
		}
	}
}
//公共方法:深度优先遍历、以及初始化
this.DSFTraverse=function()
	{
	var i,Comcon=0;
	if (this.num==0||this.num==undefined) return -1;
	for(i=0;i<this.num;i++)
		{
		this.Visited[i]=0;
		this.T[i]=new Ext.tree.TreeNode({id:i,text:this.V[i]}); 
		}
	for(i=0;i<this.num;i++)
		if(this.Visited[i]==0)
			{
			DFS(i);Comcon++;
			}
	return Comcon;
	}
//私有方法:广度优先遍历
function BFS(m)
{
	var i,n;
	var Q=new Queue();
	Q.EnQueue(m);
	Ob.Visited[m]=1;
	while(Q.Count()>0)
		{
	        n = Q.DeQueue();
                for (i = 0; i <Ob.num; i++)
               	    if (Ob.A[n][i] == 1 && Ob.Visited[i] == 0)
	            {
                        Ob.T[n].appendChild(Ob.T[i]);
	                Ob.Visited[i] = 1; 
	                Q.EnQueue(i);
	            }			
		}
}
//公共方法:深度优先遍历、以及初始化
this.BSFTraverse=function()
	{
	var i,Comcon=0;
	if (this.num==0||this.num==undefined) return -1;
	for(i=0;i<this.num;i++)
		{
		this.Visited[i]=0;
		this.T[i]=new Ext.tree.TreeNode({id:i,text:this.V[i]}); 
		}
	for(i=0;i<this.num;i++)
		if(this.Visited[i]==0)
			{
			BFS(i);
			Comcon++;
			}
	return Comcon;
	}
//获得遍历结果树,适应多个连接分量情况下。
this.getTree=function()
	{
	for(i=1;i<this.num;i++)
		if(this.T[i].parentNode==null)
			this.T[0].appendChild(this.T[i]);
	return this.T[0];
	}
}

With the above graph class, the corresponding program under the "depth-first traversal" button on the corresponding interface is:

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);
}   

The above only gives the response program for depth-first traversal. The code for breadth-first traversal is basically the same as the above process, except that the 32nd line is: m=G.BSFTraverse();

At this point, the two traversals of JavaScript are all completed. Here, the data of the graph comes from the Ext.data.ArrayStore object, which is currently constant definition or control input. In the future, Ajax method will be added to read remote database data from C#. This is all The task for the next semester is up.

Insert picture description here