用户注册



邮箱:

密码:

用户登录


邮箱:

密码:
记住登录一个月忘记密码?

发表随想


还能输入:200字
云代码 - c++代码库

图的建立

2017-09-14 作者:云代码会员举报

[c++]代码库

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

//表结点
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;

//头结点
typedef struct Vnode
{
  char data;
  ArcNode *firstarc;
}Vnode;
bool visit[20];

//图结构
typedef struct Graph
{
	int point;
	int link;
	Vnode *VeArray;
	int flag;
}AlGraph;

//初始化图
void InitGraph(AlGraph *p,int ve,int arc)
{
 p->point=ve;
 p->link=arc;
 p->flag=0;
 p->VeArray=(Vnode *)malloc(sizeof(Vnode)*ve);
}
//用邻接表存储图
void CreateGraph(AlGraph *p)
{
	int i,j;
	char index;
	ArcNode	*Q,*S;
	printf("请依次输入各顶点:\n");
	for(i=0;i<p->point;i++)
	{
	    getchar();
		scanf("%c",&index);
		p->VeArray[i].data=index;
		p->VeArray[i].firstarc=NULL;
	}
	for(i=0;i<p->point;i++)
	{
	    getchar();
		S=(ArcNode *)malloc(sizeof(ArcNode));
		printf("依次输入与顶点 %c  相邻的顶点并以#结束:",p->VeArray[i].data);
		scanf("%c",&index);
		if(index)
		{
		j=0;
	    while(index!=p->VeArray[j].data)
			j++;
		 S->adjvex=j;
         p->VeArray[i].firstarc=S;
		 Q=S;
       	}
		else
		continue;
		scanf("%c",&index);
		while(index!='#')
		{
		   S=(ArcNode *)malloc(sizeof(ArcNode));
		   j=0;
		   while(index!=p->VeArray[j].data)
			   j++;
		    S->adjvex=j;
		    Q->nextarc=S;
		    Q=S;
			scanf("%c",&index);
		}
		Q->nextarc=NULL;
	}
}
//输出邻接表
void  showGraph(AlGraph *p)
{
	int i;
	ArcNode *temp;
	printf("顶点位置\t顶点名称\t邻接顶点的位置\n");
	for(i=0;i<p->point;i++)
	{
		printf("%4d\t\t %c  ->\t\t",i,p->VeArray[i].data);
		temp=p->VeArray[i].firstarc;
		while(temp)
		{
			printf("%d->\t",temp->adjvex);
			temp=temp->nextarc;
		}
		printf("\n");
	}
}

void DFS(AlGraph &p,int i)
{
   visit[i]=true;
   printf("%c->",p.VeArray[i].data);
   ArcNode *nextNode=p.VeArray[i].firstarc;
   while(nextNode)
{
    if(!visit[nextNode->adjvex])
        DFS(p,nextNode->adjvex);
        nextNode=nextNode->nextarc;
}
}
void DFStraverse(AlGraph &p)
{
    for(int i=0;i<p.point;i++)
       visit[i]=false;
   for(int i=0;i<p.point;i++)
   {
        if(!visit[i])
          DFS(p,i);
   }
}
int main ()
{
	int ve,arc;
	AlGraph p;
	printf("请输入无向图的顶点数和边数:\n");
	scanf("%d%d",&ve,&arc);
    InitGraph(&p,ve,arc);
	CreateGraph(&p);
	printf("\n无向图的邻接表存储结构如下:\n");
	showGraph(&p);
	printf("深度优先搜索无向图序列如下:\n");
	DFStraverse(p);
}


分享到:
更多

网友评论    (发表评论)


发表评论:

评论须知:

  • 1、评论每次加2分,每天上限为30;
  • 2、请文明用语,共同创建干净的技术交流环境;
  • 3、若被发现提交非法信息,评论将会被删除,并且给予扣分处理,严重者给予封号处理;
  • 4、请勿发布广告信息或其他无关评论,否则将会删除评论并扣分,严重者给予封号处理。