#include <stdio.h>
struct node /* 图顶点结构定义 */
{
int vertex /* 顶点数据信息 */
struct node *nextnode /* 指下一顶点的指标 */
}
typedef struct node *graph /* 图形的结构新型态 */
struct node head[9] /* 图形顶点数组 */
int visited[9] /* 遍历标记数组 */
/********************根据已有的信息建立邻接表********************/
void creategraph(int node[20][2],int num)/*num指的是图的边数*/
{
graph newnode /*指向新节点的指针定义*/
graph ptr
int from /* 边的起点 */
int to /* 边的终点 */
int i
for ( i = 0 i < num i++ ) /* 读取边线信息，插入邻接表*/
{
from = node[i][0] /* 边线的起点 */
to = node[i][1] /* 边线的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node))
newnode->vertex = to /* 建立顶点内容 */
newnode->nextnode = NULL /* 设定指标初值 */
ptr = &(head[from]) /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode /* 下一个顶点 */
ptr->nextnode = newnode /* 插入节点 */
}
}
/********************** 图的深度优先搜寻法********************/
void dfs(int current)
{
graph ptr
visited[current] = 1 /* 记录已遍历过 */
printf("vertex[%d]\n",current) /* 输出遍历顶点值 */
ptr = head[current].nextnode /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /* 如过没遍历过 */
dfs(ptr->vertex) /* 递回遍历呼叫 */
ptr = ptr->nextnode /* 下一个顶点 */
}
}
/****************************** 主程序******************************/
int main()
{
graph ptr
int node[20][2] = { {1, 2}, {2, 1}, /* 边线数组 */
{1, 3}, {3, 1},
{1, 4}, {4, 1},
{2, 5}, {5, 2},
{2, 6}, {6, 2},
{3, 7}, {7, 3},
{4, 7}, {4, 4},
{5, 8}, {8, 5},
{6, 7}, {7, 6},
{7, 8}, {8, 7} }
int i
//clrscr()
for ( i = 1 i <= 8 i++ ) /* 顶点数组初始化 */
{
head[i].vertex = i /* 设定顶点值 */
head[i].nextnode = NULL /* 指针为空 */
visited[i] = 0 /* 设定遍历初始标志 */
}
creategraph(node,20) /* 建立邻接表 */
printf("Content of the gragh's ADlist is:\n")
for ( i = 1 i <= 8 i++ )
{
printf("vertex%d ->",head[i].vertex) /* 顶点值 */
ptr = head[i].nextnode /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex) /* 印出顶点内容 */
ptr = ptr->nextnode /* 下一个顶点 */
}
printf("\n") /* 换行 */
}
printf("\nThe end of the dfs are:\n")
dfs(1) /* 打印输出遍历过程 */
printf("\n") /* 换行 */
puts(" Press any key to quit...")
// getch()
}
#define MaxVerNum 100 /* 最大顶点数为*/typedef enum {False,True} boolean#include "stdio.h"#include "stdlib.h"boolean visited[MaxVerNum]typedef struct node /* 表结点*/{ int adjvex/* 邻接点域,一般是放顶点对应的序号或在表头向量中的下标*/ char Info/*与边(或弧)相关的信息*/ struct node * next /* 指向下一个邻接点的指针域*/} EdgeNode typedef struct vnode /* 顶点结点*/{ char vertex/* 顶点域*/ EdgeNode * firstedge /* 边表头指针*/} VertexNode typedef struct{ VertexNode adjlist[MaxVerNum] /* 邻接表*/ int n,e/* 顶点数和边数*/} ALGraph/* ALGraph是以邻接表方式存储的图类型*///建立一个无向图的邻接表存储的算法如下：void CreateALGraph(ALGraph *G)/* 建立有向图的邻接表存储*/{ int i,j,k int N,E EdgeNode *p printf("请输入顶点数和边数：") scanf("%d %d",&G->n,&G->e) printf("n=%d,e=%d\n\n",G->n,G->e) getchar() for(i=0i<G->ni++) /* 建立有n个顶点的顶点表*/ { printf("请输入第%d个顶点字符信息(共%d个)：",i+1,G->n) scanf("%c",&(G->adjlist[i].vertex)) /* 读入顶点信息*/ getchar() G->adjlist[i].firstedge=NULL /* 顶点的边表头指针设为空*/ } for(k=0k<2*G->ek++) /* 建立边表*/ { printf("请输入边<Vi,Vj>对应的顶点序号(共%d个)：",2*G->e) scanf("%d %d",&i,&j)/* 读入边<Vi,Vj>的顶点对应序号*/ p=(EdgeNode *)malloc(sizeof(EdgeNode))// 生成新边表结点p p->adjvex=j /* 邻接点序号为j */ p->next=G->adjlist[i].firstedge/* 将结点p插入到顶点Vi的链表头部*/ G->adjlist[i].firstedge=p } printf("\n图已成功创建!对应的邻接表如下：\n") for(i=0i<G->ni++) { p=G->adjlist[i].firstedge printf("%c->",G->adjlist[i].vertex) while(p!=NULL) { printf("[ %c ]",G->adjlist[p->adjvex].vertex) p=p->next } printf("\n") } printf("\n")} /*CreateALGraph*/int FirstAdjVertex(ALGraph *g,int v)//找图g中与顶点v相邻的第一个顶点{if(g->adjlist[v].firstedge!=NULL) return (g->adjlist[v].firstedge)->adjvex else return 0}int NextAdjVertex(ALGraph *g ,int vi,int vj )//找图g中与vi相邻的，相对相邻顶点vj的下一个相邻顶点{ EdgeNode *p p=g->adjlist[vi].firstedge while( p!=NULL &&p->adjvex!=vj) p=p->next if(p!=NULL &&p->next!=NULL) return p->next->adjvex else return 0}void DFS(ALGraph *G,int v) /* 从第v个顶点出发深度优先遍历图G */{ int w printf("%c ",G->adjlist[v].vertex) visited[v]=True /* 访问第v个顶点，并把访问标志置True */ for(w=FirstAdjVertex(G,v)ww=NextAdjVertex(G,v,w)) if (!visited[w]) DFS(G,w) /* 对v尚未访问的邻接顶点w递归调用DFS */}void DFStraverse(ALGraph *G)/*深度优先遍历以邻接表表示的图G，而以邻接矩阵表示时，算法完全相同*/{ int i,v for(v=0v<G->nv++) visited[v]=False/*标志向量初始化*///for(i=0i<G->ni++)if(!visited[0]) DFS(G,0)}/*DFS*/void main(){ ALGraph G CreateALGraph(&G) printf("该无向图的深度优先搜索序列为：") DFStraverse(&G) printf("\nSuccess!\n")}
