许多计算应用程序不仅包含项集合，而且包含这些项对之间的连通集合。这些连通关系直接产生大量问题：跟随这些连通 ，能够从一个项到达另一个项吗？从已知项，可以到达其他多少个项？从此项到彼项的最佳路径是哪一条？
我们使用一种称作图（graph）的抽象对象来给这种情形建模。下面给出本文使用的研究图算法的基本ADT接口：
typedef struct{
int v;
int w;
} Edge;
Edge EDGE(int, int);
struct graph{
int V;
int E;
int **adj;
};
typedef struct graph* Graph;
Graph GRAPHinit(int);
void GRAPHinsert(Graph, Edge);
void GRAPHremove(Graph, Edge);
int GRAPHedges(Edge[], Graph G);
Graph GRAPHcopy(Graph);
void GRAPHdestroy(Graph);
void GRAPHshow(Graph G);
Graph GRAPHrand(int, int);
int ** MATRIXint(int, int, int);
接下来是他们的实现：
Edge EDGE(int v, int w)
{
Edge edge;
edge.v = v;
edge.w = w;
return edge;
}
Graph GRAPHinit(int V)
{
Graph G = (Graph)malloc(sizeof *G);
G->V = V;
G->E = 0;
G->adj = MATRIXint(V, V, 0);
return G;
}
void GRAPHinsert(Graph G, Edge e)
{
int v = e.v, w = e.w;
if(G->adj[v][w] == 0)
G->E++;
G->adj[v][w] = 1;
G->adj[w][v] = 1;
}
void GRAPHremove(Graph G, Edge e)
{
int v = e.v, w = e.w;
if(G->adj[v][w] == 1)
G->E--;
G->adj[v][w] = 0;
G->adj[w][v] = 0;
}
/**
* get the edges of the Graph
*/
int GRAPHedges(Edge a[], Graph G)
{
int v, w, E = 0;
for(v = 0; v < G->V; v++)
for(w = v; w < G->V; w++)
if(G->adj[v][w] == 1)
a[E++] = EDGE(v, w);
return E;
}
/**
* create a matrix of integer
* r - row of the matrix
* c - column of the matrix
* val - the value of the matrix
*/
int ** MATRIXint(int r, int c, int val)
{
int i,j;
int **t = (int **)malloc(r * sizeof(int *));
for(i = 0; i<r; i++)
t[i] = (int *)malloc(c*sizeof(int));
for(i = 0; i<r; i++)
for(j = 0; j<c; j++)
t[i][j] = val;
return t;
}
Graph GRAPHcopy(Graph G)
{
int i,j;
Graph g = (Graph)malloc(sizeof *G);
g->V = G->V;
g->E = G->E;
g->adj = MATRIXint(G->V, G->V, 0);
for(i = 0; i<G->V; i++)
for(j = 0; j<G->V; j++)
g->adj[i][j] = G->adj[i][j];
return g;
}
/**
* destroy the graph and free the memory, first free
* the adj, then free the graph
*/
void GRAPHdestroy(Graph G)
{
int i;
for(i = 0; i<G->V; i++)
free(G->adj[i]);
free(G);
}
void GRAPHshow(Graph G)
{
int i,j;
printf("%d vertices, %d edges/n", G->V, G->E);
for(i = 0; i < G->V; i++)
{
printf("%2d: ", i);
for(j = 0; j < G->V; j++)
if(G->adj[i][j] == 1)
printf(" %2d", j);
printf("/n");
}
}
/**
* generate a random graph which has V vertices and E edges
*/
Graph GRAPHrand(int V, int E)
{
// create a graph
Graph g = GRAPHinit(V);
while(g->E < E)
{
Edge e;
e.v = rand() % V;
e.w = rand() % V;
GRAPHinsert(g, e);
}
return g;
}
当然这里面没有涉及到遍历图之类的算法，不过这是基本的东西嘛。然后我们可以编写图形化程序，将图这种抽象结构以图形的方式展现出来。下面先写一个窗口程序，其中g为Graph类型，pt为POINT结构指针，为了在WinMain主函数和WndProc之间传递，将它们声明为全局变量就可以了：
Graph g;
POINT *pt;
LRESULT CALLBACK WndProc(HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam);
/**
* entry of the program
*/
int APIENTRY WinMain(HINSTANCE hInstance,
HINSTANCE hPrevInstance,
LPSTR lpCmdLine,
int nCmdShow)
{
// do some initialize work.
g = GRAPHrand(25, 50);
pt = (POINT *)malloc(sizeof(*pt)*(g->V));
// create window struct.
WNDCLASSEX wndclass;
wndclass.cbClsExtra = 0;
wndclass.cbSize = sizeof(wndclass);
wndclass.cbWndExtra = 0;
wndclass.hbrBackground = (HBRUSH)::GetStockObject(WHITE_BRUSH);
wndclass.hCursor = ::LoadCursor(NULL, IDC_ARROW);
wndclass.hIcon = ::LoadIcon(NULL, IDI_APPLICATION);
wndclass.hIconSm = NULL;
wndclass.hInstance = hInstance;
wndclass.lpfnWndProc = WndProc;
wndclass.lpszClassName = "MainFrame";
wndclass.lpszMenuName = NULL;
wndclass.style = CS_HREDRAW | CS_VREDRAW;
// register class
::RegisterClassEx(&wndclass);
// create window
HWND hwnd = ::CreateWindowEx(0,
"MainFrame",
"My Program",
WS_OVERLAPPEDWINDOW,
CW_USEDEFAULT, // x
CW_USEDEFAULT, // y
CW_USEDEFAULT, // nWidth
CW_USEDEFAULT, // nHeight
NULL,
NULL,
hInstance,
NULL);
if(hwnd == NULL)
{
::MessageBox(NULL, "CreateWindowEx failed", "Error", MB_OK);
return -1;
}
// generate a random graph
RandVertices(g, pt, hwnd);
// show application window
::ShowWindow(hwnd, nCmdShow);
::UpdateWindow(hwnd);
// message loop
MSG msg;
while(::GetMessage(&msg, NULL, 0, 0))
{
::TranslateMessage(&msg);
::DispatchMessage(&msg);
}
return msg.wParam;
}
/**
* Window Precedure
*/
LRESULT CALLBACK WndProc(HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam)
{
switch(message)
{
case WM_PAINT:
{
HDC hdc;
PAINTSTRUCT ps;
hdc = BeginPaint(hwnd, &ps);
// make the vertices filled
SelectObject(ps.hdc, GetStockObject(GRAY_BRUSH));
DrawEdges(g, pt, hwnd, hdc);
DrawVertices(g, pt, hwnd, ps.hdc);
EndPaint(hwnd, &ps);
break;
}
case WM_DESTROY:
::PostQuitMessage(0);
break;
}
return ::DefWindowProc(hwnd, message, wParam, lParam);
}
RandVertices()为每个顶点随即安排一个坐标，这个程序中DrawEdges()，DrawVertices()是我们图抽象数据类型与图形化显示的桥梁。在此我们用它来连接抽象和具体的东西，它的实现如下：
void DrawEdges(Graph g, POINT pt[], HWND hwnd, HDC hdc)
{
int i;
Edge *edge = (Edge *)malloc(sizeof(*edge)*(g->E));
// get the edges
GRAPHedges(edge, g);
// draw the edge
for(i = 0; i < g->E; i++)
{
MoveToEx(hdc, pt[edge[i].v].x, pt[edge[i].v].y, NULL);
LineTo(hdc, pt[edge[i].w].x, pt[edge[i].w].y);
}
free(edge);
}
void DrawVertices(Graph g, POINT pt[], HWND hwnd, HDC hdc)
{
int i;
// draw the vertices of the graph
for(i = 0; i < g->V; i++)
Ellipse(hdc, pt[i].x-3, pt[i].y-3, pt[i].x+3, pt[i].y+3);
}
/**
* set the position of the vertices in the client
* remark - the size of p[] must equal to the number of the vertices in
* graph g
*/
void RandVertices(Graph g, POINT pt[], HWND hwnd)
{
int i;
int cxClient, cyClient;
RECT rt;
::GetClientRect(hwnd, &rt);
// get the width and height of the client
cxClient = rt.right - rt.left;
cyClient = rt.bottom - rt.top;
// randomly set x and y for every vertices
for(i = 0; i < g->V; i++)
{
pt[i].x = abs(rand())%cxClient;
pt[i].y = abs(rand())%cyClient;
}
}
程序很简单，但可以进行大量的扩展，你可以对其修改，让生成的顶点位置由你来安排，选择绘制出定点，搜索图中的回路，寻找一个定点到另一个定点的路径等等，然后在显示到你的界面上，相信会很有意思的，呵呵。
下面是我的一个25个顶点，50条边的随机生成图，相信经过你更好的设计会生成更加复杂的图，如果能图形化解决实际的问题，那么就更能为那些不理解算法的人讲述一个形象的方案了：
