[數據結構]第六次作業：圖的建立、遍歷、最小生成樹、最短路徑收藏
新一篇: [數據結構]第七次作業：二叉排序樹
/* 程序區分無向圖和右向圖的代碼可以繼續完善 */
/* ==============  Program Description  ============= */
/*               Freshare's 6th of dswork             */
/* ================================================== */

#include "stdlib.h"
#include "stdio.h"
#define INFINITY 32767   //無窮大
#define MAX 255
#define TRUE 1
#define FALSE 0
#define QUEUE_SIZE 255  //隊列長度
#define ElemType int    //隊列數據類型

int visited[MAX];
int P[MAX][MAX];
int D[MAX];
int flag;//0無向，1有向

typedef struct  //鄰接矩陣的類型定義
{ char vexs[MAX];
  int arcs[MAX][MAX];
  int vexnum, arcnum;
} MGraph;

typedef struct node //鄰接表的類型定義
{ int adjvex;
  struct ArcNode *next;
} ArcNode;
typedef struct
{ char data;
  ArcNode *firstarc;
} vexnode, AdjList[MAX];
typedef  struct{
  AdjList AdjList;
  int vexnum, arcnum;
}AlGraph;
AlGraph GA;


struct   //minispantree定義
{
  int   adjvex;
  int   lowcost;
} closedge[MAX];

typedef struct{
  ElemType data[MAX];
  int front,rear; 
  int flag;
} SqQueue;

//以下是隊列的相關操作,默認操作隊列是Q

SqQueue Q;

void IniQueue() //初始化
{
 Q.front=Q.rear=0;
 Q.flag=0;
}

int Empty()  //是否為空
{  if(Q.front==Q.rear && Q.flag==0) return(1);
   return(0);
}
int Full() //是否已滿
{  if(Q.front==Q.rear && Q.flag==1) return(1);
   return(0);
}


int EnQueue(ElemType e)
{ if(Full(Q)) return(0);
  else
  {
   Q.rear=(Q.rear+1)%MAX;
   Q.data[Q.rear]=e;
   Q.flag=1;
  }
  return(1);
} 

int DeQueue()
{ int e;
 if(Empty(Q)) return(0);  
else
{
 Q.front=(Q.front+1)%MAX;
 e=Q.data[Q.front];
 Q.flag=0;
}
return(e);
}


MGraph  CreateUDN(MGraph G)
{ int i,j,w,k,a,b;
  char ch1,ch2;
  printf("輸入頂點和邊數(用空格分隔):");
  scanf("%d %d",&G.vexnum, &G.arcnum);getchar();
  printf("輸入頂點所用符號:");
  for (i=0;i<G.vexnum;i++)
      G.vexs[i]=getchar();getchar();
  for (i=0;i<G.vexnum;i++)
    for (j=0;j<G.vexnum;j++)
  G.arcs[i][j]=INFINITY;
  printf("輸入連接每條邊的頂點和權數:\n(如:ab2代表a到b的權是2)\n");
   for (k=0;k<G.arcnum;k++)
   { 
     scanf("%c%c%d",&ch1,&ch2,&w);getchar();
     for (i=0;i<G.vexnum;i++)
   {if (G.vexs[i]==ch1) break;}
  for (j=0;j<G.vexnum;j++)
   {if (G.vexs[j]==ch2) break;}
     G.arcs[i][j]=w;
  if (flag==0) G.arcs[j][i]=w; //無向的
   }
  return(G);
}

AlGraph CreateAdjlist(AlGraph G,MGraph GM)
{ int i,j,k,a[MAX],b[MAX],i1=0,j1=0;
  ArcNode *s;
  G.vexnum=GM.vexnum;
  G.arcnum=GM.arcnum;
  for (i=0;i<G.vexnum;i++)
  { G.AdjList[i].data=GM.vexs[i]; 
    G.AdjList[i].firstarc=NULL;}
   for (i=GM.vexnum-1;i>=0;i--)
   if (flag==0)
   {
      for (j=(GM.vexnum-1);j>=i;j--)
    if(GM.arcs[i][j]!=INFINITY) 
   {
     s=malloc(sizeof(ArcNode));
     s->adjvex=j;
     s->next=G.AdjList[i].firstarc ;
     G.AdjList[i].firstarc=s;
  s=malloc(sizeof(ArcNode)); 
     s->adjvex=i;
     s->next=G.AdjList[j].firstarc ;
     G.AdjList[j].firstarc=s;
   } 
   }
   else
   {
    for (j=(GM.vexnum-1);j>=0;j--)
    if(GM.arcs[i][j]!=INFINITY) 
   {
     s=malloc(sizeof(ArcNode));
     s->adjvex=j;
     s->next=G.AdjList[i].firstarc ;
     G.AdjList[i].firstarc=s;
   } 
   }
    return(G);
}

void DFS (AlGraph G,int v) /*圖用鄰接表表示*/
{  
  ArcNode *p;
  int w;
 visited[v]=1;
  printf("%c", G.AdjList[v].data );
   p=G.AdjList[v].firstarc;
while (p!=NULL)
  {  w=p->adjvex;
      if (visited[w]==0) DFS(G,w);
         p=p->next;
    }
}


