通过代码快速上手C语言数据结构-图

以你之姓@ 2023-01-16 02:41 144阅读 0赞

# 7.1采用邻接矩阵表示法创建有向图 #

/*用邻接矩阵法创建有向网的算法如下：*/
    #include "stdlib.h"
    #include "stdio.h"
    
    #define MAX_VERTEX_NUM 10             /*最多顶点个数*/
    #define INFINITY 32768             /*表示极大值，即∞*/
    #define True 1
    #define False 0
    #define Error -1
    #define Ok 1
    
    typedef enum{DG, DN, UDG, UDN} GraphKind;  /*图的种类：DG表示有向图, DN表示有向网, UDG表示无向图, UDN表示无向网*/
    typedef char VertexData;    /*假设顶点数据为字符型*/
    
    typedef struct ArcNode
    {
    	int adj;   /*对于无权图，用1或0表示是否相邻；对带权图，则为权值类型*/
    
    } ArcNode;
    
    typedef struct
    {
    	VertexData vexs[MAX_VERTEX_NUM];                        /*顶点向量*/
    	ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];   /*邻接矩阵*/
    	int vexnum,arcnum;          /*图的顶点数和弧数*/
    	GraphKind kind;                 /*图的种类标志*/
    }AdjMatrix;      /*(Adjacency Matrix Graph)*/
    
    int LocateVertex(AdjMatrix *G,VertexData v)    /*求顶点位置函数*/
    {
    	int j=Error,k;
    	for(k=0;k<G->vexnum;k++)
    		if(G->vexs[k]==v)
    		{ 
    			j=k; 
    			break; 
    		}
    	return(j);
    }
    
    
    
    int CreateDN(AdjMatrix *G)  /*创建一个有向网*/
    { 
    	int i,j,k,weight; 
    	VertexData v1,v2;
    	printf("输入图的弧数和顶点数\n");
    	fflush(stdin);
        scanf("%d,%d",&G->arcnum,&G->vexnum); /*输入图的顶点数和弧数*/
        for(i=0;i<G->vexnum;i++)       /*初始化邻接矩阵*/
    		for(j=0;j<G->vexnum;j++)
    			G->arcs[i][j].adj=INFINITY;
        for(i=0;i<G->vexnum;i++)
    	{
            printf("输入图的顶点\n");
    		fflush(stdin);
    		scanf("%c",&G->vexs[i]);  /* 输入图的顶点*/
    	}
    	for(k=0;k<G->arcnum;k++)
    	{ 
    		printf("输入一条弧的两个顶点及权值\n");
    		fflush(stdin);
    		scanf("%c,%c,%d",&v1,&v2,&weight);/*输入一条弧的两个顶点及权值*/
    	  	i=LocateVertex(G,v1);
    	    j=LocateVertex(G,v2); 
    	    G->arcs[i][j].adj=weight;  /*建立弧*/
    	} 
    	return(Ok);
    }
    
    void main()
    {
    	AdjMatrix G;
    	CreateDN(&G);
    }

# 7.2创建图的十字链表 #

/*建立一个有向图的十字链表的算法如下：*/
    /*图的十字链表结构形式化定义如下：*/
    #include <malloc.h>
    #include <stdio.h>
    #define MAX_VERTEX_NUM 10              /*最多顶点个数*/
    #define INFINITY 32768             /*表示极大值，即∞*/
    #define True 1
    #define False 0
    
    #define Error -1
    #define Ok 1
    typedef enum{DG, DN, UDG, UDN} GraphKind;  /*图的种类*/
    typedef char VertexData;    /*假设顶点数据为字符型*/
    
    
    typedef struct ArcNode 
    {
    	int tailvex,headvex;  
    	struct ArcNode *hlink,*tlink;    
    }ArcNode;
    
    typedef struct VertexNode
    {
    	VertexData data;    /*顶点信息*/
    	ArcNode *firstin,*firstout;   
    }VertexNode;
    
    typedef struct
    {
    	VertexNode vertex[MAX_VERTEX_NUM];   
    	int vexnum,arcnum;   /*图的顶点数和弧数*/
    	GraphKind kind;              /*图的种类*/
    }OrthList;      /*图的十字链表表示法(Orthogonal List)*/
    
    int LocateVertex(OrthList *G,VertexData v)    /*求顶点位置函数*/
    {
    	int j=Error,k;
    	for(k=0;k<G->vexnum;k++)
    		if(G->vertex[k].data==v)
    		{ 
    			j=k; 
    			break; 
    		}
    	return(j);
    }
    
    void  CrtOrthList(OrthList *g)
    /*从终端输入n个顶点的信息和e条弧的信息，以建立一个有向图的十字链表*/
    {
    	int n,e;
    	int i,j,k;
    	char vt,vh;
    
    	ArcNode *p;
    	printf("从键盘输入图的顶点个数和弧的个数");
    	fflush(stdin);
    	scanf("%d,%d",&n,&e);  /*从键盘输入图的顶点个数和弧的个数*/
    	g->vexnum = n;
    	g->arcnum = e;
    	for(i=0;i<n;i++) 
    	{
    		printf("输入图的顶点");
    		fflush(stdin);
    		scanf("%c",&g->vertex[i].data);
    		g->vertex[i].firstin=NULL;g->vertex[i].firstout=NULL;
    	}
    	for(k=0;k<e;k++) 
    	{
    		printf("输入一条弧的两个顶点");
    		fflush(stdin);
    		scanf("%c,%c",&vt,&vh);
    		i=LocateVertex(g,vt);
    		j = LocateVertex(g,vh);
    		p=(ArcNode*)malloc(sizeof(ArcNode));
    		p->tailvex=i;
    		p->headvex=j;
    		p->tlink=g->vertex[i].firstout;
    		g->vertex[i].firstout=p;
    		p->hlink=g->vertex[j].firstin;
    		g->vertex[j].firstin=p;
        }
    }/* CrtOrthList */
    
    void main()
    {
    	OrthList g;
    	CrtOrthList(&g);
    }

