这个用于后面图的遍历算法
//初始化visited数组
void initVisited(int vertexNum)
{
int i;
for (i=0; i<vertexNum; i++)
visited[i] = 0;
}
V0与V1、V2、V3都有边,因此第0行的1、2、3位置处置1。 Vi与Vj有边,则第i行的第j位置处置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;
//创建图的邻接矩阵
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;
}
//输出图的邻接矩阵
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");
}
}
//图的深度优先遍历 (邻接矩阵上)
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);
}
//图的广度优先遍历 (邻接矩阵上)
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;
}
}
}
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]);
}
只考虑无向图,看无向图G5,v1与v2、v3有边,因此表头节点v1的first域后接2、3
由上图可知,构造一个邻接表需要
struct VertexNode //顶点
{
datatype data;
struct ArcNode *first;
//int degree_out; //顶点的出度
//int degree_in; //顶点的入度
} adjlist[N];
struct ArcNode //边表
{ int vertex;
struct ArcNode *next;
};
//创建图的邻接表
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;
}
//输出图的邻接表结构
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");
}
}
//图的深度优先遍历 (邻接表上)
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;
}
}
//图的广度优先遍历 (邻接表上)
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;
}
}
}
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);
}
//删除邻接表中的全部边结点
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;
}
}
}
//拓扑排序
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");
}