op-graph.cpp

图的创建和遍历

/* 图操作演示
  1.按照指定格式从正文文件中读入信息，建无向图，结构为邻接表。
  2.形象地输出图的存储结构
  3.从任一指定顶点出发，进行深度优先遍历，输出生成森
    林的边集(字符对)及对应的顶点序列。
  4.从任一指定顶点出发，进行广度优先遍历，输出生成森
    林的边集(字符对)及对应的顶点序列。
  5.判断任意指定的两个顶点间是否有通路。
*/
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#define M 20                // 顶点数上限

typedef struct anode{   // 弧结点
  int adj;
  struct anode *next;
}anode,*link;
typedef struct {            // 顶点结点
  char c;
  link first;
}vnode;
typedef struct{             // 图的邻接表结构
  vnode vexs[M+1];     // 0单元保留给监视哨使用
  int vnum,anum;
}graph;
typedef struct{             // 循环队列类型
  int q[M],len,rear;
}queue;
int v[M+1],top;            // 访问标记数组
char s[M];                    // 记录遍历次序的数组
queue q;                       // 循环队列
graph g;

void initq(queue &q){  // 初始化队列
  q.len=q.rear=0;
}

emptyq(queue q){return !q.len;}// 判队空

void enq(queue &q,int e){        // 入队
  if(q.len==M) return;
  q.q[q.rear]=e; q.rear=(++q.rear)% M; q.len++;
}

outq(queue &q){                       // 出队
int e;
  if(!q.len) return -1;
  e=q.q[(q.rear+M-q.len--)%M]; return e;
}

locat(graph g,char c){               // 顶点定位，0表示无此点, 采用监视哨查找
  int i;
  g.vexs[0].c=c; i=g.vnum;
  while(g.vexs[i].c!=c) i--; return i;
}
void creatg(graph &g){  // 从文件读入信息建邻接表
  FILE *f;
  link p;
  int i,j,k;
  char c1,c2;
  if((f=fopen("graph1.txt","rt"))==NULL){
    printf("Can't open data file!\n"); return;
  }
  fscanf(f,"%d %d\n",&g.vnum,&g.anum);
  for(i=1;i<=g.vnum;i++) {fscanf(f,"%c",&g.vexs[i].c); g.vexs[i].first=NULL;}
  fscanf(f,"\n");
  for(k=0;k<g.anum;k++) {
    fscanf(f,"%c%c\n",&c1,&c2);
    i=locat(g,c1); j=locat(g,c2);
    if(!i*j){
      printf("Vex on edge is'nt in graph!\n"); return;
    }
    p=(link)malloc(sizeof(anode)); p->adj=j; p->next=g.vexs[i].first; g.vexs[i].first=p;
    p=(link)malloc(sizeof(anode)); p->adj=i; p->next=g.vexs[j].first; g.vexs[j].first=p; // 无向图
  }
}

void destroyg(graph &g){ // 销毁图(实际只释放了弧结点)
  link p;
  int i;
  for(i=1;i<=g.vnum;i++){
    p=g.vexs[i].first;
    while(g.vexs[i].first){
      p=g.vexs[i].first; g.vexs[i].first=p->next;
      free(p);
    }
  }
}

void prtg(graph g){         // 显示图结构
  link p;
  int i;
  for(i=1;i<=g.vnum;i++){
    printf("%2d %2c",i,g.vexs[i].c);
    p=g.vexs[i].first;
    while(p){printf(" ->%d",p->adj); p=p->next;}
    printf("^\n");
  }
}

void dfs(graph g,int i){          // 深度优先遍历，输出一棵生成树，保存顶点
link p;
  v[i]=1; s[top++]=g.vexs[i].c; p=g.vexs[i].first;
  while(p){
    if(!v[p->adj]){
      printf(" %c%c,",g.vexs[i].c,g.vexs[p->adj].c);
      dfs(g,p->adj);
    } p=p->next;
  }
}

void dfstravel(graph g){                     // 深度优先遍历，输出生成森林及顶点序列
int i,j;
  for(i=0;i<=g.vnum;i++) v[i]=0;        // 访问标志初始化
  for(i=1;i<=g.vnum;i++)
    if(!v[i]){
      top=0; printf("\nDFS Maked tree:");          // 输出一棵深度优先生成树及其顶点序列
      dfs(g,i); printf("  Dfs list:");
      for(j=0;j<top;j++) putch(s[j]);
    }
}

void bfstravel(graph g){                     // 广度优先遍历，输出生成森林及顶点序列
int i,j;
link p;
  for(i=0;i<=g.vnum;i++) v[i]=0;        // 访问标志初始化
  initq(q);
  for(i=1;i<=g.vnum;i++){
    if(!v[i]){
      v[i]=1; top=0; s[top++]=g.vexs[i].c;
      enq(q,i); printf("\nBFS Maked tree:");          // 输出一棵广度优先生成树及其顶点序列
      while(!emptyq(q)){
	j=outq(q); p=g.vexs[j].first;
	while(p){
	  if(!v[p->adj]){
	    enq(q,p->adj); v[p->adj]=1; s[top++]=g.vexs[p->adj].c;
	    printf(" %c%c,",g.vexs[j].c,g.vexs[p->adj].c);
	  }
	  p=p->next;
	}
      } printf("  Bfs list:");
      for(j=0;j<top;j++) putch(s[j]);
    }
  }
}

void dfs1(int i,int j){        // 利用深度优先遍历检查i,j是否连通，top==1表示已知连通
link p;
  v[i]=1;
  if(i==j) top=1;
  p=g.vexs[i].first;
  while(p&&!top){
    if(!v[p->adj]) dfs1(p->adj,j);
    p=p->next;
  }
}

connecte(graph g){
link p;
int i,j;
char c1,c2;
  printf("Please enter two letters,Check they are connecting or not:");
  c1=getche(); c2=getche();
  for(i=0;i<=g.vnum;i++) v[i]=0;        // 访问标志初始化
  i=locat(g,c1); j=locat(g,c2);             // 查出点号
  top=0;                                               // top==1表示已知连通
  if(i*j) dfs1(i,j);
  return top;
}

main(){
char ch=' ';
  clrscr();
  printf("   1.Create graph  2.Dfs travel  3.Bfs travel  4.Connecte  5.Destroy  0.Exit");
  window(1,2,80,25);
  while(ch!=48){
    gotoxy(36,3); printf("Chose:");
    ch=getch(); clrscr(); gotoxy(15,5);
    switch(ch){
      case '1': destroyg(g); creatg(g); break;
      case '2': dfstravel(g); break;
      case '3': bfstravel(g); break;
      case '4': if(connecte(g)) printf("\nThey are connecting!\n");
		else printf("\nThey are not connecting!\n"); break;
      case '5': destroyg(g); break;
      case '0': destroyg(g); window(1,1,80,25); return 0;
    }
    gotoxy(1,10); prtg(g);
  }  return 1;
}