# 7.3-7.9图的遍历 #

*  ### 7.3深度优先遍历图 ###
 *  ### 7.4深度优先遍历v0所在的连通子图 ###
 *  ### 7.5采用邻接矩阵的DepthFirstSearch ###
 *  ### 7.6采用邻接表的DepthFirstSearch ###
 *  ### 7.7非递归形式的DepthFirstSearch ###
 *  ### 7.8广度优先搜索图g中v0所在的连通子图 ###
 *  ### 7.9深度优先找出从顶点u到v的简单路径 ###

#define N 10
    #define INFINITY  32768
    #define True 1
    #define False 0
    #define Error -1
    #define Ok 1
    
    #include "stdlib.h"
    #include "stdio.h"
    
    typedef enum{DG,DN,UDG,UDN}GraphKind;
    typedef char VertexData;
    
    typedef struct ArcNode1
    {
    	int adj;
    } ArcNode1;
    
    typedef struct
    {
    	VertexData vexs[N];
    	ArcNode1 arcs[N][N];
    	int vexnum1,arcnum1;
    	GraphKind kind1;
    }AdjMatrix;
    
    /*..............................  */
    typedef struct ArcNode2
    {
    	int adjvex;
    	struct ArcNode2 *nextarc;
    } ArcNode2;
    
    typedef struct VertexNode
    {
    	VertexData data;
    	ArcNode2 *firstarc;
    }VertexNode;
    
    typedef struct
    {
    	VertexNode vertex[N];
    	int vexnum2,arcnum2;
    	GraphKind kind2;
    }AdjList;
    /*.............................*/
    
    typedef struct Node
    {
    	int data;
    	struct Node *next;
    }LinkQueueNode;
    
    typedef struct
    {
    	LinkQueueNode *front;
    	LinkQueueNode *rear;
    }LinkQueue;
    
    int InitQueue(LinkQueue *Q)
    {
    	Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));
    	if(Q->front!=NULL)
    	{
    		Q->rear=Q->front;
    		Q->front->next=NULL;
    		return(True);
    	}
    	else  
    		return(False);
    }
    
    int EnterQueue(LinkQueue *Q,int x)
    {
    	LinkQueueNode *NewNode;
    	NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));
    	if(NewNode!=NULL)
    	{
    		NewNode->data=x;
    		NewNode->next=NULL;
    		Q->rear->next=NewNode;
    		Q->rear=NewNode;
    		return(True);
    	}
    	else 
    		return(False);
    }
    
    int DeleteQueue(LinkQueue *Q,int *x)
    {
    	LinkQueueNode *p;
    	if(Q->front==Q->rear)
    		return(False);
    	p=Q->front->next;
    	Q->front->next=p->next;
        if(Q->rear==p)
    		Q->rear=Q->front;
    	*x=p->data;
    	free(p);
    	return(True);
    }
    
    int IsEmpty(LinkQueue *Q)
    {
    	if(Q->front==Q->rear)
    		return(True);
    	else 
    		return(False);
    }
    /*..........................*/
    
    typedef struct node1
    {
    	char data;
    	struct node1 *next;
    }Node1, *LinkList1;
    
    typedef struct node2
    {
    	char data1;
    	char data2;
    	struct node2 *next;
    }Node2, *LinkList2;
    
    int a[2];
    int visited[N];
    
    int LocateVertex1(AdjMatrix *G1,VertexData v)
    {
    	int k,j=Error;
    	for(k=0;k<G1->vexnum1;k++)
    		if(G1->vexs[k]==v)
    		{
    			j=k;
    			break;
    		}
    	return(j);
    }
    
    int CreateUDG1(AdjMatrix *G1,LinkList1 *bt,LinkList2 *br)
    {
    	int i,j,k;
    	Node1 *r,*p;
    	Node2 *s,*q;
    	VertexData v1,v2;
    	(*bt)=(LinkList1)malloc(sizeof(Node1));
    	(*br)=(LinkList2)malloc(sizeof(Node2));
    	(*bt)->next=NULL;
    	(*br)->next=NULL;
    	r=*bt;   
    	s=*br;
    	printf("\ninput G->vexnum,G->arcnum\n");
    	scanf("%d,%d",&(G1->vexnum1),&(G1->arcnum1));
    	getchar();
    	a[0]=G1->vexnum1; a[1]=G1->arcnum1;
    	for(i=0;i<G1->vexnum1;i++)
    		for(j=0;j<G1->vexnum1;j++)
    			G1->arcs[i][j].adj=0;
    	printf("input G->vexs\n");
    	for(i=0;i<G1->vexnum1;i++)
    	{
    		scanf("%c",&(G1->vexs[i]));
    		p=(Node1*)malloc(sizeof(Node1));
    		p->data=G1->vexs[i];
    		p->next=NULL;
    		r->next=p;
    		r=p;
    	}
    	getchar( );
    	printf("input G v1,v2\n");
    	for(k=0;k<G1->arcnum1;k++)
    	{ 
    		scanf("%c",&v1);
    		scanf("%c",&v2);
    		getchar( );
    		q=(Node2*)malloc(sizeof(Node2));
    		q->data1=v1;
    		q->data2=v2;
    		q->next=NULL;
    		s->next=q;
    		s=q;
    		i=LocateVertex1(G1,v1);
    		j=LocateVertex1(G1,v2);
    		G1->arcs[i][j].adj=1;
    		G1->arcs[j][i].adj=1;
    	}
    	return(Ok);
    }
    /*........................*/
    
    int LocateVertex2(AdjList *G2,VertexData v)
    {
    	int k,j=Error;
    	for(k=0;k<G2->vexnum2;k++)
    		if(G2->vertex[k].data==v)
    		{
    			j=k;
    			break;
    		}
    	return(j);
    }
    
    int CreateUDG2(AdjList *G2,LinkList1 L,LinkList2 M)
    {
    	int i,j,k;
    	//char ch;
    	Node1 *m,*t;
    	Node2 *n,*s;
    	ArcNode2 *p,*r;
    	VertexData v1,v2;
    	G2->vexnum2=a[0];  G2->arcnum2=a[1];
    	for(i=0;i<G2->vexnum2;i++)
    	{ 
    		m=L->next; 
    		t=m;
    		G2->vertex[i].data=t->data;
    		L->next=L->next->next;
    		free(m);
    		G2->vertex[i].firstarc=NULL;
    	}
    	for(k=0;k<G2->arcnum2;k++)
    	{
    		s=M->next;  
    		n=s;
    		v1=n->data1;  
    		v2=n->data2;
    		M->next=M->next->next;
    		free(s);
    		i=LocateVertex2(G2,v1);
    		j=LocateVertex2(G2,v2);
    		if(G2->vertex[i].firstarc==NULL)
    		{
    			p=(ArcNode2*)malloc(sizeof(ArcNode2));
    			if(p==NULL)
    				return(False);
    			G2->vertex[i].firstarc=p;
    			p->adjvex=j;
    			p->nextarc=NULL;
    		}
    		else
    		{
    			r=G2->vertex[i].firstarc;
    			while(r->nextarc!=NULL)
    			r=r->nextarc;
    			p=(ArcNode2*)malloc(sizeof(ArcNode2));
    			if(p==NULL)
    				return(False);
    			r->nextarc=p;
    			p->adjvex=j;
    			p->nextarc=NULL;
    		}
    		if(G2->vertex[j].firstarc==NULL)
    		{
    			p=(ArcNode2*)malloc(sizeof(ArcNode2));
    			if(p==NULL)
    				return(False);
    			G2->vertex[j].firstarc=p;
    			p->adjvex=i;
    			p->nextarc=NULL;
    		}
    		else
    		{
    			r=G2->vertex[j].firstarc;
    			while(r->nextarc!=NULL)
    			r=r->nextarc;
    			p=(ArcNode2*)malloc(sizeof(ArcNode2));
    			if(p==NULL)
    				return(False);
    			r->nextarc=p;
    			p->adjvex=i;
    			p->nextarc=NULL;
    		}	
    	}
    	return(Ok);
    }
    /*............................*/
    
    void Depth1(AdjMatrix g1,int vo)
    {
    	int vj;
    	printf("%c",g1.vexs[vo]);
    	visited[vo]=True;
    	for(vj=0;vj<g1.vexnum1;vj++)
    		if((!visited[vj])&&(g1.arcs[vo][vj].adj==1))
    	Depth1(g1,vj);
    }
    
    void Depth2(AdjList g2,int vo)
    {
    	ArcNode2 *p;
    	printf("%c",g2.vertex[vo].data);
    	visited[vo]=True;
    	p=g2.vertex[vo].firstarc;
    	while(p!=NULL)
    	{
    		if(!visited[p->adjvex])
    		Depth2(g2,p->adjvex);
    		p=p->nextarc;
    	}
    }
    
    void Breadth1(AdjMatrix g1,int vo)
    {
    	int vi,vj;
    	LinkQueue Q;
    	InitQueue(&Q);
    	visited[vo]=True;
    	EnterQueue(&Q,vo);
    	while(!IsEmpty(&Q))
    	{
    		DeleteQueue(&Q,&vi);
    		printf("%c",g1.vexs[vi]);
    		for(vj=0;vj<g1.vexnum1;vj++)
    			if((!visited[vj])&&(g1.arcs[vi][vj].adj==1))
    			{
    				visited[vj]=True;
    				EnterQueue(&Q,vj);
    			}
    	}
    }
    
    void Breadth2(AdjList g2,int vo)
    {
    	ArcNode2 *p;
    	int vi;
    	LinkQueue Q;
    	InitQueue(&Q);
    	visited[vo]=True;
    	EnterQueue(&Q,vo);
    	while(!IsEmpty(&Q))
    	{
    		DeleteQueue(&Q,&vi);
    		printf("%c",g2.vertex[vi].data);
    		p=g2.vertex[vi].firstarc;
    		while(p!=NULL)
    		{
    			if(!visited[p->adjvex])
    			{
    				visited[p->adjvex]=True;
    				EnterQueue(&Q,p->adjvex);
    			}
    			p=p->nextarc;
    		}
    	}
    }
    
    void Traverse1(AdjMatrix g1)
    {
    	int vi;
    	for(vi=0;vi<g1.vexnum1;vi++)
    		visited[vi]=False;
    	printf("\nThe order of G1 Depth\n");
    	for(vi=0;vi<g1.vexnum1;vi++)
    	{
    		if(!visited[vi])
    		{
    			Depth1(g1,vi);    
    			printf("\n");
    		}
    	}
    	for(vi=0;vi<g1.vexnum1;vi++)
    		visited[vi]=False;
    	printf("\nThe order of G1 Breadth\n");
    	for(vi=0;vi<g1.vexnum1;vi++)
    	{
    		if(!visited[vi])
    		{
    			Breadth1(g1,vi);    
    			printf("\n");
    		}
    	}
    }
    
    void Traverse2(AdjList g2)
    {
    	int vi;
    	for(vi=0;vi<g2.vexnum2;vi++)
    	visited[vi]=False;
    	printf("\nThe order of G2 Depth\n");
    	for(vi=0;vi<g2.vexnum2;vi++)
    	{
    		if(!visited[vi])
    		{
    			Depth2(g2,vi); 
    			printf("\n");
    		}
    	}
    	for(vi=0;vi<g2.vexnum2;vi++)
    		visited[vi]=False;
    	printf("\nThe order of G2 Breadth\n");
    	for(vi=0;vi<g2.vexnum2;vi++)
        {
    		if(!visited[vi])
    		{
    			Breadth2(g2,vi);   
    			printf("\n");
    		}
    	}
    }
    
    main( )
    { 
    	LinkList1 L;
    	LinkList2 M;
    	AdjMatrix g1;
    	AdjList g2;
    	CreateUDG1(&g1,&L,&M);
    	CreateUDG2(&g2,L,M);
    	Traverse1(g1);
    	Traverse2(g2);
    }

