資料結構(8)

第八章 Graphs and Their Applications

8.1 Graphs

A graph consists of a set of nodes(or vertices) and a set of arcs(or edges). Each arc in a graph is specified by a pair of nodes.

Note that a graph need not to be a tree, but that a tree must br a graph.

A node n is incedent to an arc x if n is one of the two nodes in the ordered pair of nodes that constitute x. The degree of a node is the number of arcs incident to it.

The indegree of a node n is the number of arcs that have n as the head, and the outdegree of n is the number of arcs that have n as the tail.

Such a graph, in which a number is associated with each arc, is called a weighted graph or a network. The number associated with an arc is called its weight.

A path from a node to itself is called a cycle.

#define MAXNODES 50

struct node{

/*information associated with each node*/

};

struct arc{

int adj;

/*information associated with each arc*/

};

struct graph{

struct node nodes[MAXNODES];

struct arc arcs[MAXNODES][MAXNODES]

};

struct graph g;

void join(int adj[][MAXNODES], int node1, int node2)

{

/* add an arc from node1 to node2*/

adj[node1][node2]=TRUE;

}

void remv(int adj[][MAXNODES], int node1, int node2)

{

/* delete an arc from node1 to node2*/

adj[node1][node2]=FALSE;

}

int adjacent(int adj[][MAXNODES], int node1, int node2)

{

return ((adj[node1][node2]==TRUE)?TRUE:FALSE);

}

Transitive Closure

Its value is TRUE if and only if the values of both adj[i][k] and adj[k][j] are TRUE, which implies that there is an arc from node I to node k and an arc from node k to node j.

path0[i][j]=adj, since the only way to go from node I to node j without passing through any other nodes is to go directly from I to j.

void transclose(int adj[][MAXNODES], int path[][MAXNODES])

{

int I,j,k;

for(i=0;i<MAXNODES;++i)

for(j=0;j<MAXNODES;++j)

path[i][j]=adj[i][j];

for(k=0;i<MAXNODES;++k)

for(i=0;j<MAXNODES;++i)

if(path[i][k]==TRUE)

for(j=0;j<MAXNODES;++j)

path[i][j]=path[i][j]||path[k][j];

}

Page 527 Shortest-Path Algorithm

Spanning Forests

A forest may be defined as an acyclic graph on which every node has one or no predecessors.