#一日小结# 还是为了番茄

List.h

include

include

include

define MAXVEX 100 //最大顶点个数

define INFINITY 65535

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(Graph
G);
void Topsort(Graph *G);

Create_print_list.cpp

include”list.h”

//根据输入的字符串,得到对应的数字标号,例如输入v0,返回0
int getmark(VertexType s,Graph *G)
{
int i;
for(i=0;ivexnum;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;ivexnum;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

include”list.h”

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;ivexnum;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;jvexnum;j++)//找到没有排序的个数count
{
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

include”list.h”

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

include”list.h”

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;ivexnum;i++)
{
k=0;
for(j=0;jvexnum;j++)
{
if(record[i][j]==1)
tree[i][k++]=j;
}
}
////////////第二步如果新选中的边的两个顶点已经都被选中过,就返回0,即放弃此边//////////////////////////////////////////////////////////
for(i=0;ivexnum;i++)
{
flag=0;
for(j=0;jvexnum;j++)
{
if(tree[i][j]==m||tree[i][j]==n)
flag++;
}
}
if (flag==2) return 0;
else return 1;
}
void Kruskal(Graph
G)
{
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)&&not_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

include”list.h”

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

include”list.h”

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

include

include

include

define MAXVEX 100 //最大顶点个数

define INFINITY 65535

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(Graph
G);

void Topsort(Graph *G);

Create_print_list.cpp

include”matrix.h”

int getmark(VertexType s,Graph G)//根据输入的字符串,得到对应的数字标号,例如输入v0,返回0
{
int i;
for(i=0;ivexnum;i++)
{
if(strcmp(s,G->vexs[i])==0) return i;
}
return -1;
}
void CreateGraph(Graph
G)
{

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;ivexnum;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”);
}
}

  • 1
  • +11番茄
  • 752只自习生围观
  • 2017年12月19日 18:15打卡
  • 6 年,3 月前有动静
  • 引用
  • 举报

  • 公达
  • 6 年,3 月前
  • 2017年12月20日 09:34

有点过了啊

合作伙伴

线上在线自习室晚自习。番茄工作法、四象限、打卡、作业清单、作业辅导、作业交流、作业跟踪、作业计划、个人宣传相关内容

行恒 © 行恒 2013