#include<stdio.h>
#include <malloc.h>
#include<conio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define  OK 1
#define  ERROR 0
#define  INFEASIBLE -1
#define  OVERFLOW -2
 
typedef int Qelemtype;
typedef int Status;
typedef struct Qnode
{
  Qelemtype data;
  struct Qnode *next;
}Qnode, *Queueptr;
typedef struct
{
 Queueptr front;
 Queueptr rear;
}Queue;
#define maxvernum 30  
int visited[maxvernum];
typedef char vertextype;
typedef struct arcnode  
{  
       int adjvex;                                         //该弧指向的顶点位置  
       struct arcnode * nextarc;          //指向下一个表结点  
       int info;                                      //权值信息  
}arcnode;                                              //边结点类型  
   
typedef struct vnode  
{  
       vertextype data;  
       int indegree;  
       arcnode * firstarc;
}vnode, adjlist[maxvernum];  

typedef struct  
{  
       adjlist vertices;            //邻接表  
       int vernum, arcnum;             //顶点数和弧数  
}algraph;  
   
//查找符合的数据在数组中的下标  CreateALGraph
int locatever(algraph g, char u)  
{  
       int i;  
       for(i = 0; i < g.vernum; i++)  
       {  
              if(u == g.vertices[i].data)  
                     return i;  
       }  
       if(i == g.vernum)  
       {  
              printf("error u!\n");  
              exit(1);  
       }  
       return 0;  
}  
   
//常见图的邻接矩阵  
void createalgraph(algraph &g)  
{  
       int i, j, k, w;  
       char v1, v2;  
       arcnode * p;  
       printf("输入顶点数和弧数: ");  
       scanf("%d %d", &g.vernum, &g.arcnum);  
       printf("请输入顶点!\n");  
       for(i = 0; i < g.vernum; i++)  
       {  
              printf("请输入第 %d 个顶点: \n", i);  
              fflush(stdin);  
              scanf("%c", &g.vertices[i].data);  
              g.vertices[i].firstarc = NULL;  
              g.vertices[i].indegree = 0;  
       }  
   
       for(k = 0; k < g.arcnum; k++)  
       {  
              printf("请输入弧的顶点和相应权值(v1, v2, w): \n");  
              fflush(stdin);  //清空输入缓冲区
              scanf("%c %c %d", &v1, &v2, &w);  
              i = locatever(g, v1);  
              j = locatever(g, v2);  
              p = (arcnode *)malloc(sizeof(arcnode));  
              p->adjvex = j;  
              p->info = w;  
              p->nextarc = g.vertices[i].firstarc;  
              g.vertices[i].firstarc = p;  
              g.vertices[j].indegree++;                   //vi->vj, vj入度加1  
       }  
       return;  
}  

int firstadjvex(algraph g,char v)
{
 arcnode * p;
 int v1;
 v1 = locatever(g,v);//v1为顶点v在图G中的序号
 p = g.vertices[v1].firstarc;
 if (p)
 {
  return p->adjvex;//p->data.adjvex
 }
 else
 {
  return -1;
 }
}
int nextadjvex(algraph g,char v,char w)
{
    arcnode*p,*s;
    for(p=g.vertices[v].firstarc;p!=NULL;p=p->nextarc)
    {
        if(((p->adjvex)==w)&&(p->nextarc))
        {
            s=p->nextarc;
            return s->adjvex;
        }
    }
    return 0;
}



 
void dfs(algraph g,char v)      //深度优先遍历
{
    char w;
    printf("%d\n ",v);          //访问结点v
    visited[v]=true;
//    visitfunc(v);
    for(w=firstadjvex(g,v);w>=0;w=nextadjvex(g,v,w))       //访问与v相邻的未被访问过的结点
    {
        if(!visited[w])      
            dfs(g,w);
        
    }
}