# 7.10普里姆算法 #

// 
     //author: cqm               // 
     //date: 2004-9-23           // 
     //description:Undigraph MST // 
     // 
     #include <stdio.h> 
     #include <malloc.h> 
     #include <limits.h> 
     #define INFINITY INT_MAX                              //INT_MAX表示最大整数，请参阅C的limits.h文件 
     #define n 10                                         //图的顶点数，应由用户定义 
     typedef int AdjMatrix[n][n];                          //用二维数组作为邻接矩阵表示 
     //树边结点 
     typedef struct{                                       
     int fromvex,tovex;                                 //边的起点和终点 
     int length;                                        //边上的权 
     }TreeEdgeNode; 
     typedef TreeEdgeNode MST[n-1];                        //最小生成树类型 
     AdjMatrix G;                                          //连通网的带权邻接矩阵,作为Prim算法的输入 
     MST T;                                                //存放G的最小生成树，作为Prim算法的输出 
    
     //打印错误信息 
     void Error(char *msg) 
     { 
     printf("%c\n",msg); 
     } 
     // 
     void CreateGraph(AdjMatrix G){ 
     int i,j; 
     int start,end,weight; 
     for(i=0;i<n;i++)                                  //n为图的顶点数 
      for(j=0;j<n;j++) 
       G[i][j] = INFINITY;                       //INFINITY代表无穷大 
     printf("输入弧和其权值，格式：弧尾，弧头，权值\n"); 
     for(i=0;i<n-1;i++){ 
      scanf("%d %d %d",&start,&end,&weight); 
      getchar(); 
      G[start][end]=weight; 
      G[end][start]=weight; 
     } 
     } 
     void DefaultCreateGraph(AdjMatrix G){ 
     int i,j; 
     for(i=0;i<n;i++)                                  //n为图的顶点数 
      for(j=0;j<n;j++) 
       G[i][j] = INFINITY; 
     //0-9 
     G[0][1]=4; 
     G[1][0]=4; 
        
     G[1][2]=2; 
     G[2][1]=2; 
    
     G[0][3]=3; 
     G[3][0]=3; 
    
     G[1][5]=1; 
     G[5][1]=1; 
    
     G[3][6]=10; 
     G[6][3]=10; 
    
     G[6][9]=5; 
     G[9][6]=5; 
    
     G[9][7]=2; 
     G[7][9]=2; 
    
     G[7][8]=6; 
     G[8][7]=6; 
    
     G[3][4]=8; 
     G[4][3]=8; 
    
     G[4][5]=1; 
     G[5][4]=1; 
    
     G[2][5]=2; 
     G[5][2]=2; 
    
     G[4][7]=4; 
     G[7][4]=4; 
    
     G[5][8]=4; 
     G[8][5]=4; 
     } 
     //构造初始的时候选轻边集T[0...n-2]，树边集TE!=Null,红点集U={r} 
     void InitCandidateSet(AdjMatrix G,MST T,int r){ 
     int i,k=0; 
     for(i=0;i<n;i++)                                   //依次行成每个蓝点i初始的最短紫边存放在T[k]中 
      if(i!=r){                                      //i是蓝点(r,i)是紫边 
       T[k].fromvex = r;                          //紫边的起点为红点 
       T[k].tovex   = i;                          //紫边的终点为蓝点 
       T[k++].length= G[r][i];                    //紫边长度,注:先取k然后再加一 
      }//endif 
     } 
    
     //在当前候选轻边集中选择一条轻边,即选择长度最短的紫边 
     int SelectLightEdge(MST T,int k){ 
     //在当前候选轻边集T[k..n-2]中选择最短紫边,k<=n-2 
     int min = INFINITY,i,minpos; 
     for(i=k;i<n-1;i++)                                 //遍历当前候选轻边集,找一轻边 
      if(T[i].length < min){ 
       min = T[i].length; 
       minpos = i;                                //记录当前最短紫边位置 
      }//endif 
     if(min==INFINITY)                                  //表示图不连通,不能求MST 
      Error("Graph is disconnected!"); 
     return minpos;                                     //返回找到的轻边T[minpos]的位置 
     }//end SelectLightEdge 
    
     //调整候选边集 
     void ModifyCandidateSet(AdjMatrix G,MST T,int k,int v){ 
     int i,d; 
     for(i=k;i<n-1;i++){                                //遍历当前候选轻边集T[k..n-2] 
      d = G[v][T[i].tovex];                          //d是新紫边(v,T[i].tovex)的长度 
      if(d<T[i].length){//新紫边长度小于蓝点T[i].tovex原来关联的最短紫边的长度 
       T[i].length = d; 
       T[i].fromvex= v;                           //新紫边取代原最短紫边 
      }//endif 
     }//end for 
     }//ModifyCandidateSet 
    
     //求图G的以r为根的MST,r为开始的结点 
     void PrimMST(AdjMatrix G,MST T,int r){ 
     int k,m,v; 
     TreeEdgeNode e; 
    
     InitCandidateSet(G,T,r);                           //设置初始的轻边候选集T[0..n-2] 
        for(k=0;k<n-1;k++){                                //依次求MST的第k条树边 
            m = SelectLightEdge(T,k);                      //在当前候选轻边集T[k..n-2]中选取轻边T[m] 
            //轻边T[m]和紫边T[k]交换，即把轻边扩充到树中 
      e   = T[m]; 
      T[m]= T[k]; 
      T[k]= e;                                                   
            v   = T[k].tovex;                              //交换后红色树边集为T[0..k]候选边集为T[k+1..n-2] 
            ModifyCandidateSet(G,T,k+1,v);                 //根据新红点v调整候选轻边集T[k+1...n-2]扩充 
        }//endfor 
     }//PrimMST 
     void PrintMST(MST T){ 
      int i; 
      for(i=0;i<n-1;i++){ 
      printf("(%d,%d)=%d\n",T[i].fromvex,T[i].tovex,T[i].length); 
      } 
     } 
     //测试主函数 
     void main(){ 
     int u; 
     char j='y'; 
     printf("本程序将演示构造图的最小代价生成树。\n"); 
        printf("首先输入图的顶点数和弧数.\n格式：顶点数，弧数；例如:4,4\n"); 
        printf("接着输入各条弧(弧尾,弧头)和弧的权值。\n"); 
        printf("格式:弧尾，弧头，权值；例如\n1,2,1\n1,3,2\n2,4,3\n3,4,4\n"); 
        printf("程序将会构造该图的最小代价生成树。\n"); 
     printf("并显示该最小生成树。\n1,2\n1,3\n2,4\n"); 
    
     while(j!='N'&&j!='n') 
        { 
        printf("请输入图的顶点和弧数:"); 
           DefaultCreateGraph(G);                           //CreateGraph(G);//生成邻接矩阵结构的图 
           printf("从哪一顶点开始:"); 
           scanf("%d",&u);                                  //输入普里姆算法中的起始顶点 
           PrimMST(G,T,u);                                  //普里姆算法求最小生成树 
        PrintMST(T);                                     //打印最小生成树 
           printf("最小代价生成树构造完毕，继续进行吗?(Y/N)"); 
           scanf("%c",&j); 
        } 
     }

