（一）图与网络的基本概念

一、无向图

     含有的元素为顶点，弧和权重，但是没有方向

二、有向图

     含有的元素为顶点，弧和权重，弧具有方向。

三、有限图、无限图

     顶点和边有限就是有限图，否则就是无限图。

四、简单图

     既没有环，也没有两条边连接同一对顶点的图

五、完全图、二分图

     每一对不同的顶点都有一条边相连的简单图称为完全图。

六、子图

     就是被包含的图

七、顶点的度

     就是顶点连接了几条边。

性质：1、全部顶点的度相加为偶数

        2、 任意一个图的奇顶点的个数为偶数。

（二）图与网络的数据结构

一、邻接矩阵表示法

1、定义：

      就是0-1矩阵，如果元素cij为“1”表示弧从第i个到第j个点，为“0”的话表示没有。如果是无向图则必定cij=cji。

2、一个demo：

3、缺点

      浪费大量的空间

二、关联矩阵表示法

1、定义

      在关联矩阵中，每行对应图的一个节点，每列对应图的一条弧。如果元素为“1”为一条弧的起点，元素为“-1”是一条弧的终点，元素为“0”与弧没有关联。

2、缺点：

      浪费大量的弓箭

3、一个demo

三、弧表表示法

1、定义：

     上面两种方法都是以点优先，这种方法以边优先，记录下来每个边的起点，终点和权重。

2、一个demo

四、邻接表表示法

1、定义

     就是用一个单向链表存储所有的顶点，然后每个顶点又是一个单向链表的头指针， 引导着每个由它出发的弧。

2、一个demo

五、星形表示法

1、前向星形表示法

（1）定义：

     定义2个数组，一个数组记录边信息的数组，跟换标表示法类似，然后还有一个数组记录每个出弧的起始地址编号

（2）demo

（3）性质

a、在point数组中，节点号比图的顶点多一个，一定要有point(1)=1,point(n)=m+1，

b、对于一个节点i，其对应的弧的信息数组的位置区间为

    如果，则没有出弧。

（4）评价

    能快速检索每个节点的所有出弧，但是没有办法快速检索每个节点的所有入弧。

2、后向星形表示法

（1）定义：

     定义2个数组，一个数组记录边信息的数组，跟换标表示法类似，然后还有一个数组记录每个出弧的起始地址编号，但是是记录从终点到顶点。

（2）demo

3、双星型表示法

（1）加前向星形表示法的基础上，再加上一个正向弧对应的编号即可

（2）demo

（三）应用——最短路问题

一、两个指定顶点之间的最短路径

1、例子一：

     解法：

2、例子二：

clc,clear;a=zeros(6);a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;a(2,3)=15;a(2,4)=20;a(2,6)=25;a(3,4)=10;a(3,5)=20;a(4,5)=10;a(4,6)=25;a(5,6)=55;a=a+a‘;ll=find(a==0);a(ll)=inf;pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));d(1:length(a))=inf;d(1)=0;temp=1;while sum(pb)<length(a)    tb=find(pb==0);    d(tb)=min(d(tb),d(temp)+a(temp,tb));    tmpb=find(d(tb)==min(d(tb)));    temp=tb(tmpb(1));    pb(temp)=1;    index1=[index1,temp];    temp2=find(d(index1)==d(temp)-a(temp,index1));    index2(temp)=index1(temp2(1));endd,index1,index2

建模算法（五）——图与网络