zb2.cpp

有向图的强连通的分量的实现

/*******************************************
计算机4班  张冰  01204106
********************************************

有向图的强连通的分量的实现

******************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_VERTEX_NUM 20
#define  MAX_NAME   10
#define  OK  1
#define  TRUE 1
#define ERROR 0
#define FALSE 0
typedef  int status;
typedef char VertexType[MAX_NAME];
 
struct ArcNode
{
    int adjvex; // 该弧所指向的顶点的位置
    ArcNode *nextarc; // 指向下一条弧的指针
}; // 表结点
typedef struct
{
    VertexType data; // 顶点信息
    ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM]; // 头结点
struct ALGraph
{
	AdjList vertices;
    int vexnum,arcnum; // 图的当前顶点数和弧数
};


void main()
{
	int LocateVex(ALGraph G,VertexType u);
	status  CreateGraph(ALGraph &G,ALGraph&Gr);
	VertexType& GetVex(ALGraph G,int v);
	int FirstAdjVex(ALGraph G,VertexType v);
	int NextAdjVex(ALGraph G,VertexType v,VertexType w);
	//void (*VisitFunc)(char* v); 
    void print(char *v);void DFS(ALGraph G,int v);
	void DFSTraverseGr(ALGraph G,void(*Visit)(char*));
	void DFSGr(ALGraph &G,int v);
	void DFSTraverse(ALGraph G,void(*Visit)(char*));
	void DFS(ALGraph G,int v);
	ALGraph  graph,graph1;//构造有向图graph，graph存储逆邻接表
	CreateGraph(graph,graph1);
	 
	DFSTraverse(graph,print);
	DFSTraverseGr(graph1,print);
 
}


 int LocateVex(ALGraph G,VertexType u)
 { // 初始条件: 图G存在,u和G中顶点有相同特征
   // 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1
    int i;
    for(i=0;i<G.vexnum;++i)
      if(strcmp(u,G.vertices[i].data)==0)
        return i;
    return -1;
 }
status  CreateGraph(ALGraph &G,ALGraph&Gr)
{//生成有向图的邻接表和逆邻接表
	int i,j,k;
	VertexType va,vb;
	ArcNode  *p,*q;
	printf("请输入图的顶点数,边数: ");
    scanf("%d%d",&G.vexnum,&G.arcnum);
    printf("请输入%d个顶点的字符串(<%d个字符，如v1，v2等):\n",G.vexnum,MAX_NAME);
	Gr.vexnum=G.vexnum;Gr.arcnum=G.arcnum;
    for(i=0;i<G.vexnum;++i) // 构造顶点向量
    {
        scanf("%s",G.vertices[i].data);
		strcpy(Gr.vertices[i].data,G.vertices[i].data);
        G.vertices[i].firstarc=Gr.vertices[i].firstarc=NULL;
    }
    printf("请顺序输入每条弧(边)的弧尾和弧头:\n");
    for(k=0;k<G.arcnum;++k) // 构造表结点链表
    {
		printf("\n第%d条弧:",k+1);
		scanf("%s%s",va,vb);
		i=LocateVex(G,va); // 弧尾
		j=LocateVex(G,vb); // 弧头
		p=(ArcNode*)malloc(sizeof(ArcNode));//邻接表中的表节点
		q=(ArcNode*)malloc(sizeof(ArcNode));//逆邻接表中的表节点
		p->adjvex=j;
		p->nextarc=G.vertices[i].firstarc; // 插在表头
        G.vertices[i].firstarc=p;
		q->adjvex=i;
		q->nextarc=Gr.vertices[j].firstarc;
		Gr.vertices[j].firstarc=q;
	}
	return OK;
} 
VertexType& GetVex(ALGraph G,int v)
 { // 初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值
   if(v>=G.vexnum||v<0)
     exit(ERROR);
   return G.vertices[v].data;
 }
int FirstAdjVex(ALGraph G,VertexType v)
 { // 初始条件: 图G存在,v是G中某个顶点
   // 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1
   ArcNode *p;
   int v1;
   v1=LocateVex(G,v); // v1为顶点v在图G中的序号
   p=G.vertices[v1].firstarc;
   if(p)
     return p->adjvex;
   else
     return -1;
 }
 int NextAdjVex(ALGraph G,VertexType v,VertexType w)
 { // 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点
   // 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。
   //           若w是v的最后一个邻接点,则返回-1
   ArcNode *p;
   int v1,w1;
   v1=LocateVex(G,v); // v1为顶点v在图G中的序号
   w1=LocateVex(G,w); // w1为顶点w在图G中的序号
   p=G.vertices[v1].firstarc;
   while(p&&p->adjvex!=w1) // 指针p不空且所指表结点不是w
     p=p->nextarc;
   if(!p||!p->nextarc) // 没找到w或w是最后一个邻接点
     return -1;
   else // p->adjvex==w
     return p->nextarc->adjvex; // 返回v的(相对于w的)下一个邻接顶点的序号
 }
void (*VisitFunc)(char* v); // 函数变量(全局量)
void print(char *v)
 {
   printf("%s ",v);
 }
int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量)
int finished[MAX_VERTEX_NUM];
int count;
void DFS(ALGraph G,int v)
 { // 从第v个顶点出发递归地深度优先遍历图G。算法7.5
   int w;
   VertexType v1,w1;
   strcpy(v1,GetVex(G,v));
   visited[v]=TRUE; // 设置访问标志为TRUE(已访问)
   VisitFunc(G.vertices[v].data); // 访问第v个顶点
   for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,GetVex(G,w))))
     if(!visited[w])
       DFS(G,w); // 对v的尚未访问的邻接点w递归调用DFS
	 finished[count++]=v;
 }
void DFSTraverse(ALGraph G,void(*Visit)(char*))
 { // 对图G作深度优先遍历。算法7.4
	  count=0;//计数变量初始化
    int v;
    VisitFunc=Visit; // 使用全局变量VisitFunc,使DFS不必设函数指针参数
    for(v=0;v<G.vexnum;v++)
		visited[v]=FALSE; // 访问标志数组初始化
    for(v=0;v<G.vexnum;v++)
		if(!visited[v])
			DFS(G,v); // 对尚未访问的顶点调用DFS
    printf("\n");
 }
void DFSGr(ALGraph &G,int v)
 { // 从第v个顶点出发递归地深度优先遍历图G。算法7.5
   int w;
   VertexType v1,w1;
   strcpy(v1,GetVex(G,v));
   visited[v]=TRUE; // 设置访问标志为TRUE(已访问)
 //  VisitFunc(G.vertices[v].data); // 访问第v个顶点
   for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,GetVex(G,w))))
     if(!visited[w])
       DFSGr(G,w); // 对v的尚未访问的邻接点w递归调用DFS
	 printf("%s",GetVex(G,v));
 }
void DFSTraverseGr(ALGraph G,void(*Visit)(char*))
{ // 对图G的逆邻接表作作深度优先遍历。算法7.4
//	   从finishied[G.vexnum-1]开始遍历
    int v;int num=G.vexnum-1;int i=0;
    VisitFunc=Visit; // 使用全局变量VisitFunc,使DFS不必设函数指针参数
    for(v=0;v<G.vexnum;v++)
		visited[v]=FALSE; // 访问标志数组初始化
    for( ;v=finished[num],num>=0;num--)
	 	if(!visited[v])
		{
			printf("\n第%d个强连通分量:",++i);
			DFSGr(G,v); // 对尚未访问的顶点调用DFS
		}
	printf("\n");
}