#  7.11-7.13拓扑排序算法 #

*  ### 7.11拓扑排序算法 ###
 *  ### 7.12求入度算法 ###
 *  ### 7.13修改后的拓扑排序算法 ###

#include "stdio.h"
    #include "stdlib.h"
    #include "malloc.h"
    #define Null 0
    #define MAX 20
    
    typedef struct ArcNode
    {
    int adjvex;
    int weight;
    struct ArcNode *nextarc;
    }ArcNode,*AdjList;
    
    typedef struct Graph
    {
    AdjList elem[MAX+1];
    int vexnum;
    int arcnum;
    int GraphKind;
    }Graph;
    
    
    typedef struct Stack
    {
    int s[MAX];
    int top;
    }Stack;
    
    void initStack(Stack *s)
    {
    (*s).top=0;
    }
    
    int Push(Stack *s, int e)
    {
    if((*s).top>=MAX) return 0;
    else (*s).s[(*s).top++]=e;
    }
    
    int Pop(Stack *s, int *e)
    {
    if((*s).top<=0) return 0;
    else *e=(*s).s[--(*s).top];
    }
    
    int StackEmpty(Stack s)
    {
    if(s.top==0)return 1;
    else return 0;
    }
    
    
    void create(Graph *G)
    {
    int i, start, end; AdjList p;
    for(i=0;i<=MAX;i++)
    (*G).elem[i]=Null;
    for(i=1;i<=(*G).arcnum;i++)
    {
    scanf("%d,%d",&start,&end);
    p=(AdjList)malloc(sizeof(ArcNode));
    p->adjvex=end;
    p->nextarc=(*G).elem[start];
    (*G).elem[start]=p;
    if((*G).GraphKind==0)
    {
    p=(AdjList)malloc(sizeof(ArcNode));
    p->adjvex=start;
    p->nextarc=(*G).elem[end];
    (*G).elem[end]=p;
    }
    }
    }
    
    
    int TopoSort(Graph G)
    {
    int i, count, indegree[MAX+1];
    AdjList p; Stack S;
    for(i=1;i<=G.vexnum;i++)
    indegree[i]=0;
    initStack(&S);
    for(i=1;i<=G.vexnum;i++)
    for(p=G.elem[i];p;p=p->nextarc)
    ++indegree[p->adjvex];
    for(i=1;i<=G.vexnum;i++)
    if(!indegree[i]) Push(&S,i);
    count=0;
    while(!StackEmpty(S))
    {
    Pop(&S,&i);
    printf("v%d ",i);++count;
    for(p=G.elem[i];p;p=p->nextarc)
    if(!(--indegree[p->adjvex])) Push(&S,p->adjvex);
    }
    if(!count) return 1;
    }
    
    
    main()
    {
    Graph G;
    printf("Please input the number of vex, arc and GraphKind:");
    scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&G.GraphKind);
    create(&G);
    printf("The outcome of TopoSort is:\n");
    TopoSort(G);
    }

