数据结构是计算机专业考研重点内容，大部分院校都是考到了数据结构，其中基于邻接矩阵存储的图的创建和深度优先遍历算法是其中的重点难点内容，因此中公考研计算机教研室为大家整理的“数据结构考研重难点解析：基于邻接矩阵存储的图的创建和深度优先遍历算法”，希望对大家有所帮助！
一、图的创建
1.创建基于邻接矩阵存储的图的结构体，主要由4个部分组成：顶点集合vex、边集合edge、顶点个数n、边的数目e。定义如下：
typedef struct AdjMatrix{
char vex[100];
int edge[100][100];
int n;
int e;
}Adj;
2.定义创建图的基本操作，函数void create(Adj &G);该函数无返回值，参数为图的结构体变量，由于要对它进行创建，所以 “&”符号；具体步骤如下：循环地输入每一个顶点元素，当输入为‘#’时停止输入，并记录输入结点个数，再循环地输入边，输入方式为边左右两边的下标，并记录输入边的数目。
代码如下：
void create(Adj &G)
{
int i,j,vi,vj,count=0;
char ch;
printf("请输入顶点：\n");
for(i=0;(ch=getchar())!='#';i )
{
G.vex[i]=ch;
}
G.n=i;
for(i=0;i<G.n;i )
{
for(j=0;j<G.n;j )
G.edge[i][j]=0;
}
printf("请输入边：\n");
scanf("%d%d",&vi,&vj);
while(vi>=0)
{
G.edge[vi][vj]=1;
scanf("%d%d",&vi,&vj);
count ;
}
G.e=count;
}
二、深度优先遍历（DFS）
深度优先遍历(Depth First Search)遍历类似于树的先根遍历。它是从图中某个顶点v出发，访问此顶点，然后依次从v未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问为止。
1.首先创建访问数组int visitDFS[10]；最多有10个顶点；
2.其次创建深度优先访问函数void DFSTravel(Adj G)，它无返回值，有一个参数就是图变量，具体步骤为：给访问数组赋初始值，全部设置为0；通过深度优先访问方式遍历每一个未被访问过的顶点，修改访问数组对应位置的值为1，直到所有顶点都访问一次结束。
代码如下：
int visetDFS[10];
void DFSTravel(Adj G)
{
int i;
for(i=0;i<G.n;i )
visetDFS[i]=0;
for(i=0;i<G.n;i )
{
if(!visetDFS[i])
DFS(G,i);
}
}
3.最后创建深度优先访问算法void DFS(Adj G,int i);该算法无返回值，有两个参数图变量以及要访问的顶点下标。
具体步骤如下：给传进来的顶点的访问数组设置为已访问（1），访问该顶点，通过for循环找到该顶点的所有邻接点，从第一个不为0的邻接点出发，通过递归的方式来找它的邻接点。
代码如下：
void DFS(Adj G,int i)
{
visetDFS[i]=1;
printf("%c ",G.vex[i]);
for(int j=0;j<G.n;j )
{
if(G.edge[i][j]!=0&&!visetDFS[j])
DFS(G,j);
}
}
