邻接矩阵与邻接表

// 邻接矩阵
#include<stdio.h>
#include<string.h>
#define MAXN 100
int Edge[MAXN][MAXN];
int main()
{
   // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    int m,n,i,j,id,od,u,v;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(m==0&&n==0)  break;
        memset(Edge,0,sizeof(Edge));
        for(i=0; i<m; i++)
        {
            scanf("%d%d",&u,&v);
            Edge[u-1][v-1]=1;
        }
        for(i=0; i<n; i++)
        {
            od=0;
            for(j=0; j<n; j++)
                od+=Edge[i][j];
            if(i==0) printf("%d",od);
            else printf(" %d",od);
        }
        printf("\n");
        for(i=0; i<n; i++)
        {
            id=0;
            for(j=0; j<n; j++)
                id+=Edge[j][i];
            if(i==0) printf("%d",id);
            else printf(" %d",id);
        }
        printf("\n");
    }
    return 0;
}
//邻接表
#define MAXN 100
#include<stdio.h>

struct arcnode   //边结点
{
    int adjvex;        //有向边的另一个邻接点的序号
    arcnode *nextarc;   //指向下一个边结点的指针
};
struct vnode     //  顶点
{
    int data;    //   顶点信息
    arcnode *head1;   // 出边表的表头指针
    arcnode *head2;   //  入边表的表头指针
};
struct lgraph              //图的邻接表存储结构
{
    vnode vertexs[MAXN];  //顶点数组
    int vexnum,arcnum;    //顶点数和边数
} lg;
void createlg()
{
    int i;
    arcnode *pi; //用来构造边链表的边结点指针
    int v1,v2;   // 有向边的2个顶点
    for(i=0; i<lg.vexnum; i++)
        lg.vertexs[i].head1=lg.vertexs[i].head2=NULL;
    for(i=0; i<lg.arcnum; i++)
    {
        scanf("%d%d",&v1,&v2);  //输入一条边的起点和终点
        v1--;
        v2--;
        pi=new arcnode;  //假设有足够空间
        pi->adjvex=v2;
        pi->nextarc=lg.vertexs[v1].head1; //插入链表
        lg.vertexs[v1].head1=pi;

        pi=new arcnode;  //假设有足够空间
        pi->adjvex=v1;
        pi->nextarc=lg.vertexs[v2].head2; //插入链表
        lg.vertexs[v2].head2=pi;
    }
}
void deletelg()
{
    int i;
    arcnode *pi;
    for(i=0; i<lg.vexnum; i++)
    {
        pi=lg.vertexs[i].head1;
        while(pi!=NULL)
        {
            lg.vertexs[i].head1=pi->nextarc;
            delete pi;
            pi=lg.vertexs[i].head1;
        }
        pi=lg.vertexs[i].head2;
        while(pi!=NULL)
        {
            lg.vertexs[i].head2=pi->nextarc;
            delete pi;
            pi=lg.vertexs[i].head2;
        }
    }
}
int main()
{
    //freopen("input.txt","r",stdin);
    int i,id,od;
    arcnode *pi;
    while(1)
    {
        lg.vexnum=lg.arcnum=0;
        scanf("%d%d",&lg.vexnum,&lg.arcnum);
        if(lg.vexnum==0) break;
        createlg();
        for(i=0;i<lg.vexnum;i++)
        {
            od=0;
           pi=lg.vertexs[i].head1;
           while(pi!=NULL)
           {
               od++;
               pi=pi->nextarc;
           }
           if(i==0) printf("%d",od);
           else  printf(" %d",od);
        }
        puts("");
        for(i=0;i<lg.vexnum;i++)
        {
            id=0;
            pi=lg.vertexs[i].head2;
            while(pi!=NULL)
            {
                id++;
                pi=pi->nextarc;
            }
           if(i==0) printf("%d",id);
           else  printf(" %d",id);
        }
        puts("");
        deletelg();
    }
    return 0;
}
时间: 2024-10-25 13:25:30

邻接矩阵与邻接表的相关文章

数据结构之自建算法库——图及其存储结构(邻接矩阵、邻接表)

本文是[数据结构基础系列(7):图]中第4课时[图的邻接矩阵存储结构及算法]和第5课时[图的邻接表存储结构及算法],并为后续内容的实践提供支持. 图的存储结构主要包括邻接矩阵和邻接表,本算法库提供存储结构的定义,以及用于构造图存储结构.不同结构的转换及显示的代码.算法库采用程序的多文件组织形式,包括两个文件: 1.头文件:graph.h,包含定义图数据结构的代码.宏定义.要实现算法的函数的声明: #ifndef GRAPH_H_INCLUDED #define GRAPH_H_INCLUDED

C#中如何实现图的邻接矩阵和邻接表的显示

