数据结构图网拓朴 - 金刚钻Johnny的日志

http://blog.csdn.net/hflyingheart/archive/2008/01/10/2032808.aspx

图的基本概念http://www.kangjiezx.net/jingsai/E_ReadNews.asp?NewsId=120

图的存储结构（1）http://www.kangjiezx.net/jingsai/E_ReadNews.asp?NewsID=121

图（Graph）是一种较线性表和树更为复杂的数据结构。在图结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关，因此，图结构的应用更加广泛。

一、图的基本概念

图是一种数据结构，它的形式化定义为Graph=（V，E）。其中，V是顶点的有穷非空集合；E是两个顶点之间的关系（边）的集合，通常用相关顶点的偶对来表示。

screen.width-333)this.width=screen.width-333" border=0>

在图（a）中，顶点的集合为V={v1，v2，v3，v4}；顶点之间用弧（有向边）相连，弧的起点称为弧头，弧的终点称为弧尾，用相关顶点的有序对来表示弧，则边的集合为E={<v1，v2>，<v1，v3>，<v3，v4>，<v4，v1>}；这类图称为有向图。

在图（b）中，顶点的集合为V={v1，v2，v3，v4，v5}；用相关顶点的无序对来表示边，则边的集合为E={（v1，v2），（v1，v4），（v2，v3），（v3，v4），（v4，v5）}；这类图称为无向图。

我们用n表示图中顶点数目，用e表示边或弧的数目，那么，对于无向图，e的取值范围是0到n(n-1)/2，有n(n-1)/2条边的无向图称为完全图。

对于有向图，e的取值范围是0到n(n-1)，具有n(n-1)条弧的有向图称为有向完全图。

有时图的边或弧具有一个和它相关的数，这个数叫做权，这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。

对于无向图，如果边（v，v’）∈E，则称顶点v和v’互为邻接点，即v和v’相邻接，或者说v和v’相关联。顶点v的度是指和v相关联的边的数目，记为TD(v)。

对于有向图，如果弧<v，v’>∈A，则称顶点v邻接到顶点v’。以顶点v为终点的弧的数目称为v的入度，记为ID(v)；以v为起点的弧的数目称为v的出度，记为OD（v）；顶点v的度为TD(v)= ID(v)+ OD(v)。

对于无向图，如果从顶点v出发，经过一个顶点序列（v=vi0，vi1，……，vim=v’）到达顶点v’，这个顶点序列称为路径。如果G是有向图，则路径也是有向的。

路径上的边或弧的数目称为路径的长度，如果第一个顶点和最后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为简单回路或简单环。

图的存储结构（1）

发表日期：2008年4月19日共浏览94 次作者：平凡心【编辑录入：zhaohui】

字体颜色：选择颜色黑色红色黄色绿色橙色紫色蓝色褐色墨绿深蓝赭石粉绿淡绿黄灰翠绿综红砖红淡蓝暗红玫瑰红紫红桔黄军黄烟灰深灰灰蓝【字体：放大正常缩小】【双击鼠标左键自动滚屏】【图片上滚动鼠标滚轮变焦图片】

2.1 邻接矩阵表示法

邻接矩阵是表示顶点之间相邻关系的矩阵，设G={V,E}是一个n个顶点的图，则G的邻接矩阵是一个n阶方阵，G[i,j]的值定义如下：

screen.width-333)this.width=screen.width-333" border=0>

(1).无向图的邻接矩阵一定是一个对称矩阵。

(2).不带权的有向图的邻接矩阵一般是稀疏矩阵。

(3).无向图的邻接矩阵的第i 行(或第i 列)非0 或非；元素的个数为第i 个顶点的度数。

(4).有向图的邻接矩阵的第i 行非0或非µ元素的个数为第i 个顶点的出度;第i 列非0或非µ元素的个数为第i 个顶点的入度。

2.2 邻接表表示法

核心思想:对具有n个顶点的图建立n个线性链表存储该图。

1. 每一个链表前面设置一个头结点,用来存放一个顶点的数据信息,称之为顶点结点。其中,data域存放某个顶点的数据信息; link 域存放某个链表中第一个结点的地址。

2. 第i 个链表中的每一个链结点表示以第i 个顶点为出发点的一条边;边结点的构造为

其中,next 域为指针域;

w 域为权值域(若图不带权,则无此域); v 域存放以第i 个顶点为出发点的一条边的另一端点在头结点数组中的位置。

screen.width-333)this.width=screen.width-333" border=0>

特点：

(1).无向图的第i个链表中边结点的个数是第i个顶点度数。

(2).有向图的第i个链表中边结点的个数是第i个顶点的出度。

(3).若图中有n个顶点、e条边，则采用邻接表存储无向图时，

需要n个顶点结点，2e个边结点；采用邻接表存储有向图

时，需要n个顶点结点，e个边结点。

有向图邻接表的建立过程：

procedure createlist(var g:list);

var s:edge;

begin

read(n,e); {n为顶点数，e为边数}

for i:=1 to n do

begin

read(g[i].data); {读入顶点信息}

g[i].link:=nil; {表头指针初始化}

end;

for k:=1 to e do

begin

read(i,j,w);

new(s);

s^.v:=j;

s^.w:=w;

s^.next:=g[i].link;

g[i].link:=s;

end;

从图中某一顶点出发，系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作称为图的遍历。为了避免重复地访问某个顶点，可以设置一个标志数组visited[i]，未访问时值为false，访问一次后改为true。

图的遍历分为深度优先遍历和广度优先遍历。

1、深度优先遍历的原则：从图中某个指定的顶点v出发,先访问顶点v,然后从顶点v 未被访问过的一个邻接点出发, 继续进行深度优先遍历,直到图中与v相通的所有顶点都被访问；若

此时图中还有未被访问过的顶点, 则从另一个未被访问过的顶点出发重复上述过程,直到遍历全图。

深度优先遍历的算法;(假设图用邻接表存储)

procedure dfs(i:integer);

var p:edge;

begin

write(g[i].data);

visited[i]:=true;

p:=g[i].link;

while p<>nil do

begin

j:=p^.v;

if not visited[j] then dfs(j);

p:=p^.next;

end;

2、广度优先遍历的原则：从图中某个指定的顶点v出发,先访问顶点v,然后依次访问顶点v的各个未被访问过的邻接点,然后又从这些邻接点出发, 按照同样的规则访问它们的那些未被访问过的邻接点，如此下去，直到图中与v 相通的所有顶点都被访问; 若此时图中还有未被访问过的顶点, 则从另一个未被访问过的顶点出发重复上述过程, 直到遍历全图。

广度优先遍历的算法：

procedure bfs(i:integer);

var p:edge;

begin

f:=0;r:=1; {队列初始化}

write(g[i].data); {访问顶点i}

q[r]:=g[i].data; {顶点i进队列}

visited[i]:=true; {设置访问标记}

while f<r do

begin

f:=f+1; {出队列}

p:=g[q[f]].link; {取邻接顶点指针}

while p<>nil do {存在后继结点}

begin

if not visited[p^.v] then

begin

write(g[p^.v].data);

visited[p^.v]:=true;

r:=r+1; q[r]:=p^.v; {进队列}

end;

p:=p^.next;

end;