graphadjlink.cpp

图的邻接表存储实现

typedef int status;
typedef int ElemType;
typedef int ElementType;

#include"GraphAdjLink.h"
#include"CircleQueue.h"
#include"Stack.h"
#include<stdio.h>
#include<stdlib.h>
int visit[MAX];  //顶点标志数组,全局变量
NODE *ptr[MAX];   //顶点链表指针数组
NODE adjlist[MAX];  
//图的创建
int CreateGraph(NODE *adjlist)
 { 
	 NODE *p;
     int num, i, v1, v2;
     scanf("%d\n", &num);  //读入结点数
     for(i=0; i<num; i++) //初始化空关系图
	  { 
		  adjlist[i].link=NULL; adjlist[i].vertex=i; 
	  }
	 for(; ;)
     {
		 scanf("%d to %d\n", &v1, &v2);  //读入一条边
		 if (v1<0 || v2<0) break; // 数据输入的终止条件
		 p=(NODE *)malloc(sizeof(NODE));
		 p->vertex=v2;
		 p->link=adjlist[v1].link; adjlist[v1].link=p; //插入在链表首部
		 p=(NODE *)malloc(sizeof(NODE));
		 p->vertex=v1;
		 p->link=adjlist[v2].link; 
		 adjlist[v2].link=p;
	 } 
	return(num); // 返回图的结点数
}

static void Dfs( int v)
  { int w;
      printf( "%d, ", v); visit[v]=1;    // 访问此结点
      while (ptr[v]!=NULL)
       { w= ptr[v]->vertex;   //取结点的邻接顶点w
           if ( visit[w]==0) Dfs(w);
           ptr[v]=ptr[v]->link;      // 记住顶点v 的邻接顶点位置，该邻接点在w之后
         }                                             
    }

void DepthFirst( NODE adjlist[], int num)
  { int i;
     for (i=0; i<num;i++)
      { ptr[i]=adjlist[i].link; //记住每个顶点链表的第一个结点的地址
         visit[i]=0;                   //给每个结点一个未访问标记
       }
      for (i=0; i<num;i++)
        if (visit[i] ==0) Dfs(i);    //调用以顶点vi 为出发点的深度优先遍历图G 的算法
                                                   
     } 



static void Bft(int v) //从v出发，广度优先遍历图G。
 { int w; NODE *p;
   SqQueue q;
   InitQueue(q);
   visit[v]=1;
   printf("%d,",v); // EnQueue(q,v)为入队列函数
   EnQueue(q,v); 
   while(DeQueue(q,v)==1); // DeQueue（q）为出队列函数
    { p=adjlist[v].link;     //p指向出队列顶点v的第一个邻接点
      while(p!=NULL)
        { 
		  w = p->vertex; //遍历v所指的整个链表
          if(visit[w]==0)  //如果w 未被访问过
           { printf("%d,",w);  // 访问 w
             visit[w]=1; 
			 EnQueue(q,w); //访问后，w 入队
           } 
		  p=p->link;
        }
    }
 }



void BreadFirst(int num)
 { int i;
   for (i=0;i<num;i++) visit[i]=0;//给所有顶点一个未被访问标记
   for (i=0;i<num;i++)
     if(visit[i]==0) Bft(i); //  调用以顶点vi 为出发点的是广度优先遍历图G的算法
                                     
  }


int TopologicalSort(NODE *adjlist, int num) 
//有向图G采用邻接表存储结构。
//若G无回路，则输出G的顶点的一个拓扑序列并返回1，否则0。
{  
	  SqStack s;  //存放入度为0的顶点的栈 
      int i, out, k; 
	  NODE *p;
      int num1=0;
      for(i=0; i<num; i++)
          if (adjlist[i].vertex==0)    //入度为0顶点的编号进栈
				Push(s,i);    
	while(!IsSqStackEmpty(s))
	   { 
		Pop(s,out); 
		printf( "%d,",out);
		num1++;
   		p=adjlist[out].link;
		while ( p!=NULL)
			{ k=p->vertex;
			  adjlist[k].vertex--; //顶点入度减1，
			  if (adjlist[k].vertex ==0)  //若入度减为0，则进栈
			  Push(s,k);
			  p=p->link; 
       		}
	  }
  if (num1<num) //根据输出节点数来判断	
	 return( 0);   //该有向图是否有回路
  else
	 return (1);
}