# 7.14关键路径算法 #

#include<stdio.h> 
    #include<stdlib.h> 
    #include<iomanip.h> 
    #include <process.h> 
    
    //#define PROJECTNUMBER 9//10 
    
    //#define PLANNUMBER 11//13 
    int SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime); 
    void CreateGraphic(Graphicmap,projectnumber,activenumber); 
    typedef struct node 
    { 
        int adjvex; 
        int dut; 
        struct node *next; 
    }edgenode; 
    
    typedef struct 
    { 
        int projectname; 
        int id; 
        edgenode *link; 
    }vexnode; 
    
    //vexnode Graphicmap[PROJECTNUMBER]; 
    
    void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber) 
    { 
        int begin,end,duttem; 
    	int i,k;
        edgenode *p; 
        for(i=0;i<projectnumber;i++) 
        { 
        Graphicmap[i].projectname=i; 
           Graphicmap[i].id =0; 
          Graphicmap[i].link =NULL; 
        }   
        printf("某项目的开始到结束在图中的节点输入<vi,vj,dut>\n"); 
        printf("如：3,4,9 回车表示第三节点到第四节点之间的活动用了9个单位时间\n"); 
        for(k=0;k<activenumber;k++) 
        { 
           scanf("%d,%d,%d",&begin,&end,&duttem); 
           p=(edgenode*)malloc(sizeof(edgenode)); 
           p->adjvex =end-1; 
           p->dut =duttem; 
           Graphicmap[end-1].id ++; 
           p->next =Graphicmap[begin-1].link ; 
           Graphicmap[begin-1].link =p; 
        } 
    } 
    
    int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int totaltime)
    { 
        int i,j,k,m=0; 
        int front=-1,rear=-1; 
        int* topologystack=(int*)malloc(projectnumber*sizeof(int));//用来保存拓扑排列 
        int* vl=(int*)malloc(projectnumber*sizeof(int));//用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间 
    	int* ve=(int*)malloc(projectnumber*sizeof(int));//用来表示Vj最早发生时间 
        int* l=(int*)malloc(activenumber*sizeof(int));//用来表示活动Ai最迟完成开始时间 
        int* e=(int*)malloc(activenumber*sizeof(int));//表示活动最早开始时间 
        edgenode *p; 
        totaltime=0; 
        for(i=0;i<projectnumber;i++) ve[i]=0; 
        for(i=0;i<projectnumber;i++) 
        { 
           if(Graphicmap[i].id==0) 
           { 
               topologystack[++rear]=i; 
             m++; 
           } 
        } 
        while(front!=rear) 
        { 
           front++; 
           j=topologystack[front]; 
           m++; 
           p=Graphicmap[j].link ; 
           while(p) 
           { 
              k=p->adjvex ; 
               Graphicmap[k].id --; 
               if(ve[j]+p->dut >ve[k]) 
                  ve[k]=ve[j]+p->dut ; 
               if(Graphicmap[k].id ==0) 
                 topologystack[++rear]=k; 
              p=p->next ; 
           } 
        } 
        if(m<projectnumber) 
        { 
           printf("\n本程序所建立的图有回路不可计算出关键路径\n"); 
           printf("将退出本程序\n"); 
           return 0; 
        } 
        totaltime=ve[projectnumber-1]; 
        for(i=0;i<projectnumber;i++) 
           vl[i]=totaltime; 
        for(i=projectnumber-2;i>=0;i--) 
        { 
           j=topologystack[i]; 
           p=Graphicmap[j].link ; 
           while(p) 
           { 
               k=p->adjvex ; 
               if((vl[k]-p->dut )<vl[j]) 
                  vl[j]=vl[k]-p->dut ; 
               p=p->next ; 
           } 
        } 
        i=0; 
        printf("| 起点 | 终点 |  最早开始时间  |  最迟完成时间  | 差值 |  备注  |\n"); 
        for(j=0;j<projectnumber;j++) 
        { 
           p=Graphicmap[j].link; 
           while(p) 
          { 
               k=p->adjvex ; 
               e[++i]=ve[j]; 
               l[i]=vl[k]-p->dut; 
               printf("| %4d | %4d |    %4d    |    %4d    | %4d |",Graphicmap[j].projectname +1,Graphicmap[k].projectname +1,e[i],l[i],l[i]-e[i]); 
               if(l[i]==e[i]) 
                  printf(" 关键活动 |"); 
               printf("\n"); 
               p=p->next ; 
           } 
        } 
        return 1; 
    } 
    
    void seekkeyroot() 
    { 
        int projectnumber,activenumber,totaltime=0; 
    	vexnode* Graphicmap;
        system("cls"); 
        printf("请输入这个工程的化成图形的节点数:"); 
        scanf("%d",&projectnumber); 
      printf("请输入这个工程的活动个数:"); 
      scanf("%d",&activenumber); 
      Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode)); 
      CreateGraphic(Graphicmap,projectnumber,activenumber); 
      SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime); 
      printf("整个工程所用的最短时间为：%d个单位时间\n",totaltime); 
      system("pause"); 
    } 
    
    int main() 
    { 
    	char ch; 
    	int i;
        for(;;) 
        { 
    		do 
    		{ 
    			system("cls"); 
    			printf("|             欢迎进入求关键路径算法程序              |"); 
    			for(i=0;i<80;i++)printf("*"); 
    			printf("%s","(S)tart开始输入工程的节点数据并求出关键路径\n"); 
    			printf("%s","(E)xit退出\n"); 
    			printf("%s","请输入选择:"); 
    			scanf("%c",&ch); 
    			ch=toupper(ch); 
    		}while(ch!='S'&&ch!='E'); 
    		switch(ch) 
    		{ 
    		case'S': 
    			seekkeyroot(); 
    			break; 
    		case'E': 
    			return 1; 
    		} 
        } 
    }

