图(Graph)是一种复杂的非线性结构。在人工智能、工程、数学、物理、化学、生物和计算机科学等领域中，图结构有着广泛的应用。
本章先介绍图的概念，再介绍图的存储方法及有关图的算法。
图的二元组定义
图G由两个集合V和E组成，记为：
G=(V，E)
其中：
V是顶点的有穷非空集合，
E是V中顶点偶对(称为边)的有穷集。
通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。
有向图和无向图
1．有向图
若图G中的每条边都是有方向的，则称G为有向图(Digraph)。
（1）有向边的表示
在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head)。
【例】
i，vj>表示一条有向边，vi是边的始点(起点)，vj是边的终点。因此，i，vj>和j，vi>是两条不同的有向边。
（2）有向图的表示
【例】下面(a)图中G1是一个有向图。图中边的方向是用从始点指向终点的箭头表示的，该图的顶点集和边集分别为：
V(G1)={v1，v2，v3}
E(G1)={1，v2>，2，v1>，2，v3>}
2．无向图
若图G中的每条边都是没有方向的，则称G为无向图(Undigraph)。
（1）无向边的表示
无向图中的边均是顶点的无序对，无序对通常用圆括号表示。
【例】无序对(vi，vj)和(vj，vi)表示同一条边。
（2）无向图的表示
【例】下面(b)图中的G2和(c)图中的G3均是无向图，它们的顶点集和边集分别为：
V(G2)={v1，v2，v3，v4}
E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)}
V(G3)={v1，v2，v3，v4，v5，v6，v7}
E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)}
注意：
在以下讨论中，不考虑顶点到其自身的边。即若(v1，v2)或l，v2>是E(G)中的一条边，则要求v1≠v2。此外，不允许一条边在图中重复出现，即只讨论简单的图。
3．图G的顶点数n和边数e的关系
（1）若G是无向图，则0≤e≤n(n-1)/2
恰有n(n-1)/2条边的无向图称无向完全图(Undireet-ed Complete
Graph)
（2）若G是有向图，则0≤e≤n(n-1)。
恰有n(n-1)条边的有向图称为有向完全图(Directed Complete
Graph)。
注意：
完全图具有最多的边数。任意一对顶点间均有边相连。
【例】上面(b)图的G2就是具有4个顶点的无向完全图。
4、图的邻接矩阵表示法
在图的邻接矩阵表示法中：
① 用邻接矩阵表示顶点间的相邻关系
② 用一个顺序表来存储顶点信息
5、图的基本算法的Java实现
包括遍历、最小生成树等。
package zieckey.datastructure.study.graph;
/**
*
* 图中的(节)点。
*
* @author zieckey
*
*/
class Vertex
{
public char label; // label (e.g. 'A')
public boolean wasVisited;
public Vertex( char lab ) // constructor
{
label = lab;
wasVisited = false;
}
} // end class Vertex
|
package zieckey.datastructure.study.graph;
class Graph
{
private final int MAX_VERTS = 20;
private Vertex[] vertexList; // array of vertices
private int[][] adjMat; // adjacency matrix
private int nVerts; // current number of vertices
private StackInt theStack;
private QueueInt theQueue;
/**
* 默认构造函数 初始化邻接矩阵
*/
public Graph( )
{
vertexList = new Vertex[MAX_VERTS];
// 图的邻接矩阵adjacency matrix
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for ( int j = 0; j < MAX_VERTS; j++ )
{
// set adjacency
for ( int k = 0; k < MAX_VERTS; k++ )
{
// matrix to 0
adjMat[j][k] = 0;
}
}
theStack = new StackInt( MAX_VERTS );
theQueue = new QueueInt( MAX_VERTS );
}
/**
* 添加一个节点
*
* @param lab
*/
public void addVertex( char lab ) // argument is label
{
vertexList[nVerts++ ] = new Vertex( lab );
}
/**
* 添加一条边
*
* @param start
* 起始点
* @param end
* 终点
*/
public void addEdge( int start, int end )
{
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
/**
* 添加一条边
*
* @param start
* 起始点
* @param end
* 终点
*/
public void addEdge( char startVertex, char endVertex )
{
int start = getIndexByLabel( startVertex );
int end = getIndexByLabel( endVertex );
if ( -1 != start && -1 != end )
{
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
}
/**
* depth-first search深度优先搜索
*/
public void dfs()
{
theStack.setTop( -1 );// 置空stack
vertexList[0].wasVisited = true; // mark it
displayVertex( 0 ); // display it
theStack.push( 0 ); // push it
int v = 0;
while ( !theStack.isEmpty() )
{
v = getAdjUnvisitedVertex( theStack.peek() );
if ( -1 == v )
{
theStack.pop();
} else
{
vertexList[v].wasVisited = true;
displayVertex( v );
theStack.push( v );
}
}// end while
// 重置标志
for ( int j = 0; j < nVerts; j++ )
{
vertexList[j].wasVisited = false;
}
}
/**
* breadth-first search 广度优先搜索
*/
public void bfs()
{
vertexList[0].wasVisited = true; // mark it
theQueue.insert( 0 );
while ( !theQueue.isEmpty() )
{
int currentVertex = theQueue.remove();
displayVertex( currentVertex );//打印当前访问的节点
int v = -2;
//搜索与当前节点currentVertex相邻的所有节点
while ( -1 != ( v = getAdjUnvisitedVertex( currentVertex ) ) )
{
theQueue.insert( v );
vertexList[v].wasVisited = true; // mark it
}
}
// 重置标志
for ( int j = 0; j < nVerts; j++ )
{
vertexList[j].wasVisited = false;
}
}
/**
* 最小生成树算法。用深度优先搜索算法得到
*/
public void buildMinimumSpanningTree()
{
theStack.setTop( -1 );// 置空stack
vertexList[0].wasVisited = true; // mark it
theStack.push( 0 ); // push it
int v = 0;
while ( !theStack.isEmpty() )
{
int currentVertex = theStack.peek();
v = getAdjUnvisitedVertex( currentVertex );
if ( -1 == v )
{
theStack.pop();
} else
{
vertexList[v].wasVisited = true;
displayVertex( currentVertex );
displayVertex( v );
System.out.print(" ");
theStack.push( v );
}
}// end while
// 重置标志
for ( int j = 0; j < nVerts; j++ )
{
vertexList[j].wasVisited = false;
}
}
/**
* 得到节点 v 的还未被访问的一个节点
*
* @param v
* @return 返回v的还未被访问的一个节点，如果没有找到，返回-1
*/
public int getAdjUnvisitedVertex( int v )
{
for ( int j = 0; j < nVerts; j++ )
{
if ( adjMat[v][j] == 1 && vertexList[j].wasVisited == false )
{
return j; // return first such vertex
}
}
return -1; // no such vertices
} // end getAdjUnvisitedVert()
/**
* 显示一个节点
*
* @param v
*/
public void displayVertex( int v )
{
System.out.print( vertexList[v].label );
}
public int getIndexByLabel( char lable )
{
for ( int i = 0; i < vertexList.length; i++ )
{
if ( lable == vertexList[i].label )
{
return i;
}
}
// 没有这个节点
return -1;
}
}
|
阅读(3707) | 评论(0) | 转发(0) |
