主题:怎样构造有向图?
zouf2003
[专家分:0] 发布于 2005-11-16 22:23:00
那位帮忙指点,怎样构造一个有向图?给出思路,有源代码最好
回复列表 (共4个回复)
沙发
fime20044 [专家分:230] 发布于 2006-01-01 21:09:00
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);
}
板凳
zouf2003 [专家分:0] 发布于 2006-03-13 22:12:00
多谢!
3 楼
雨523 [专家分:200] 发布于 2006-06-20 23:52:00
顶
4 楼
雨523 [专家分:200] 发布于 2006-06-26 09:09:00
再看看
我来回复