int InitQueue(Queue &Q)
{
  Q.front = Q.rear = (Queueptr) malloc (sizeof(Qnode));
  if(!Q.front)  return (OVERFLOW);
  Q.front ->next = NULL;
  return OK;
}//构造一个空队列
Status EnQueue(Queue &Q,Qelemtype e)
{
   Queueptr p;
   p = (Queueptr) malloc (sizeof(Qnode));
   if(!p) return(OVERFLOW);
   p->data = e;
   p->next = NULL;
   Q.rear->next = p;
   Q.rear = p;
   return OK;
}//插入新元素
Status DeQueue(Queue &Q,Qelemtype &e)
{
 Queueptr p;
 if(Q.front == Q.rear)  return ERROR;
 p = Q.front->next;
    e = p->data;
 Q.front->next = p->next;
 if(Q.rear == p) Q.rear = Q.front;
 free(p);
 return OK;
}//删除队头元素
Status Queueempty(Queue Q)
{
    if(Q.front == Q.rear)  return OK;
 else  return ERROR;
}//判断队列是否为空
void bfs(algraph g,int v)   //广度优先搜索
{
    Queue Q;
    int u;
    char w;
    for(v=0;v<g.vernum;++v)
        visited[v]=false;
    InitQueue(Q);
    for(v=0;v<g.vernum;++v)
        if(!visited[v])
        {
            visited[v]=true;
            printf("%d\n",v);
            EnQueue(Q,v);
            while(!Queueempty(Q))
            {
      
                DeQueue(Q,u);      
     
                for(w=firstadjvex(g,u);w>=0;w=nextadjvex(g,u,w))   
                    if(!visited[w])
                    {
                        visited[w]=true;
                        printf("%d\n ",w);
                        EnQueue(Q,w);
                    }//if
            }//while
        }//if
}





//求图的关键路径函数  
void criticalpath(algraph g)  
{  
       int i, k, e, l;  
       int * ve, * vl;  
       arcnode * p;  
   

       //以下是求时间最早发生时间  

   
       ve = new int [g.vernum];  
       vl = new int [g.vernum];  
   
       for(i = 0; i < g.vernum; i++)              //前推  
              ve[i] = 0;  
   
       for(i = 0; i < g.vernum; i++)  
       {  
              arcnode * p = g.vertices[i].firstarc;  
              while(p != NULL)  
              {  
                     k = p->adjvex;  
                     if(ve[i] + p->info > ve[k])  
                            ve[k] = ve[i]+p->info;  
                     p = p->nextarc;  
              }  
       }  
 
       //以下是求最迟发生时间  

       for(i = 0; i < g.vernum; i++)  
              vl[i] = ve[g.vernum-1];  
       for(i = g.vernum-2; i >= 0; i--)                 //后推  
       {  
              p = g.vertices[i].firstarc;  
              while(p != NULL)  
              {  
                     k = p->adjvex;  
                     if(vl[k] - p->info < vl[i])  
                            vl[i] = vl[k] - p->info;  
                     p = p->nextarc;  
              }  
       }  
       for(i = 0; i < g.vernum; i++)  
       {  
              p = g.vertices[i].firstarc;  
              while(p != NULL)  
              {  
                     k = p->adjvex;  
                     e = ve[i];              //最早开始时间为时间vi的最早发生时间  
                     l = vl[k] - p->info;             //最迟开始时间  
                     char tag = (e == l) ? '*' : ' '; //关键活动  
                     printf("(%c, %c), e = %2d, l = %2d, %c\n", g.vertices[i].data, g.vertices[k].data, e, l, tag);  
                     p = p->nextarc;  
              }  
       }  
       delete [] ve;  
       delete [] vl;  
}  


void main()

{int i;
algraph g;
createalgraph(g); /*创建图*/
printf("以下是查找图的关键路径的程序。\n");
//criticalpath(g);

for(i=1;i<maxvernum;i++)

visited[i]=0; /*访问数组初始化*/

dfs(g,0); /*调用DFS*/

getch(); /*等待输入*/

for(i=1;i<maxvernum;i++)

visited[i]=0;

bfs(g,1); /*调用BFS*/
printf("以下是查找图的关键路径的程序。\n");
criticalpath(g);
}