问题描述 C#中如何实现图的邻接矩阵和邻接表的显示,用silverlight实现的 解决方案 解决方案二:怎么没有人回答该问题那

图(网)的存储结构(数组存储表示即邻接矩阵、邻接表)

图(Graph)是一种非线性结构 图的特点(多对多),顶点之间的关系是任意的,图中任意两个顶点之间都可能相关,顶点的前驱和后继个数无限制. 图:数据元素间存在多对多关系的数据结构,加上一组基本操作构成的抽象数据类型. 图的基本术语   顶点:图中的数据元素. 弧:若 <v, w>∈VR,则 <v, w> 表示从 v 到 w 的一条弧,且称 v 为弧尾,称 w 为弧头,此时的图称为有向图.  G1 = (V1, A1)          V1 = {v1, v2, v3, v4} A

无向图 邻接表-无向图的存储结构,求大神求大神

问题描述 无向图的存储结构,求大神求大神 Description 给出一个有n个顶点的无向图,顶点编号从0到n-1.给出每一条边,输出该图的邻接矩阵和邻接表. Input 输入的第一行是顶点数n和边数 e . 1 ≤ n ≤ 300 ,1 ≤ e ≤ 1000 接下来是 e 行,每行2个整数 i , j ( 0 ≤ i, j < n ) ,表示顶点 i 和 j 之间有一条边. Output 输出该图的邻接矩阵.邻接表按顶点编号每行从小到大,每列也是从小到大. 然后输出一个空行. 接着输出该图的邻

邻接矩阵(以顶点为中心),比较稀疏时,采用邻接表;图的两种遍历

对于边比较稠密的图,可以采用邻接矩阵(以顶点为中心)的方式表示,而边比较稀疏时,采用邻接表的结构更合适.两种都不能直观表达哪两个点相连或者最短路径是什么. 深度优先遍历类似于树的先根序遍历.与树不同的是,它需要对已经访问过的节点添加标记以免被重复遍历. public class Depth { /** * 对k号节点深度遍历 * @param a * @param color * @param k 节点 */ public static void depthTraversal(int[][] a

acm-邻接矩阵能进行深搜么。现在会邻接表的深搜,还用把邻接矩阵转化为邻接表吗

问题描述 邻接矩阵能进行深搜么.现在会邻接表的深搜,还用把邻接矩阵转化为邻接表吗 邻接矩阵如果能进行的话.麻烦大神给点代码啊.小白..如题...... 解决方案 void dfs(int i){ visited[i]=1; for(int j=0;j<n;j++){ if(G[i][j]==1&&visited[j]==0){ dfs(j); } } } 解决方案二: 这是用邻接矩阵求最小生成树的,题主看下能否帮的上忙,如果能帮的上,希望可以采纳 #include #include

大话数据结构十九:图的存储结构之邻接表

1. 邻接表(无向图)的特点: 有时候邻接矩阵并不是一个很好的选择: 如上图: 边数相对顶点较少,这种结构无疑是存在对存储空间的极大浪费. 邻接表: 数组和链表结合一起来存储. 1.)顶点用一个一位数组存储. 2.)每个顶点Vi的所有邻接点构成一个线性表,由于邻接点的个数不确定,所以我们选择单链表来存储. 更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/ 2. 邻接表(有向图)的特点: 把顶点当弧尾建立的邻

数据结构的C++实现之图的存储结构之邻接表

对于图来说,邻接矩阵是不错的一种图存储结构,但是我们也发现,对于边数相对顶点较少的图,这种结构是存在对存 储空间的极大浪费的.因此我们考虑另外一种存储结构方式:邻接表(Adjacency List),即数组与链表相结合的存储方法 . 邻接表的处理方法是这样的. 1.图中顶点用一个一维数组存储,另外,对于顶点数组中,每个数据元素 还需要存储指向第一个邻接点的指针,以便于查找该顶点的边信息. 2.图中每个顶点vi的所有邻接点构成一个线性 表,由于邻接点的个数不定,所以用单链表存储,无向图称为顶点vi

【算法导论】邻接表存储的拓扑排序

        上一篇文章中讲述了用邻接矩阵存储的图的拓扑排序,下面本文介绍用邻接表存储的图的拓扑排序.         关于拓扑排序的概念及基本思想,我在上一篇文章中已经较为详细的描述了,这里不在介绍.我们知道利用邻接矩阵进行拓扑排序时,程序实现较为简单,但是效率不高,算法的复杂度为O(n^3).而利用邻接表会使入度为0的顶点的操作简化,从而提高算法的效率. 在邻接表存储结构中,为了便于检查每个顶点的入度,可在顶点表中增加一个入度域(id),这样的邻接表如下图所示,这样只需对由n个元素构成的顶