邻接表

转自http://blog.csdn.net/lgdblue/article/details/24846211

Def:邻接表是图的链式存储结构,其意义是把每个邻接于vi的顶点连接成一个单链表,这个单链表就成为该顶点的邻接表。

实现方法:

1、动态建表

Method:对于每个读入的边建立一个邻接表节点的对象,加入到相应的邻接表中,同时动态申请内存。

Property:

(1)对于无向图的邻接表,每个顶点度就是该顶点的邻接表中节点数。

(2)对于有向图,第i个链表(邻接表)中的节点数是vi节点的出度;求其入度需要遍历整个邻接表或者建立你邻接表。

(3)对于同一个图,输入边的顺序不同,其邻接表也不一样。

AnalystS:

(1)时间效率:O(m),空间效率O(m)。

(2)根据需求动态申请内存,需要多少内存就申请多少。

AnalystW:

(1)需要考虑内存的释放问题。

(2)一次性申请内存与随机申请再申请总数一定的时候前者消耗时间少。

(3)判断任意两个顶点之间是否有边连接时需要搜索这两个点的链表。

#include<iostream>
#include<cstdio>
using namespace std;

#define maxn 100

struct Edgenode //邻接表节点
{
    int to;//边指向的终点
    int w;//该边的权值
    Edgenode *next;//指向当前点上一次已经保存的邻接点,把该点的所有邻接点连到一起
};

struct Vnode //表头节点
{
    int from; //节点序号
    Edgenode *first; //指向该节点邻接表中第一个节点。
};

Vnode adjlist[maxn];  //整个图的邻接表

int main()
{
    int i,j,w;
    int n;
    scanf("%d",&n);
    int N = n;
    while(N--)
    {
        cin>>i>>j>>w;
        Edgenode *p = new Edgenode(); //对于每个新读入节点新建一个邻接表节点

        p->to = j;
        p->w = w;
        p->next = adjlist[i].first;
        adjlist[i].first = p;
    }
    cout<<endl;

    for(i = 1; i <= n; i++)
    {
        for(Edgenode * k = adjlist[i].first; k != NULL; k = k->next)
        {
            cout<<i<<" "<<k->to<<" "<<k->w<<endl;
        }
    }
}
/*
12
5 8 29
6 1 12
8 3 11
1 2 4
3 1 22
4 3 17
7 4 25
6 5 9
8 7 7
1 6 9
3 2 19
6 7 4
*/

2、STL(vector) 模拟链表

原理同1,不同的是用STL中的vector模拟链表

#include<iostream>
#include<cstdio>
#include<vector>
//#include<map>
using namespace std;

#define maxn 100

struct node
{
    int from;
    int to;
    int w;
};
struct Edgenode
{
    int to;
    int w;
};
vector <node> map[maxn];
int main()
{
    int i,j,w;
    int n;
    scanf("%d",&n);
    int N = n;
    Edgenode e;
    while(N--)
    {
        cin>>i>>j>>w;
        e.to = j;
        e.w = w;
        map[i].push_back(e);
    }
    cout<<endl;
    for(i = 1; i <= n; i++)
    {
        for(vector<node>::iterator k = map[i].begin(); k != map[i].end(); k++)
        {
            node t = *k;
            cout<<i<<" "<<t.to<<" "<<t.w<<endl;
        }
    }

3、静态建表(链式前向星)

Def:基于前向星的方法,只是在前向星的基础上增加next的数组,省去了排序的过程,可以替代邻接表。

Method:采用数组模拟链表方式替代邻接表。

AnalystS:

(1)建图效率高,与读入图同步。

(2)时间复杂度O(m),空间复杂度O(m+n)

(3)可以存储重边。

(4)可以应付点和边的数量都很大的时候。

(5)不需要内存管理。

AnalystW:不不能直接由起点和终点直接确定是否有边。

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;

#define v 100

int head[v];
struct Edgenode
{
    int to;
    int w;
    int next;
}edge[v];
int main()
{
    int i,j,w,m,n;
    scanf("%d %d",&n,&m);//m:边的数目 ,n: 点的数目
    int k = 1;
    memset(head,-1,sizeof(head));
    while(k <= m)
    {
        cin>>i>>j>>w;
        edge[k].to = j;
        edge[k].w = w;
        //数组模拟链表的主要方式是记录下一个节点在数组的哪个位置
        edge[k].next = head[i];
        head[i] = k;//存储描述点i边信息的链的起点在edge数组中的位置。
        k++;
        //构造前向星是将信加入的节点放到对用链的最开始并修改head数组中对应的位置
    }
    for(i = 1; i <= m; i++)
    {
        for(k = head[i]; k != -1; k = edge[k].next)
            cout<<i<<" "<<edge[k].to<<" "<<edge[k].w<<endl;
    }
}
/*
input:
4 5
1 4 5
1 2 4
2 3 3
3 1 8
3 4 7
*/

该部分深入学习可以参考Malash 大牛的博客 http://malash.me/200910/linked-forward-star/