图第四课时作业

一、邻接表（Adjacency List），即_______与________相结合的存储方法。
二、邻接表的处理方法：
1、图中顶点用一个_______存储，另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的______信息。
2、图中每个顶点vi的所有邻接点构成一个_______，由于邻接点的个数不定，所以用_______，无向图称为顶点vi的边表，有向图称为顶点vi作为弧尾的出边表。


3、对于带权值的网图，可以在边表结点定义中再增加一个______，存储权值信息即可。

三、深度优先遍历算法的基本思想：
(1) 首先选定一个未被访问过的顶点V作为起始顶点（或者访问指定的起始顶点V），并将其标记为_____；
(2) 然后搜索与顶点V邻接的所有顶点，判断这些顶点是否被_____，如果有未被访问过的顶点，则任选一个顶点W进行访问；再选取与顶点W_____的未被访问过的任一个顶点并进行访问，依次重复进行。当一个顶点的_____邻接顶点都被访问过时，则依次回退到最近被访问的顶点。若该顶点还有其他邻接顶点未被访问，则从这些未被访问的顶点中取出一个并重复上述过程，直到与起始顶点V相通的所有顶点都被访问过为止。
(3) 若此时图中依然有顶点未被访问，则再选取其中一个顶点作为起始顶点并访问之，转（2）。反之，则遍历结束。
我们如何判断起始顶点V的邻接顶点是否被访问过呢？
四、程序填写：

void DFS(MGraph *G,int i)
{
	int j;
	
	//1.处理起始点 
	printf("%c",G->Vertex[i]);//1.输出起始结点 
	_________（1）______;//2.将已访问的结点标志成1
	
	 //2.由起始点开始，对后续结点进行 *** 作
	for(j=0;j<G->vexnum;j++)//依次搜索vi的邻接点 
	{
		if(G->AdjMatrix[i][j]==____(2)___&&visited[j]==0)//当满足有边且未被访问过时，递归调用去查找该邻接点 
		{
			____(3)____;//注意此处的G已经是指针类型，不需要再&G 
		}
	}
	
}

五、写出下列程序的运行结果：______。

#include 
void swap(int *,int);

int main(){
	int a=3,b=5;
	swap(&a,b);
	printf("a=%d,b=%d",a,b);
}

void swap(int *x,int y){
	int temp;
	temp=*x;
	*x=y;
	y=temp;
}