# 7.15图的最短路径算法 #

#include <stdio.h>
    #include <conio.h>
    #include <stdlib.h>
    
    #define X 10000
    #define VertexNum  7  //实际上共有六个顶点（1---6）
    #define EdgeNum  9
    
    int Graph[VertexNum][VertexNum] =
    //0  1  2  3  4  5  6
    { X, X, X, X, X, X, X,  //0
      X, X, 6, 3, X, X, X,  //1
      X, X, X, X, 5, X, X,  //2
      X, X, 2, X, 3, 4, X,  //3
      X, X, X, X, X, X, 3,  //4
      X, X, X, X, 2, X, 5,  //5
      X, X, X, X, X, X, X   //6
    };
    
    int Visited[VertexNum];
    int path[VertexNum];
    int Distance[VertexNum];
    
    void Dijkstra(int Begin)
    {
      int MinEdge, Vertex, i,j, Edges;
      Edges = 1;
      Visited[Begin] = 1;
      for (i = 1; i<VertexNum; i++) Distance[i] = Graph[Begin][i];
    
      Distance[Begin] = 0;
      printf("     1  2  3  4  5  6\\n");
      printf("-----------------------------------\\n");
      printf("s:%d", Edges);
      for( i=1; i<VertexNum; i++)
      if (Distance[i] == X) printf("  *"); else printf("%3d",Distance[i]);
      printf("\\n");
      while( Edges<VertexNum-1)
      {
        Edges++; MinEdge = X;
        for(j=1; j<VertexNum; j++)
        if (Visited[j]==0 && MinEdge > Distance[j] )
        {
     Vertex = j; MinEdge = Distance[j];
        }
        Visited[Vertex] = 1;
        printf("s:%d",Edges);
        for(j=1; j<VertexNum; j++)
        {
          if (Visited[j] == 0 && Distance[Vertex] + Graph[Vertex][j] <Distance[j])
          {   Distance[j] = Distance[Vertex] + Graph[Vertex][j];
       path[j] = Vertex;
          }
          //printf("%6d",Distance[j]);
           if (Distance[j] == X) printf("  *"); else printf("%3d",Distance[j]);
        }
        printf("\\n");
      }
    }
    
    void main()
    {
      
      int i;
      int k;
     // clrscr();
      for(i=0; i<VertexNum; i++) { Visited[i] = 0;  path[i] = 1;}
      Dijkstra(1);
      printf("\\n\\nAll Path-------------------------\\n");
    
    
      for(i=2; i<VertexNum; i++) //printf("%5d",Visited[i]);
      {
         printf("[%d] ",Distance[i]);
         k = i;
         do
         {
           printf("%d<--",k);
           k  = path[k];
         } while (k!=1);
         printf("1 \\n");
      }
    }

