用户注册



邮箱:

密码:

用户登录


邮箱:

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

发表随想


还能输入: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、请勿发布广告信息或其他无关评论,否则将会删除评论并扣分,严重者给予封号处理。


扫码下载

加载中,请稍后...

输入口令后可复制整站源码

加载中,请稍后...