图
初始化visited数组
这个用于后面图的遍历算法
//初始化visited数组
void initVisited(int vertexNum)
{
int i;
for (i=0; i<vertexNum; i++)
visited[i] = 0;
}
1. 邻接矩阵
V0与V1、V2、V3都有边，因此第0行的1、2、3位置处置1。
Vi与Vj有边，则第i行的第j位置处置1。
由上图可知，一个图，需要
- 一个二维数组
- 每个点的信息（为了方便，将点信息统一放在一个一维数组里面）
注：若需要记录出入度，将对应注释解除即可
1.1 定义结构
#include <stdio.h>
typedef int datatype;
#define N 10
//用于存储图的邻接矩阵的数组
struct {
datatype vertex[N]; //顶点信息表
int arc[N][N]; //邻接矩阵
//int degree_out[N]; //顶点的出度
//int degree_in[N]; //顶点的入度
}mGraph;
1.2 创建图的邻接矩阵（重点）
//创建图的邻接矩阵
int MGraph( )
{ int vertexNum,arcNum;
int i,j,k;
//datatype vertex[N];
printf("请输入顶点个数和边的个数：");
scanf("%d%d",&vertexNum, &arcNum);
printf("请输入顶点的值：");
for (i=0; i<vertexNum; i++)
scanf("%d",&mGraph.vertex[i]);
//初始化邻接矩阵
for (i=0; i<vertexNum; i++)
for (j=0; j<vertexNum; j++)
mGraph.arc[i][j]=0;
//for (i=0; i<vertexNum; i++) //初始化邻接矩阵中顶点的出度值和入度值
//{ mGraph.degree_out[i] = 0; mGraph.degree_in[i] = 0; }
printf("请输入边（边依附的两个顶点的序号）：");
for (k=0; k<arcNum; k++) //依次输入每一条边
{
scanf("%d%d",&i,&j); //边依附的两个顶点的序号
i--; j--; //习惯中的序号从1开始，需要-1
mGraph.arc[i][j]=1; //置有边标志
mGraph.arc[j][i]=1; //置有边标志
//mGraph.degree_out[i]++; //计算顶点的出度
//mGraph.degree_in[j]++; //计算顶点的出度
}
return vertexNum;
}
1.3 输出图的邻接矩阵 （重点）
//输出图的邻接矩阵
void display(int vertexNum)
{ int i,j;
printf("\n输出顶点的值：\n");
for (i=0; i<vertexNum; i++) //输出顶点的值
printf("%d ",mGraph.vertex[i]);
printf("\n输出邻接矩阵：\n");
for (i=0; i<vertexNum; i++) //输出邻接矩阵
{ for (j=0; j<vertexNum; j++)
printf(" %d " ,mGraph.arc[i][j]);
//打印一行之后记得换行
printf("\n");
}
}
1.4 图的深度优先遍历 （邻接矩阵上） （重点）
//图的深度优先遍历 （邻接矩阵上）
int visited[N];
void DFSTraverse1(int i,int vertexNum)
{
printf("%d ",mGraph.vertex[i]);
visited [i]=1;
for (int j=0; j<vertexNum; j++)
if (mGraph.arc[i][j]==1 && visited[j]==0)
DFSTraverse1( j , vertexNum);
}
1.5 图的广度优先遍历 （邻接矩阵上）
//图的广度优先遍历 （邻接矩阵上）
void BFSTraverse1(int v,int vertexNum)
{ int front,rear,Q[N];
int j;
front=rear=-1; //假设采用顺序队列且不会发生溢出
printf("%d ",mGraph.vertex[v]);
visited[v]=1; Q[++rear]=v;
while (front!=rear)
{
v=Q[++front];
for (j=0; j<vertexNum; j++)
if (mGraph.arc[v][j]==1 && visited[j]==0 ) {
printf("%d ",mGraph.vertex[j]);
visited[j]=1; Q[++rear]=j;
}
}
}
1.6 输出顶点的度（基于邻接矩阵的）
void printDegree1(int vertexNum)
{ int i;
for (i=0; i<vertexNum; i++)
printf("顶点 %d 的出度为： %d ，入度为： %d\n",mGraph.vertex[i],mGraph.degree_out[i],mGraph.degree_in[i]);
}
2. 邻接表
结构图
只考虑无向图，看无向图G5，v1与v2、v3有边，因此表头节点v1的first域后接2、3
由上图可知，构造一个邻接表需要
- 表头节点，包含data和first（first相当于边表的head，书上为啥叫first我也不知道）
- 表节点，包含连接的点vertex和next。（包含表头节点的关联节点）
2.1 定义
struct VertexNode //顶点
{
datatype data;
struct ArcNode *first;
//int degree_out; //顶点的出度
//int degree_in; //顶点的入度
} adjlist[N];
struct ArcNode //边表
{ int vertex;
struct ArcNode *next;
};
2.2 创建图的邻接表 （重点）
//创建图的邻接表
int ALGraph( )
{
int vertexNum,arcNum;
datatype x;
int i,j,k;
struct ArcNode *s;
printf("请输入顶点个数和边的个数：");
scanf("%d%d",&vertexNum, &arcNum);
printf("请输入顶点的值：");
for (i=0; i<vertexNum; i++)
//输入顶点信息，初始化边表
{ scanf("%d",&x);
adjlist[i].data= x;
adjlist[i].first=NULL;
//adjlist[i].degree_in = 0; adjlist[i].degree_out = 0; //初始化入度和出度值
}
printf("请输入边（边依附的两个顶点的序号）：");
for (k=0; k<arcNum; k++)
//输入边的信息存储在边表中
{
scanf("%d%d",&i,&j);
i--; j--;
//头插法
s=(struct ArcNode*)malloc(sizeof(struct ArcNode));
s->vertex=j;
s->next=adjlist[i].first;
adjlist[i].first=s;
//adjlist[j].degree_in++ ; adjlist[i].degree_out++; //统计入度和出度值
}
return vertexNum;
}
2.3 输出图的邻接表结构 （重点）
//输出图的邻接表结构
void displayALgraph(int vertexNum)
{ int i,j;
datatype x,y;
struct ArcNode *p;
printf("\n输出顶点的值及其邻接边：\n");
for (i=0; i<vertexNum; i++) //输出顶点的值
{
x = adjlist[i].data;
printf("%d :", x );
p = adjlist[i].first;
while( p )
{
j = p->vertex;
y = adjlist[j].data;
printf("(%d,%d) ",x,y);
p = p->next;
}
printf("\n");
}
}
2.4 图的深度优先遍历 （邻接表） （重点）
//图的深度优先遍历 （邻接表上）
void DFSTraverse2(int i)
{ struct ArcNode *p;
int j=0;
printf("%d ",adjlist[i].data);
visited[i]=1;
p=adjlist[i].first;
while (p!=NULL)
{
j = p->vertex;
if (visited[j]==0) DFSTraverse2(j);
p=p->next;
}
}
2.5 图的广度优先遍历 （邻接表上）
//图的广度优先遍历 （邻接表上）
void BFSTraverse2(int v)
{ struct ArcNode *p;
int front,rear,Q[N];
int j;
front=rear=-1;
printf("%d ",adjlist[v].data); visited[v]=1; Q[++rear]=v;
while (front!=rear)
{
v=Q[++front]; p=adjlist[v].first;
while (p!=NULL)
{
j = p->vertex;
if (visited[j]==0)
{ printf("%d ",adjlist[j].data);
visited[j]=1; Q[++rear]=j;
}
p=p->next;
}
}
}
2.6 输出顶点的度（基于邻接表的）
void printDegree2(int vertexNum)
{ int i;
for (i=0; i<vertexNum; i++)
printf("顶点 %d 的出度为： %d ，入度为： %d\n",adjlist[i].data,adjlist[i].degree_out,adjlist[i].degree_in);
}
2.7 删除邻接表中的全部边结点
//删除邻接表中的全部边结点
void deleteAdjllist(int vertexNum)
{
int i,j;
struct ArcNode *p;
for (i=0; i<vertexNum; i++)
{
p = adjlist[i].first;
while( p )
{
adjlist[i].first= p->next;
free(p);
p = adjlist[i].first;
}
}
}
3. 拓扑排序
//拓扑排序
void toposort(int vertexNum)
{
int i,j;
struct ArcNode *p;
int indegree[N]={0};
int top = -1, stack[N];
int count = 0;
for (i=0; i<vertexNum; i++)
{ indegree[i] = adjlist[i].degree_in;
if(indegree[i] == 0) stack[++top] = i;
}
while(top!= -1)
{
i = stack[top]; top--;
printf("%d ",adjlist[i].data);
count++;
for(p = adjlist[i].first; p != NULL; p = p->next)
{
j = p->vertex;
indegree[j]--;
if(indegree[j]==0)
stack[++top] = j;
}
}
printf("\n");
if(count < vertexNum)printf("有回路！\n");
}
记忆总结
- 创建邻接矩阵，
a. 先初始化为0
b. 输入边对应的点i,j
c. 将i,j和j,i对应的点设为1（若ij是从1开始，则需要先减1） - 输出邻接矩阵就是输出二维数组，没啥好说的，别忘了把顶点信息表也输出，以及注意控制换行
- 邻接矩阵的深度优先
a. 利用visited，若visited访问过了，就置为1.
b. 递归条件： mGraph.arc[v][j]==1 && visited[j]==0 该点有边且未被访问过
- 创建邻接表
a. 记得先初始化顶点表，所有的first=NULL
b. 从顶点表到边表使用的是头插法 - 输出邻接表
a. 遍历顶点，先输出顶点，然后通过顶点的first遍历单链表 - 深度优先遍历邻接表递归条件：if (visited[j]==0) DFSTraverse2(j);
京公网安备 11010502036488号