MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
图的存储  链表 和 矩阵存储

矩阵存储 :


#include <stdio.h>
#include 
<string.h>

int main(){
    freopen(
"M.in""r", stdin);
    freopen(
"M.out""w", stdout);
    
int m, n, map[100][100], u, v, i, j;
    
while(scanf("%d%d"&n, &m) != -1){
        memset(map, 
0sizeof(map));
        
for(i = 0; i < m; i++){
            scanf(
"%d%d"&u, &v);
            map[u][v] 
= map[v][u] = 1//代表 u->v   v -> u 两条边
        }
        
for(i = 0; i < n; i++){
            
for(j = 0; j < n; j++)
                printf(
"%d ", map[i][j]);
            puts(
"");
        }
    }
    
return 0;
}


链表存储 :

#include <stdio.h>
#include 
<string.h>
struct e{
    
int v;
    
struct e* next;
};
e
* edge[100];
int m, n;
int main(){
    freopen(
"link_new.in""r", stdin);
    freopen(
"link_new.out""w", stdout);
    
int i, j, u, v;
    e
* node;
    
while(scanf("%d%d"&n, &m) != -1){
        
for(i = 0; i < 100; i++)edge[i] = NULL;
        
for(i = 0; i < m; i++){
            scanf(
"%d%d"&u, &v);
            node 
= new e;
            node
->= v;
            node
->next = edge[u];//只想指针数组所指的链表内第一个元素,其实就相当于记录一下指针数组的所指的位置
            edge[u] = node;//把指针数组只想插入的节点,就连接上了。 倒序插入
            node = new e;
            node
->= u;
            node
->next = edge[v];
            edge[v] 
= node;
        }
        
for(i = 0; i < n; i++){
            node 
= edge[i];
            printf(
"%d : ", i);
            
while(node){
                printf(
"%d ", node->v);
                node 
= node -> next;
            }
            puts(
"");
        }
    }
    
return 0;
}


posted on 2009-10-06 23:11 memorygarden 阅读(111) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理