- 因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环。
解决方案：附设访问标志数组visited[n] 。
代码如下:
void initVisited(int vertexNum)
{
int i;
for (i=0; i
邻接矩阵实现图的存储结构
- 是否可以采用顺序存储结构存储图？
图的特点：顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存 储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。
- 如何存储图？
考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。
- 邻接矩阵数组表示
基本思想：用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。
假设图G＝(V，E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：
arc[i][j]＝ 1 若(vi, vj)∈E（或∈E）
0 其它
全局定义结构体
struct node
{
datatype vertex[N];
int arc[N][N];
int degree_out[N]; //顶点的出度
int degree_in[N]; //顶点的入度
}mGraph;
邻接矩阵创建图
1.确定图的顶点个数和边的个数；
2. 输入顶点信息；
3. 初始化邻接矩阵；
4. 依次输入每条边存储在邻接矩阵arc中；
4.1 输入边依附的两个顶点的序号i, j；
4.2 将邻接矩阵的第i行第j列的元素值置为1；
4.3 将邻接矩阵的第j行第i列的元素值置为1；
代码如下：
int creatGraph(int vertexnum,int vertexarc)//创建邻接矩阵
{
int l,k,j,i;
printf("请输入四个顶点的值n");
for(int i=0;i
邻接矩阵输出图
代码如下：
void display(int vertexnum,int vertexarc)//输出图的邻接矩阵
{
int i,j;
puts("输出顶点的值");
for(i=0;i
基于邻接矩阵深度优先遍历
⑴ 访问顶点v；
⑵ 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；
⑶ 重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。
代码如下：
int DFSTraversel(int v)//基于邻接矩阵的深度优先遍历
{
printf("%d ",mGraph.vertex[v]);
visited [v]=1;
for (int j=0; j
基于邻接矩阵的广度优先遍历
⑴ 访问顶点v；
⑵ 依次访问v的各个未被访问的邻接点v1, v2, …, vk；
⑶ 分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。
代码如下：
int DFSTraversel2(int v)//基于邻接矩阵的广度优先遍历
{
printf("基于邻接矩阵的广度优先遍历");
int rear=-1,front=-1;
int Q[vertexnum];
printf("%d ",mGraph.vertex[v]);
visited[v]=1;
Q[++rear]=v;
while(front!=rear)
{
v=Q[++front];
for(i=0;i
- 如何求顶点 i 的所有邻接点？
将数组中第 i 行元素扫描一遍，若arc[i][j]为1，则顶点 j 为顶点 i 的邻接点。
- 有向图的邻接矩阵一定不对称吗？
不一定，例如有向完全图。
- 如何判断从顶点 i 到顶点 j 是否存在边？
测试邻接矩阵中相应位置的元素arc[i][j]是否为1。
邻接表实现图的存储结构
- 图的邻接矩阵存储结构的空间复杂度？
假设图G有n个顶点e条边，则存储该图需要O(n2) 。
- 如果为稀疏图则会出现什么现象？
邻接表存储的基本思想：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表。
- 边表中的结点表示什么？
每个结点对应图中的一条边，邻接表的空间复杂度为O(n+2e)。
- 如何求顶点 i 的度？
顶点i的边表中结点的个数。
- 如何判断顶点 i 和顶点 j之间是否存在边?
测试顶点 i 的边表中是否存在终点为 j 的结点。
- 如何求顶点 i 的出度？
顶点 i 的出边表中结点的个数。
- 如何求顶点 i 的入度？
各顶点的出边表中以顶点 i 为终点的结点个数。
- 如何求顶点 i 的所有邻接点？
遍历顶点 i 的边表，该边表中的所有终点都是顶点 i 的邻接点。
定义邻接表结点
typedef struct ArcNode
{ int adjvex;
struct ArcNode *next;
}Arcnode;
struct VertexNode
{
datatype vertex;
Arcnode *firstedge;
int degree_out; //顶点的出度
int degree_in; //顶点的入度
} adjlist[N];
创建邻接表
1. 确定图的顶点个数和边的个数；
2. 输入顶点信息，初始化该顶点的边表；
3. 依次输入边的信息并存储在边表中；
3.1 输入边所依附的两个顶点的序号i和j；
3.2 生成邻接点序号为j的边表结点s；
3.3 将结点s插入到第i个边表的头部；
代码如下：
int ALgraph(int vertexnum,int vertexarc)//邻接表的创建
{
Arcnode *p;
puts("请输入四个顶点的值");
for(i=0;iadjvex=l;
p->next=adjlist[k].firstedge;
adjlist[k].firstedge=p;
}
}
输出邻接表
代码如下：
void displayAlgraph(int vertexnum)//邻接表的输出
{
ArcNode *p;
for(i=0;iadjvex);
printf("(%d,%d) ",adjlist[i].vertex,adjlist[p->adjvex].vertex);
p=p->next;
}
printf("n");
}
}
基于邻接表的深度优先遍历
⑴ 访问顶点v；
⑵ 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；
⑶ 重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。
代码如下：
int DFSTraverse(int v)//基于邻接表的深度优先遍历
{
Arcnode *p;
p=adjlist[v].firstedge;
printf("%d ",adjlist[v].vertex);
visited[v]=1;
while(p)
{
j=p->adjvex;
if(visited[j]==0)
DFSTraverse(j);
p=p->next;
}
}
基于邻接表的广度优先遍历
⑴ 访问顶点v；
⑵ 依次访问v的各个未被访问的邻接点v1, v2, …, vk；
⑶ 分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。
代码如下：
int DFSTraverse2(int v)//基于邻接表的广度优先输出
{
Arcnode *p;
int rear=-1,front=-1;
int Q[vertexnum];
printf("%d ",adjlist[v].vertex);
visited[v]=1;
Q[++rear]=v;
while(rear!=front)
{
v=Q[++front];
p=adjlist[v].firstedge;
while(p)
{
j=p->adjvex;
if(visited[j]==0)
{
printf("%d ",adjlist[j].vertex);
visited[j]=1;
Q[++rear]=j;
}
p=p->next;
}
}
}
主函数
main()
{menu();
printf("请输入你要选择的功能： ");
int n;
scanf("%d",&n);
while(n)
{
switch(n)
{
case 0:break;
case 1:creatGraph(vertexnum,vertexarc); //创建图的邻接矩阵结构
break;
case 2:ALgraph(vertexnum,vertexarc);// 创建图的邻接表结构
break;
case 3:display(vertexnum,vertexarc);//输出图的邻接矩阵
break;
case 4:displayAlgraph(vertexnum);//输出图的邻接表
break;
case 5:puts("深度优先遍历输出");
DFSTraversel(0);//基于邻接矩阵的深度优先遍历
putchar('n');//换行
initVisited(vertexnum);//初始化visited数组
break;
case 6: DFSTraversel2(0);//基于邻接矩阵的广度优先遍历
putchar('n');//换行
initVisited(vertexnum);//初始化visited数组
break;
case 7:
puts("深度优先遍历输出");
DFSTraverse(0);//基于邻接表的深度优先遍历
putchar('n');//换行
initVisited(vertexnum);//初始化visited数组
break;
case 8:puts("广度优先遍历输出");
DFSTraverse2(0);//基于邻接表的广度优先遍历
putchar('n');//换行
initVisited(vertexnum);//初始化visited数组
break;
}
menu();
scanf("%d",&n);
}
}
