主题:求助!有关图的操作
你很狼嘛
[专家分:110] 发布于 2006-05-09 22:17:00
要实现图(无向图和有向图均可)的邻接矩阵和邻接表的存储结构的相关代码,要用c写的,我实在是作不出来,它老是有错,所以想参考一下高手的,小女子感激不尽~
回复列表 (共7个回复)
沙发
findlyhl [专家分:280] 发布于 2006-05-10 10:17:00
这个是邻接矩阵的算法:
#include <stdio.h>
#define maxvalue 0
#define maxvnum 100
void vertex(int A[][maxvnum],int n,int e)
{
int i,j,k,weight;
for(i=0; i<n; i++)
for(j=0; j<n; j++)
A[i][j] = maxvalue;
for(k=0; k<e; k++)
{
printf("i=?,j=?,weight=?\n");
scanf("%d%d%d",&i,&j,&weight);
A[i][j] = weight;
A[j][i] = weight;
}
printf("\n邻接矩阵为:\n");
for(i=0; i<n; i++)
{ for(j=0; j<n; j++)
printf(" %d ",A[i][j]);
printf("\n");
}
}
void main()
{
int n,e;
n = 5;
e = 5;
int A[5][maxvnum];
vertex(A,n,e);
}
板凳
findlyhl [专家分:280] 发布于 2006-05-10 10:19:00
带权有向图建立邻接表结构
#include <stdio.h>
#include <malloc.h>
typedef struct edge //声明一个边结点类型
{
int adjvex;
int weight;
struct edge *next;
}elink;
typedef struct ver //声明一个顶点结点类型
{
int vertex;
elink *link;
}vlink;
//输入带权有向图的n个顶点(假设以序号i表示第i个顶点)和e个表示边的顶点偶对,建立其邻接表结构
void adjlist(vlink G[],int n,int e)
{
int k,vi,vj,weight,h;
elink *p,*q;
for(k = 0; k < n; k++)
{
G[k].vertex = k+1; //建立n个顶点结点
G[k].link = NULL;
}
for(k = 0; k < e; k++)
{
printf("\n输入顶点偶对和权值\n");
scanf("%d%d%d",&vi,&vj,&weight); //输入顶点偶对和权值
p = (elink*)malloc(sizeof(elink)); //申请一个边结点
p->adjvex = vj-1;
p->weight = weight;
p->next = NULL;
if(G[vi-1].link == NULL)
G[vi-1].link = p;
else
{
q = G[vi-1].link;
while(q->next)
q = q->next;
q->next = p;
}
}
for(k = 0; k < n; k++) //输出
{
printf(" %d ",G[k].vertex);
if(G[k].link)
{
p = G[k].link;
while(p)
{
printf("adjvex: %d weight: %d ",p->adjvex,p->weight);
p = p->next;
}
printf("\n");
}
else
printf("\n");
}
}
void main()
{
int n,e;
printf("\n输入带权有向图的n个顶点(假设以序号i表示第i个顶点)和e个表示边的顶点偶对:\n");
scanf("%d%d",&n,&e);
vlink G[100];
adjlist(G,n,e);
}
3 楼
findlyhl [专家分:280] 发布于 2006-05-10 10:21:00
带权无向图建立邻接表结构
#include <stdio.h>
#include <malloc.h>
typedef struct edge
{
int adjvex;
int weight;
struct edge *next;
}elink;
typedef struct ver
{
int vertex;
elink *link;
}vlink;
void adjlist(vlink G[],int n,int e)
{
elink *p,*q,*r,*m;
int vi,vj,k,weight,h;
for(k = 0; k < n; k++)
{
G[k].vertex = k+1;
G[k].link = NULL;
}
for(k = 0; k < e; k++)
{
printf("\n输入顶点偶对和权值:\n");
scanf("%d%d%d",&vi,&vj,&weight);
p = (elink*)malloc(sizeof(elink));
p->adjvex = vj-1;
p->weight = weight;
p->next = NULL;
if(G[vi-1].link == NULL)
G[vi-1].link = p;
else
{
q = G[vi-1].link;
while(q->next)
q = q->next;
q->next = p;
}
r = (elink*)malloc(sizeof(elink));
r->adjvex = vi-1;
r->weight = weight;
r->next = NULL;
if(G[vj-1].link == NULL)
G[vj-1].link = r;
else
{
m = G[vj-1].link;
while(m->next)
m = m->next;
m->next = r;
}
}
for(k = 0; k < n; k++) //输出
{
printf(" %d ",G[k].vertex);
if(G[k].link)
{
p = G[k].link;
while(p)
{
printf("adjvex: %d weight: %d ",p->adjvex,p->weight);
p = p->next;
}
}
printf("\n");
}
}
void main()
{
int n,e;
printf("输入带权无向图的n个结点和e个表示边的顶点偶对:\n");
scanf("%d%d",&n,&e);
vlink G[100];
adjlist(G,n,e);
}
4 楼
你很狼嘛 [专家分:110] 发布于 2006-05-10 18:21:00
#define infinity int_max
#define max_vertex_num 20
#define ok 1
#define error 0
typedef int vertextype;
typedef int vrtype;
typedef char gtelemtype;
typedef enum{dg,udg}graphkind;
typedef struct arccell{
vrtype adj;
}arccell,adjmatrix[max_vertex_num][max_vertex_num];
typedef struct{
vertextype vexs[max_vertex_num];
adjmatrix arcs;
int vexnum,arcnum;
graphkind kind;
}mgraph;
//确定v1,v2在g中的位置
status locatevex(mgraph &g,char v){
int i;
for(i=0;i<g.vexnum;i++)
if(v=g.vexs[i])
return i;
}
//无向图的构造(数组)
status createudg(mgraph &g){
int i,j,k;
gtelemtype v1,v2;
printf("请输入顶点数和弧数:");
scanf("%d %d",&g.vexnum,&g.arcnum);
for(i=0;i<g.vexnum;i++)
scanf("%d",&g.vexs[i]);
for(k=0;k<g.vexnum;i++){
scanf("%c %c",&v1,&v2);
i=locatevex(g,v1);
j=locatevex(g,v2);
g.arcs[j][i]=g.arcs[i][j];
}
return ok;
}
void main(){
mgraph g;
createudg(g);
}
能帮我看一下这个有什么问题吗?
我运行他老说有错
5 楼
findlyhl [专家分:280] 发布于 2006-05-11 11:42:00
//确定v1,v2在g中的位置
status locatevex(mgraph &g,char v){
int i;
for(i=0;i<g.vexnum;i++)
if(v=g.vexs[i])
return i;
}
你的这部分是什么意思,?好象有错
6 楼
你很狼嘛 [专家分:110] 发布于 2006-05-11 16:14:00
这个是定位v1和v2在定点中的位置,为了后面的创建二位数组找i和j,
谢谢了,我前面忘了加包含函数了,加上在修改一下就可以了
7 楼
雨523 [专家分:200] 发布于 2006-06-20 23:29:00
好
我来回复