回 帖 发 新 帖 刷新版面

主题:怎样构造有向图?

那位帮忙指点,怎样构造一个有向图?给出思路,有源代码最好

回复列表 (共4个回复)

沙发

VC++6.0上运行的:
#include<iostream.h>
#include<stdlib.h>
#define maxsize 20
typedef struct edgeNode //边结点定义
{
   struct edgeNode *nextarc;//指向下一个邻接顶点指针
   int adjdata;//邻接顶点的值
   int weight;//弧的权
   }edgeNode;
typedef struct vexNode//顶点结点定义
{  int visit;//访问
   int id;//顶点入度值
   int data;//顶点的值
   struct edgeNode *firstarc;//指向第一个邻接顶点的指针
}vexNode;
typedef struct//图的定义
{
  struct vexNode *list;//指向图首地址的指针
   int vernum,arcnum;//图的边数和顶点数
}graph;
int locate(graph &g,int v1,int w)//判断v1是否是图的顶点
{
   for(int i=0;i<g.vernum;i++)
   {
       if(v1==g.list[i].data&&w==1)
           return i;
   }
   return -1;
}
void creat(graph &g)            //图的创建
{  int i=0;                     //循环变量
   cout<<"输入顶点数和边数:"<<endl;
   cin>>g.vernum>>g.arcnum;
    if(!(g.list=(vexNode *)malloc(g.vernum*sizeof(vexNode))))
       return ;
    for(i=0;i<g.vernum;i++)
   {
       cout<<"g.list["<<i<<"]=";
       cin>>g.list[i].data;
       cout<<"输入入度:";
       cin>>g.list[i].id;
       g.list[i].firstarc=NULL;
       g.list[i].visit=0;
    }
    edgeNode *p=NULL;//定义了指向边结点的指针
    for(int k=0;k<g.arcnum;k++)
   {
          int v1=0,v2=0,w=1,j=0;
             cout<<"输入v1和v2:"<<endl;
             cin>>v1>>v2;
          i=locate(g,v1,w);
          j=locate(g,v2,w);
          if(!(p=(edgeNode *)malloc(sizeof(edgeNode))))  //为边结点分配空间
             return ;
          p->adjdata=j;
          p->weight=w;
             p->nextarc=g.list[i].firstarc;
          g.list[i].firstarc=p;
      }
}
void print(graph &g)  //输出
{
    edgeNode *p;//定义了指向边结点的指针
    int i=0;
        cout<<"输出顶点:"<<endl;
    for(i=0;i<g.vernum;i++)
        cout<<g.list[i].data<<' ';
    cout<<endl;
    cout<<"图的邻接链表为:"<<endl;
    for(i=0;i<g.vernum;i++)
    {
        cout<<g.list[i].data<<' ';
        p=g.list[i].firstarc;
        //if(p=NULL)
        //cout<<"不存在链表";    
        while(p)
            {
            cout<<g.list[p->adjdata].data<<' ';
                p=p->nextarc;
            }
            cout<<endl;
        }
}
void Destroy(graph &g)//
{    edgeNode *q=NULL,*p=NULL;//定义了指向边结点的指针
   for(int i=0;i<g.vernum;i++)
    {
       p=g.list[i].firstarc;
       q=p;
       while(p)
       {
           p=p->nextarc;
           delete q;
           q=p;
       }
   }
     delete[]g.list;
}
#include"1.h"
void main()
{
  graph G;
  creat(G);
  print(G);
  Destroy(G);
}

板凳

多谢!

3 楼

4 楼

再看看

我来回复

您尚未登录,请登录后再回复。点此登录或注册