# 7.16弗洛伊德算法 #

#include "stdio.h"
    #include "iostream.h"
    #include "stdlib.h"
    
    #include <iostream>
    
    #define INFINITY 32767//int型的最大值为∞
    #define MAX_VEX_NUM 30//最大顶点个数
    typedef struct{  
    	char vexs[MAX_VEX_NUM+1];//顶点信息
    	int arcs[MAX_VEX_NUM+1][MAX_VEX_NUM+1];//邻接矩阵存放权值
        int vexnum,arcnum;//顶点数,弧(边)数
    }AdjGraph;
    
    int CenterVex(AdjGraph *g);//带权图的邻接矩阵建立
    AdjGraph *CreateAdjGrahp();//Floyd算法
    void main()
    {
    	int k;
    	AdjGraph *g;
    	g=CreateAdjGrahp();
    	k=CenterVex(g);
        cout<<"中心顶点为:"<<g->vexs[k]<<endl;
    }
    
    邻接矩阵的建立
    AdjGraph *CreateAdjGrahp()
    {    
        AdjGraph *g;
    	g=new AdjGraph;
    	int i,j,k,x;
    	cout<<"Input vexnum and arcnum(格式如:顶点数 边数<Enter>):"<<endl;
    	scanf("%d%d",&g->vexnum,&g->arcnum);//读入顶点个数和边数
    	cout<<"输入顶点信息:(如:abcde<Enter>)"<<endl;
    	scanf("%c",&g->vexs[1]);
    	for(i=1;i<=g->vexnum;i++)
    		scanf("%c",&g->vexs[i]);//读入顶点信息
        for(i=1;i<=g->vexnum;i++)
    		for(j=1;j<=g->vexnum;j++)
    			g->arcs[i][j]=INFINITY;//初始化邻接矩阵	
    		cout<<"顶点<->序号"<<endl;
    		for(k=1;k<=g->vexnum;k++)
            {   
    			printf("%4c<->%d",g->vexs[k],k);	
    			cout<<endl;
    		}	
    		cout<<"输入每条边对应的两个顶点的序号及权值,格式为:"<<endl
    		    <<"i j x<Enter>"<<endl;
    		for(k=1;k<=g->arcnum;k++)
    		{
    			scanf("%d%d%d",&i,&j,&x);//输入边信息，建立邻接矩阵
    		    g->arcs[i][j]=x;
    		}
    		return g;
    }//CreateGraph
    /Floyd算法///
    int CenterVex(AdjGraph *g)
    {//在带权图G中求一个中心顶点，返回该顶点编号
    	int i,j,k;
    	int min,len, length[MAX_VEX_NUM+1][MAX_VEX_NUM+1];
    	for(i=1;i<=g->vexnum;i++){			
    		for(j=1;j<=g->vexnum;j++)
    			length[i][j]=g->arcs[i][j];		
    		length[i][i]=0;
    	}
    	for(k=1;i<=g->vexnum;k++)
    		for(i=1;i<=g->vexnum;i++)
    			for(j=0;j<g->vexnum;j++)			
    				if(length[i][k]+length[k][j]<length[i][j])				
    					length[i][j]=length[i][k]+length[k][j];				
    				min=INFINITY; k=0;		
    				for(i=1;i<=g->vexnum;i++){//选择最大短路径长度之和最小的顶点Vk			
    					len=0;		
    					for(j=0;j<g->vexnum;j++)//求Vi到其余顶点最短路径长度之和
    						len=len+length[i][j];	
    					if(len<min){		
    						k=i;		
    						min=len;	
    					}
    				}						
    				return(k);
    }
    
    /* * * * * * * * * * * 运行结果 * * * * * * * * * * * * * *
    Input vexnum and arcnum(格式如：顶点数 边数<Enter>):
    5 7<Enter>
    输入顶点信息:(如:abcde<Enter>)
    abcde<Enter>
    顶点<->序号
       a<->1
       b<->2
       c<->3
       d<->4
       e<->5
    输入每条边对应的两个顶点的序号及权值,格式为:
    i j k<Enter>
    1 2 1
    2 3 2
    3 5 4
    5 4 5
    4 2 1
    3 4 2
    4 3 3
    中心顶点为:d
    Press any key to continue
    */