频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
算法学习 - 图的创建和打印
2015-03-13 08:35:48      个评论    来源:累了就歇一会  
收藏   我要投稿

图表示

之前的博客里已经说过了图的两种表示方法,一个是邻接链表,一个是邻接矩阵的方法。

前面适合稀疏图,后面自然就适合稠密图。

图创建

邻接矩阵

邻接矩阵其实就是二维矩阵,在前面的图表示已经简单的说过了,直接建立一个int G[NumVertex][NumVertex]然后直接输入就好了。

下面着重讲一下邻接链表的方法。

邻接链表

表示方法已经说过了,传送门:图表示。

下面看下代码:

struct Node{
    int val;
    int length;
    Node* next;
    Node(): val(0), length(0), next(NULL) {}
};

typedef Node* Graph;

Graph CreateG (Graph G){
    int num;
    scanf("%d", &num); // input the number of the vertex
    G = (Graph)malloc(sizeof(struct Node) * (num+1)); //malloc memory for graph
    G[0].length = num; //save the graph vertex number
    degree = (int *)malloc((num+1) * sizeof(int));
    memset(degree, 0, num*sizeof(int));
    for (int i = 1; i <= num; i++) {
        G[i].val = i;
        G[i].next = NULL;
        int outdegree = 0;
        scanf("%d", &outdegree);
        for (int j = 0; j < outdegree; j++) {
            Node* temp = (Node*)malloc(sizeof(struct Node));
            scanf("%d %d",&(temp->val), &(temp->length));
            temp->next = G[i].next;
            G[i].next = temp;
            degree[temp->val] += 1;
        }
    }
    return G;
}

这就是创建的代码了。

图打印

邻接链表

打印这里只说邻接链表的方法了,因为矩阵也是很简单。就是两层for循环就解决了。

下面看邻接链表的代码:

void PrintG (Graph G){
//    int length = sizeof(G)/sizeof(struct Node);
    int length = G[0].length;
    Node * temp;
    for (int i = 1; i <= length; i++) {
        temp = &G[i];
        printf("Node: %d ",temp->val);
        while (temp->next) {
            printf("-> %d(%d)",temp->next->val, temp->next->length);
            temp = temp->next;
        }
        printf("\n");
    }
}

代码就是上面的了,我这个打印没有在G[0].length已经保存了整个链表的顶点数。

点击复制链接 与好友分享!回本站首页
相关TAG标签 算法
上一篇:双缓冲显示位图
下一篇:算法学习 - 图的拓扑排序
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站