回 帖 发 新 帖 刷新版面

主题:求助!有关图的操作

要实现图(无向图和有向图均可)的邻接矩阵和邻接表的存储结构的相关代码,要用c写的,我实在是作不出来,它老是有错,所以想参考一下高手的,小女子感激不尽~

回复列表 (共7个回复)

沙发


这个是邻接矩阵的算法:
#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);
}

板凳

带权有向图建立邻接表结构
#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 楼

带权无向图建立邻接表结构
#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 楼

#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 楼


//确定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 楼

这个是定位v1和v2在定点中的位置,为了后面的创建二位数组找i和j,
谢谢了,我前面忘了加包含函数了,加上在修改一下就可以了

7 楼

我来回复

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