void BFS (AlGraph G)     /*用鄰接表表示*/
{ int v,u,w;
  ArcNode *p;
  for ( v=0; v<G.vexnum; v++)  visited[v]=FALSE;
  IniQueue();
  for ( v=0; v<G.vexnum; v++)
    if ( !visited[v]) 
 {
    visited[v]=TRUE; 
    printf("%c", G.AdjList[v].data);
    EnQueue(v);
  while (!Empty())
    {
  u=DeQueue();
     p=G.AdjList[u].firstarc;
    while (p!=NULL)
    {  w=p->adjvex;
      if (!visited[w])
     { visited[w]=TRUE; 
        printf("%c", G.AdjList[w].data );
       EnQueue(w);    }  //if
        p=p->next;
      }  //while
   }  //while
}  // if
}

int minimum(int g)
{
 int i=0,min;
 while(closedge[i].lowcost==0) i++;
 min=i;
 for(i=1;i<g;i++)
  if ((closedge[i].lowcost!=0)&&(closedge[i].lowcost<closedge[min].lowcost))
   min=i;
 return min;
}

void MiniSpanTree_PRIM(MGraph G, int u)
{
  int i,j,k;
  k = u;
  for (j=0; j<G.vexnum; ++j ) 
  {
    if (j!=k) 
     { closedge[j].adjvex=u;
    closedge[j].lowcost=G.arcs[k][j]; 
  }
  }
  closedge[k].lowcost = 0; 
  for (i=1; i<G.vexnum; ++i)
  {
    k = minimum(G.vexnum);
    printf("%c %c\n",G.vexs[closedge[k].adjvex],G.vexs[k]); 
    closedge[k].lowcost = 0;
    for (j=0; j<G.vexnum; ++j)
      if (G.arcs[k][j]<closedge[j].lowcost)
   { 
        closedge[j].adjvex=k;
        closedge[j].lowcost=G.arcs[k][j];
      }
  }
}

void ShortestPath_DIJ(MGraph G,int v0)
{ int i=0,j,v,w,min;
  int final[MAX];
  for (v=0; v<G.vexnum; ++v) 
  {
    final[v] = FALSE;  
    D[v] = G.arcs[v0][v];
    for (w=0; w<G.vexnum; ++w)  P[v][w] = FALSE;  // 設空路徑
    if (D[v] < INFINITY) { P[v][v0] = TRUE;  P[v][v] = TRUE; }
  }
  D[v0] = 0;  final[v0] = TRUE;  
  for (i=1; i<G.vexnum; ++i) { 
    min = INFINITY; 
    for (w=0; w<G.vexnum; ++w)
      if (!final[w]) 
        if (D[w]<min) { v = w;  min = D[w]; }
    final[v] = TRUE;
    for (w=0; w<G.vexnum; ++w)
      if (!final[w] && (min+G.arcs[v][w]<D[w])) 
   { 
        D[w] = min + G.arcs[v][w];
        for(j=0;j<G.vexnum;j++) P[w][j] = P[v][j]; 
        P[w][w] = TRUE;
      }//if
  }//for
} // ShortestPath_DIJ


void main()
{
 MGraph G;
 int i=0,j=0,k,v;
 ArcNode *pointer;
 printf("清選擇， 0 - 無向圖  ， 1 - 有向圖:");
 scanf("%d",&flag);getchar();
 G=CreateUDN(G);// 鄰接矩陣
 GA=CreateAdjlist(GA,G);//鄰接表，根據G自動生成
 printf("鄰接表:\n");
 for (k=0;k<GA.vexnum;k++)
 {
  printf("%c",GA.AdjList[k].data);
    pointer=GA.AdjList[k].firstarc;
    while (pointer!=NULL)
   {
    printf(" -> %d",pointer->adjvex);
    pointer=pointer->next;
   }
   printf("\n");
 }
 printf("鄰接矩陣:\n");
 for (i=0;i<G.vexnum;i++)
  for (j=0;j<G.vexnum;j++)
  {printf("%d\t",G.arcs[i][j]);
  if (j==(G.vexnum-1)) printf("\n");}
 printf("\n輸入遍歷的起點:");
 scanf("%d",&v);
 printf("DFS遍歷:\n");
 DFS(GA,v);
    printf("\nBFS遍歷:\n");
 BFS(GA);
 printf("\n最小生成樹如下:\n");
 MiniSpanTree_PRIM(G,0);
 printf("\n輸入一個頂點的編號，求它到其他頂點的最短路徑:");
 scanf("%d",&v);
 ShortestPath_DIJ(G,0);
 for (i=0;i<G.vexnum;i++)
 {
  if (D[i]!=0||D[i]!=INFINITY) printf("到%c的最短路徑是:  ",G.vexs[i]);
  for (j=0;j<G.vexnum;j++)
   if (P[i][j]!=0) printf("-->%c",G.vexs[j]);
 printf("\n");
 }
}