List.h
typedef enum {DG,DN,UDG,UDN} GraphKind; //{有向图,有向网,无向图,无向网}
//结点定义
typedef char VertexType[3];
typedef int EdgeType;
//边表结点
typedef struct EdgeNode
{
int arc;//邻接点域,存储该顶点对应的下标
EdgeType weight;//用于存储权值,对于非网图可以不需要
struct EdgeNode *next;//链域,指向下一个邻接点
}EdgeNode;
//顶点表结点
typedef struct VertexNode
{
VertexType vex; //顶点域,存储顶点信息
EdgeNode *firstedge; //边表头指针
}VertexNode,VexList[MAXVEX];
typedef struct
{
VexList list;
int vexnum, arcnum;//图中当前顶点数和边数
GraphKind kind; //图的种类标志
}Graph;
int getmark(VertexType s,Graph G);
void CreateGraph(Graph G);
void PrintGraph(Graph *G);
void getdist(int dist[MAXVEX][MAXVEX],Graph*G);//图的距离信息收录
void Dijkslra(VertexType x,VertexType y,Graph*G);
void Prim(GraphG);
void Kruskal(GraphG);
void Topsort(Graph *G);
Create_print_list.cpp
//根据输入的字符串,得到对应的数字标号,例如输入v0,返回0
int getmark(VertexType s,Graph *G)
{
int i;
for(i=0;i
{
if(strcmp(s,G->list[i].vex)==0) return i;
}
return -1;
}
void CreateGraph(Graph G)
{
int i,j,k,w;
EdgeNode e;
VertexType s,t;
FILE *fp = fopen("3_1.txt","r");
if(fp==NULL){printf("cannot open file\n");exit(0);}//打开文件
printf("输入图的类型:\n");
fscanf(fp,"%d",&G->kind);
printf("%d\n",G->kind);
//输入顶点数和边数
printf("输入顶点数和边数:\n");
fscanf(fp,"%d%d",&G->vexnum,&G->arcnum);
printf("%d %d\n",G->vexnum,G->arcnum);
//输入顶点信息,建立顶点表
printf("输入顶点字符:\n");
for(i=0;i<G->vexnum;i++)
{
fscanf(fp,"%s",&G->list[i].vex);
printf("%s",G->list[i].vex);
G->list[i].firstedge=NULL;
}
printf("\n");
//建立边表
for(k=0;k<G->arcnum;k++)
{
if(G->kind%2==0)
{
printf("输入边(vi,vj):\n");
fscanf(fp,"%s%s",&s,&t);
printf("%s%s\n",s,t);
i=getmark(s,G);
j=getmark(t,G);
//(单链表中的头插法)
e = (EdgeNode*)malloc(sizeof(EdgeNode));//向内存申请空间
//生成边表结点
e->arc=j;
e->weight=1;
e->next=G->list[i].firstedge;
G->list[i].firstedge=e;
if(G->kind>1)
{
e = (EdgeNode*)malloc(sizeof(EdgeNode));//向内存申请空间
//生成边表结点
e->arc=i;
e->weight=1;
e->next=G->list[j].firstedge;
G->list[j].firstedge=e;
}
}
else
{
printf("输入边(vi,vj)权:\n");
fscanf(fp,"%s%s%d",&s,&t,&w);
printf("%s%s%d\n",s,t,w);
i=getmark(s,G);
j=getmark(t,G);
//(单链表中的头插法)
e = (EdgeNode*)malloc(sizeof(EdgeNode));//向内存申请空间
//生成边表结点
e->arc=j;
e->weight=w;
e->next=G->list[i].firstedge;
G->list[i].firstedge=e;
if(G->kind>1)
{
e = (EdgeNode*)malloc(sizeof(EdgeNode));//向内存申请空间
//生成边表结点
e->arc=i;
e->weight=w;
e->next=G->list[j].firstedge;
G->list[j].firstedge=e;
}
}
}
fclose(fp);
}
void PrintGraph(Graph G)
{
int i;
EdgeNode p;
printf(“邻接表内容为:\n”);
for(i=0;i
{
printf(“%s\t”,G->list[i].vex);
p=G->list[i].firstedge;
while(p)
{
printf("%d\t",p->arc);
if(G->kind%2==1) printf("%d\t",p->weight);
p=p->next;
}
printf("\n");
}
}
Topsort.cpp
int indegree[MAXVEX];
int flag[MAXVEX]={0};
void GetIndegree(Graph G)
{
int i;
EdgeNode p;
for(i=0;i<G->vexnum;i++)//初始化数组
indegree[i]=0;
for(i=0;i<G->vexnum;i++)//遍历整个图一旦在边中找到顶点的坐标,就将相应顶点indegree[]加一
{
p=G->list[i].firstedge;
while(p)
{
indegree[p->arc]++;
p=p->next;
}
}
}
void DeleteRelated(int v,Graph G)//删除与顶点i有关的弧
{
EdgeNode p,*s;
p=G->list[v].firstedge;
while(p)
{
s=p;
p=p->next;
free(s);
}
G->list[v].firstedge=NULL;
}
void Topsort(Graph *G)
{
int i,j;
int count;//数flag的个数,即没有排的顶点个数
if(G->kind>1){printf("Graph have no derection, cannot topsort\n");return;}
////////////////第一GetIndegree操作更新indegree[]数组///////////////////////////////////////////////////////////////////////
GetIndegree(G);
////////////////第二通过遍历indegree[]数组找到入度为零的顶点////////////////////////////////////////////////////////////////
for(i=0;i
{
if(indegree[i]==0&&flag[i]==0)
{
printf(“%s\t”,G->list[i].vex);
flag[i]=1;
DeleteRelated(i,G);
break;
}
}
///////////////第三设置停止条件为flag[]数组元素全为1。////////////////////////////////////////////////////
for(count=0,j=0;j
{
if(flag[j]==0)count++;
}
if(i==G->vexnum)//如果找不到入度为零的顶点
if(count==0)return;
else {printf("Graph have a cycle, cannot topsort\n");return;}
Topsort(G);
}
Dijkslra.cpp
void getdist(int dist[MAXVEX][MAXVEX],GraphG)//图的距离信息收录
{
int i;
EdgeNode p;
for(i=0;i<G->vexnum;i++)
{
p=G->list[i].firstedge;
while(p)
{
dist[i][p->arc]=p->weight;
p=p->next;
}//通过遍历得到每个顶点之间的距离信息
}
}
void Dijkslra(VertexType x,VertexType y,Graph*G)
{
int distance[MAXVEX]={INFINITY};//记录每一个点到源点的最短距离
int pre[MAXVEX];//记录前一个的下标
int dist[MAXVEX][MAXVEX]={INFINITY};//记录初始距离信息并不再改变
int s[MAXVEX]={0};//集合s
int start,end;//两个点的数组下标
int i;int j;int k;
int temp;
int mindistance=INFINITY;
int minmark;
int no_zero_flag=0;
int remember;
int path[MAXVEX];
EdgeNode*p;
start=getmark(x,G);
end=getmark(y,G);
temp=start;
for(i=0;i<G->vexnum;i++)//赋初值
{
distance[i]=INFINITY;
for(j=0;j<G->vexnum;j++)
{
dist[i][j]=INFINITY;
if(i==j) dist[i][j]=0;
}
}
getdist(dist,G);//初始化全部距离信息资料
for(i=0;i<G->vexnum;i++)
{
pre[i]=temp;//路径初始化
}
distance[start]=0;
while(no_zero_flag==0)//这次困在了达不到的情况
{
remember=temp;
s[temp]=1;//printf("%d",temp);
p=G->list[temp].firstedge;
//////////////////第一步如果通过新选出的顶点,遍历所有相关顶点,若其distance会更短就更新////////////////////////
while(p)
{
if(distance[temp]+p->weight < distance[p->arc])
{
distance[p->arc]=distance[temp]+p->weight;//求全部点到源点的距离distance[]
pre[p->arc]=temp;
}
p=p->next;
}
mindistance=INFINITY;
///////////////////第二步遍历所有distance里最小距离,选中此顶点//////////////////////////////
for(i=0;i<G->vexnum;i++)
{
if(s[i]==0&&distance[i]<mindistance)//所有distance里找最小的
{
mindistance=distance[i];
minmark=i;
}
}
//////////////////第三步确定循环终止条件,所有顶点被选中过///////////////////////////////////////
temp=minmark;
no_zero_flag=1;
for(i=0;i<G->vexnum;i++)//判断是不是全零
{
if(s[i]==0) no_zero_flag=0;
}
/////////////////////
if(temp==remember)break;//这种情况说明有达不到的顶点
}
/////////////////////输出部分///////////////////////
if(distance[end]>=INFINITY)
{
printf("达不到顶点%s\n",G->list[end].vex);
return;
}
printf("距离:\t%d\n",distance[end]);
i=j=k=0;
i=end;
while(i!=start)
{
path[j++]=i;
i=pre[i];
}
path[j]=start;
printf("路径:\t");
for(k=j;k>=0;k--)
{
printf("%s",G->list[path[k]].vex);
if(k==0) printf("\n");
else printf("->");
}
}
Kruskal.cpp
int not_a_tree(int m,int n,int record[MAXVEX][MAXVEX],Graph G)//判断此边是否会使所有选中边连成一个环
{
int i,j,k;
int flag;
int tree[MAXVEX][MAXVEX]={0};
////////////第一步遍历record,记录已经选中的边中和顶点i相连的点/////////////////////////////
for(i=0;i
{
k=0;
for(j=0;j
{
if(record[i][j]==1)
tree[i][k++]=j;
}
}
////////////第二步如果新选中的边的两个顶点已经都被选中过,就返回0,即放弃此边//////////////////////////////////////////////////////////
for(i=0;i
{
flag=0;
for(j=0;j
{
if(tree[i][j]==m||tree[i][j]==n)
flag++;
}
}
if (flag==2) return 0;
else return 1;
}
void Kruskal(Graph
{
int dist[MAXVEX][MAXVEX]={INFINITY};
int record[MAXVEX][MAXVEX]={0};
int i,j;
int min_i,min_j;
int mindistance=INFINITY;
int count=0;
if(G->kind<=1){printf("Graph have direction, cannot kruskal\n");return;}
for(i=0;i<G->vexnum;i++)//赋初值
{
for(j=0;j<G->vexnum;j++)
{
dist[i][j]=INFINITY;
if(i==j) dist[i][j]=0;
}
}
getdist(dist,G);
while(count<G->vexnum-1)//终止条件是找到顶点-1条边
{
mindistance=INFINITY;
///////////////////////第一步遍历dist找到符合条件的最短边,选中///////////////////////////////////////
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
{
if((i!=j)&&(record[i][j]==0)&¬_a_tree(i,j,record,G)&&(dist[i][j]<mindistance))
{
mindistance=dist[i][j];
min_i=i;min_j=j;
}
}
record[min_i][min_j]=1;
record[min_j][min_i]=1;
count=0;
/////////////////////////第二步用record标记找到的边///////////////////////////////////////////////////////
for(i=0;i<G->vexnum;i++)
{
for(j=0;j<i;j++)
{
if(record[i][j]==1) count++;
//printf("%d\t",count);
}
}
}
/////////输出//////////////////
printf("kruskal最小生成树:\n");
for(i=0;i<G->vexnum;i++)
for(j=0;j<i;j++)
if(record[i][j]==1)
printf("%s-%s\t",G->list[i].vex,G->list[j].vex);
printf("\n");
}
Prim.cpp
void Prim(Graph*G)
{
int distance[MAXVEX]={INFINITY};
int pre[MAXVEX];//记录前一个的下标
int dist[MAXVEX][MAXVEX]={INFINITY};
int s[MAXVEX]={0};//集合s
int start=0;//两个点的数组下标
int i;int j;
int mindistance=INFINITY;
int minmark;
int zeroflag=0;
EdgeNode*p;
if(G->kind<=1){printf("Graph have direction, cannot prim\n");return;}
for(i=0;i<G->vexnum;i++)//赋初值
{
distance[i]=INFINITY;
for(j=0;j<G->vexnum;j++)
{
dist[i][j]=INFINITY;
if(i==j) dist[i][j]=0;
}
}
getdist(dist,G);//初始化全部距离信息资料
for(i=0;i<G->vexnum;i++)
{
pre[i]=start;//路径初始化
}
while(zeroflag==0)
{
s[start]=1;//printf("%d",start);
distance[start]=0;
p=G->list[start].firstedge;
////////////第一步如果通过新选出的顶点,遍历所有相关顶点,若其distance会更短就更新//////////////////////////////
while(p)
{
if(p->weight < distance[p->arc])
{
distance[p->arc]=p->weight;//求全部点到集合中点的距离distance[]
pre[p->arc]=start;
}
p=p->next;
}
mindistance=INFINITY;
///////////////第二步遍历所有distance里最小距离,选中此顶点////////////////////////////////
for(i=0;i<G->vexnum;i++)
{
if(s[i]==0&&distance[i]<mindistance)//所有distance里找最小的
{
mindistance=distance[i];
minmark=i;
}
}
////////////////第三步确定循环终止条件,所有顶点被选中过/////////////////////////////////////////
start=minmark;
zeroflag=1;
for(i=0;i<G->vexnum;i++)//判断是不是全零
{
if(distance[i]!=0) zeroflag=0;
}
}
/////////////////下面是代码的第二部分,输出结果/////////////////////////////////////////
printf("Prim最小生成树:\n");
for(i=0;i<G->vexnum;i++)
{
if(i!=pre[i])
printf("%s-%s\t",G->list[pre[i]].vex,G->list[i].vex);
}
printf("\n");
}
Main.cpp
void main()
{
Graph G;
VertexType x,y;
CreateGraph(&G);
PrintGraph(&G);
printf("请输入起点终点(例如a f):");
scanf("%s%s",x,y);
Dijkslra(x,y,&G);
Prim(&G);
Kruskal(&G);
printf("拓扑排序:\n");
Topsort(&G);
}
(一)领接矩阵结构为基础的代码
List.h
typedef enum {DG,DN,UDG,UDN} GraphKind; //{有向图,有向网,无向图,无向网}
typedef char VertexType[3];
typedef int EdgeType;
typedef struct
{
VertexType vexs[MAXVEX]; //存储顶点的一维数组
EdgeType arcs[MAXVEX][MAXVEX]; //存储邻接矩阵的二维数组
int vexnum, arcnum; //图的当前顶点数和弧数
GraphKind kind; //图的种类标志
}Graph;
int getmark(VertexType s,Graph G);//通过字符得到对应顶点下标
void CreateGraph(Graph G);
void PrintGraph(Graph *G);
void getdist(int dist[MAXVEX][MAXVEX],Graph*G);//图的距离信息收录
void Dijkslra(VertexType x,VertexType y,Graph*G);
void Prim(GraphG);
void Kruskal(GraphG);
void Topsort(Graph *G);
Create_print_list.cpp
int getmark(VertexType s,Graph G)//根据输入的字符串,得到对应的数字标号,例如输入v0,返回0
{
int i;
for(i=0;i
{
if(strcmp(s,G->vexs[i])==0) return i;
}
return -1;
}
void CreateGraph(Graph
{
int i,j,k,w;
VertexType s,t;
FILE *fp = fopen("3_1.txt","r");
if(fp==NULL){printf("cannot open file\n");exit(0);}//打开文件
printf("输入图的类型:\n");
fscanf(fp,"%d",&G->kind);
printf("%d\n",G->kind);
printf("输入顶点数和边数:\n");
fscanf(fp,"%d%d",&G->vexnum,&G->arcnum);//输入顶点数和边数
printf("%d %d\n",G->vexnum,G->arcnum);
printf("输入顶点字符:\n");
for(i=0;i<G->vexnum;i++)//读入顶点信息,建立顶点表
{
fscanf(fp,"%s",&G->vexs[i]);
printf("%s",G->vexs[i]);
}
printf("\n");
if(G->kind%2==1)//如果是网,输入权值
{
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
G->arcs[i][j]=INFINITY;//邻接矩阵初始化
for(k=0;k<G->arcnum;k++)//读入arcnum条边,建立邻接矩阵
{
printf("输入边(vi,vj),权w:\n");
fscanf(fp,"%s%s%d",&s,&t,&w);//输入边(vi,vj)上的权w
printf("%s%s%d\n",s,t,w);
i=getmark(s,G);
j=getmark(t,G);
G->arcs[i][j]=w;
if(G->kind>1)
G->arcs[j][i] = G->arcs[i][j];//因为是无向图,矩阵对称
}
}
else//如果不是网,输入0,1
{
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
G->arcs[i][j]=0;//邻接矩阵初始化
for(k=0;k<G->arcnum;k++)//读入arcnum条边,建立邻接矩阵
{
printf("输入边(vi,vj):\n");
fscanf(fp,"%s%s",&s,&t);//输入边(vi,vj)
printf("%s%s\n",s,t);
i=getmark(s,G);
j=getmark(t,G);
G->arcs[i][j]=1;
if(G->kind>1)
G->arcs[j][i] = G->arcs[i][j];//因为是无向图,矩阵对称
}
}
fclose(fp);
}
void PrintGraph(Graph *G)
{
int i,j,k;
printf(“顶点数组的内容为:\n”);
for(i=0;i
printf(“%s”,G->vexs[i]);
printf(“\n”);
printf(“邻接矩阵的内容为:\n”);
for(j=0;j<=5;j++)
{
for(k=0;k<=5;k++)
printf(“%d\t”,G->arcs[j][k]);
printf(“\n”);
}
}
有点过了啊