6-1 邻接矩阵存储图的深度优先遍历 (20 分)
试实现邻接矩阵存储图的深度优先遍历。
函数接口定义：
void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );
其中MGraph是邻接矩阵存储的图，定义如下：
typedef struct GNode
PtrToGNode;
struct GNode{
int Nv; /
顶点数
/
int Ne; /
边数
/
WeightType G[MaxVertexNum][MaxVertexNum]; /
邻接矩阵
/
};
typedef PtrToGNode MGraph; /
以邻接矩阵存储的图类型 */
函数DFS应从第V个顶点出发递归地深度优先遍历图Graph，遍历时用裁判定义的函数Visit访问每个顶点。当访问邻接点时，要求按序号递增的顺序。题目保证V是图中的合法顶点。
裁判测试程序样例：
#include <stdio.h>
typedef enum {false, true} bool;
#define MaxVertexNum 10 /* 最大顶点数设为10
/
#define INFINITY 65535 /
∞设为双字节无符号整数的最大值65535*/
typedef int Vertex; /* 用顶点下标表示顶点,为整型
/
typedef int WeightType; /
边的权值设为整型 */
typedef struct GNode
PtrToGNode;
struct GNode{
int Nv; /
顶点数
/
int Ne; /
边数
/
WeightType G[MaxVertexNum][MaxVertexNum]; /
邻接矩阵
/
};
typedef PtrToGNode MGraph; /
以邻接矩阵存储的图类型
/
bool Visited[MaxVertexNum]; /
顶点的访问标记 */
MGraph CreateGraph(); /* 创建图并且将Visited初始化为false；裁判实现，细节不表 */
void Visit( Vertex V )
{
printf(” %d”, V);
}
void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );
int main()
{
MGraph G;
Vertex V;
G = CreateGraph();
scanf("%d", &V);
printf("DFS from %d:", V);
DFS(G, V, Visit);
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例：给定图如下
5
输出样例：
DFS from 5: 5 1 3 0 2 4 6
这道题其实实现起来很简单，只要用一个递归就可以了
void DFS(MGraph T,Vertex V,void (*Visit)(Vertex))//这里调用了一个Visit函数输出，虽然我也不太明白为什么
{
Visit(V);//输出
Visited[V]=true;//改标记
int i;
for(i=0;i<T->Nv;i++)//邻接表遍历所有结点
{
if(T->G[V][i]==1&&Visited[i]==false)//找到一个邻接点递归遍历
DFS(T,i,Visit);
}
}
完整代码
#include<stdio.h>
typedef enum{false,true}bool;
#define MaxVertexNum 10//最大顶点数为10
#define INFINITY 65535
typedef int Vertex;//定义顶点类型
typedef int WeightType;//定义边类型
typedef struct GNode*PtrToGNode;
struct GNode{
int Nv;
int Ne;
WeightType G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGNode MGraph;
bool Visited[MaxVertexNum];
MGraph CreateGraph();
MGraph CreateGraph()
{
MGraph T;
T=(MGraph)malloc(sizeof(struct GNode));
T->Nv=7;
T->Ne=9;
int i,j,k;
for(i=0;i<T->Nv;i++)//先初始化再输入
for(i=0;i<T->Nv;i++)
T->G[i][j]=0;
for(k=0;k<T->Ne;k++)
{
scanf("%d %d",&i,&j);
T->G[i][j]=1;
T->G[j][i]=1;
}
for(i=0;i<T->Nv;i++)
Visited[i]=false;
return T;
}
void visit(Vertex V);
void visit(Vertex V)
{
printf(" %d",V);
}
void DFS(MGraph T,Vertex V,void (*Visit)(Vertex));
void DFS(MGraph T,Vertex V,void (*Visit)(Vertex))
{
Visit(V);
Visited[V]=true;
int i;
for(i=0;i<T->Nv;i++)
{
if(T->G[V][i]==1&&Visited[i]==false)
DFS(T,i,Visit);
}
}
int main()
{
MGraph G;
Vertex V;
G=CreateGraph();
scanf("%d",&V);
printf("DFS from %d:",V);
DFS(G,V,visit);
return 0;
}
书上的深度遍历有两种
（1）
#define MaxVerNum
int flag[MaxVerNum]={0};
void DFSTraverse(Graph*G,int v)
{
Visited(v);flag[v]=1;
for(w=FirstAdfVex(G,v);w;w=NextAdjVex(G,v,w))
if(!flag[w])
DFSTraverse(G,w);
}
用邻接矩阵存储的图的两个函数实现
int firstadj(G,v)
{int w;
for(w=1;w<=G.VerNum;w++)
{if(G.AdjMatruux[v][w]>=1&&G.AdjMatrix[v][w]<INF)
{
return w;
{
}
return 0;
}
int nextadj(G,v,w)
{int i;
for(i=w+1;i<=G.VerNum;i++)
{
if(G.AdjMatrix[v][i]>=1&&G.AdjMatrix[v][i]<INF)
return i;
}
return 0;
}
用邻接表实现
int FirstAdj(VNode G[],int v)
{if(G[v].firstarc!=NULL)
return (G[v].firstarc)->adjvex;
return -1;
int NextAdj(VNode G[],int v)
{
ArcNode*p;
p=G[v].firstarc;
while(p!=NULL)
{if(visited[p-adjvex])p=p->next;
else
return p->adjvex;
}
return -1;
还有我自己写的一个NextAdj（VNode G[]，int v,int w)函数
int NextAdj(VNode G[],int v,int w)
{ArcNode*p;
p=G[v].firstarc;
while(p->adjvex!=w)//先到达w的位置
p=p->next;
if(p->next==NULL)return -1;
else p=p->next;//从w的下一条边开始
while(p!=NULL)
{if(visited[p->adjvex])p=p->next;
else return p->adjvex;
}
return -1;
书上的确切过程，用邻接表实现的
#define MaxVerNum
int flag[MaxVerNum]={0}
void DFSAL(Graph*G,int i)
{
EdgeNode *p;
Visited(G->AdjList[i].vertex);
flag[i]=1;
p=G->AdjList[i].firstedge;
while(p)
{j=p->adjvex;
if(!flag[j])
DFSAL(G,j);
p=p->next;
}
}
void DFSTraverseAL(Graph*G)//图中有几个连通分量，通过该函数就会调用几次DFS函数
{int i;
for(i=0;i<G->vnum;i++)
if(!flag[i])DFS(G,i);
}