1.1图
图是由顶点集合以及顶点间的关系集合组成的一种数据结构。
图通常用来表示和存储具有“多对多”关系的数据，是数据结构中非常重要的一种结构。
遍历：从图中某一顶点出发，并系统地访问完图中的所有顶点，且都恰好访问一次的运算操作
。图是按照无方向和有方向分为无向图和有向图。图的遍历方式分为两种：深度优先遍历与广度优先遍历，二者的时间复杂度都是O(n2)；运用：递归，回溯，方式：从起始点（假设是A）出发，并将点A标记好，然后再去访问与A相连，且未被访问过的顶点。一个中间的顶点（假设是B）在访问完B的所有邻接点后，再退回到B的上一个点（假设是C，即访问时由C到B），去访问C的另一个未被访问的邻接点，继续遍历。在选择邻接点遍历的先后时，一般准则是小序号优先。
1.2代码实现
#include#include #define QUEUE_SIZE 10 int* visitedPtr; typedef struct GraphNodeQueue{ int* nodes; int front; int rear; }GraphNodeQueue, *QueuePtr; //初始化 QueuePtr initQueue(){ QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(struct GraphNodeQueue)); resultQueuePtr->nodes = (int*)malloc(QUEUE_SIZE * sizeof(int)); resultQueuePtr->front = 0; resultQueuePtr->rear = 1; return resultQueuePtr; }//Of initQueue //Is the queue empty? bool isQueueEmpty(QueuePtr paraQueuePtr){ if ((paraQueuePtr->front + 1) % QUEUE_SIZE == paraQueuePtr->rear) { return true; } return false; } //Add a node to the queue. void enqueue(QueuePtr paraQueuePtr, int paraNode){ printf("front = %d, rear = %d.rn", paraQueuePtr->front, paraQueuePtr->rear); if ((paraQueuePtr->rear + 1) % QUEUE_SIZE == paraQueuePtr->front % QUEUE_SIZE) { printf("Error, trying to enqueue %d. queue full.rn", paraNode); return; } paraQueuePtr->nodes[paraQueuePtr->rear] = paraNode; paraQueuePtr->rear = (paraQueuePtr->rear + 1) % QUEUE_SIZE; printf("enqueue %d ends.rn", paraNode); }//Of enqueue //Remove an element from the queue and return. int dequeue(QueuePtr paraQueuePtr){ if (isQueueEmpty(paraQueuePtr)) { printf("Error, empty queuern"); return NULL; } paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE; printf("dequeue %d ends.rn", paraQueuePtr->nodes[paraQueuePtr->front]); return paraQueuePtr->nodes[paraQueuePtr->front]; }//Of dequeue // The structure of a graph. typedef struct Graph{ int** connections; int numNodes; } *GraphPtr; //void deepFirst(GraphPtr paraGraphPtr, int paraNode); GraphPtr initGraph(int paraSize, int** paraData) { int i, j; GraphPtr resultPtr = (GraphPtr)malloc(sizeof(Graph)); resultPtr -> numNodes = paraSize; //resultPtr -> connections = (int**)malloc(paraSize * paraSize * sizeof(int)); resultPtr -> connections = (int**)malloc(paraSize * sizeof(int*)); for (i = 0; i < paraSize; i ++) { resultPtr -> connections[i] = (int*)malloc(paraSize * sizeof(int)); for (j = 0; j < paraSize; j ++) { resultPtr -> connections[i][j] = paraData[i][j]; } } return resultPtr; } //Initialize the tranverse. void initTranverse(GraphPtr paraGraphPtr) { int i; //Initialize data visitedPtr = (int*) malloc(paraGraphPtr -> numNodes * sizeof(int)); for (i = 0; i < paraGraphPtr -> numNodes; i ++) { visitedPtr[i] = 0; }//Of for i }//Of initTranverse void depthFirstTranverse(GraphPtr paraGraphPtr, int paraNode) { int i; visitedPtr[paraNode] = 1; printf("%dt", paraNode); for (i = 0; i < paraGraphPtr -> numNodes; i ++) { if (!visitedPtr[i]) { if (paraGraphPtr -> connections[paraNode][i]) { depthFirstTranverse(paraGraphPtr, i); }//Of if }//Of if }//Of for i }//Of depthFirstTranverse // Width first tranverse. void widthFirstTranverse(GraphPtr paraGraphPtr, int paraStart){ //Use a queue to manage the pointers int i, j, tempNode; i = 0; QueuePtr tempQueuePtr = initQueue(); printf("%dt", paraStart); visitedPtr[paraStart] = 1; enqueue(tempQueuePtr, paraStart); while (!isQueueEmpty(tempQueuePtr)) { tempNode = dequeue(tempQueuePtr); visitedPtr[tempNode] = 1; // output. i ++; for (j = 0; j < paraGraphPtr->numNodes; j ++) { if (visitedPtr[j]) continue; if (paraGraphPtr->connections[tempNode][j] == 0) continue; printf("%dt", j); visitedPtr[j] = 1; enqueue(tempQueuePtr, j); }//Of for j }//Of while }//Of widthFirstTranverse void testGraphTranverse() { int i, j; int myGraph[5][5] = { {0, 1, 0, 1, 0}, {1, 0, 1, 0, 1}, {0, 1, 0, 1, 1}, {1, 0, 1, 0, 0}, {0, 1, 1, 0, 0}}; int** tempPtr; printf("Preparing datarn"); tempPtr = (int**)malloc(5 * sizeof(int*)); for (i = 0; i < 5; i ++) { tempPtr[i] = (int*)malloc(5 * sizeof(int)); }//Of for i for (i = 0; i < 5; i ++) { for (j = 0; j < 5; j ++) { printf("i = %d, j = %d, ", i, j); printf("%drn", tempPtr[i][j]); tempPtr[i][j] = myGraph[i][j]; printf("i = %d, j = %d, %drn", i, j, tempPtr[i][j]); }//Of for j }//Of for i printf("Data readyrn"); GraphPtr tempGraphPtr = initGraph(5, tempPtr); printf("num nodes = %d rn", tempGraphPtr -> numNodes); printf("Graph initializedrn"); printf("Depth first visit:rn"); initTranverse(tempGraphPtr); depthFirstTranverse(tempGraphPtr, 4); printf("rnWidth first visit:rn"); initTranverse(tempGraphPtr); widthFirstTranverse(tempGraphPtr, 4); }//Of testGraphTranverse int main(){ testGraphTranverse(); return 1; }//Of main //深度优先用递归. //广度优先用栈
1.3结果运行
Preparing data i = 0, j = 0, 11364160 i = 0, j = 0, 0 i = 0, j = 1, 0 i = 0, j = 1, 1 i = 0, j = 2, 11338064 i = 0, j = 2, 0 i = 0, j = 3, 0 i = 0, j = 3, 1 i = 0, j = 4, 760237908 i = 0, j = 4, 0 i = 1, j = 0, 11364160 i = 1, j = 0, 1 i = 1, j = 1, 0 i = 1, j = 1, 0 i = 1, j = 2, 11338064 i = 1, j = 2, 1 i = 1, j = 3, 0 i = 1, j = 3, 0 i = 1, j = 4, 842087763 i = 1, j = 4, 1 i = 2, j = 0, 11364160 i = 2, j = 0, 0 i = 2, j = 1, 0 i = 2, j = 1, 1 i = 2, j = 2, 11338064 i = 2, j = 2, 0 i = 2, j = 3, 0 i = 2, j = 3, 1 i = 2, j = 4, 1769096293 i = 2, j = 4, 1 i = 3, j = 0, 11364160 i = 3, j = 0, 1 i = 3, j = 1, 0 i = 3, j = 1, 0 i = 3, j = 2, 11338064 i = 3, j = 2, 1 i = 3, j = 3, 0 i = 3, j = 3, 0 i = 3, j = 4, 1852140636 i = 3, j = 4, 0 i = 4, j = 0, 11364160 i = 4, j = 0, 0 i = 4, j = 1, 0 i = 4, j = 1, 1 i = 4, j = 2, 11338064 i = 4, j = 2, 1 i = 4, j = 3, 0 i = 4, j = 3, 0 i = 4, j = 4, 1030255713 i = 4, j = 4, 0 Data ready num nodes = 5 Graph initialized Depth first visit: 4 1 0 3 2 Width first visit: 4 front = 0, rear = 1. enqueue 4 ends. dequeue 4 ends. 1 front = 1, rear = 2. enqueue 1 ends. 2 front = 1, rear = 3. enqueue 2 ends. dequeue 1 ends. 0 front = 2, rear = 4. enqueue 0 ends. dequeue 2 ends. 3 front = 3, rear = 5. enqueue 3 ends. dequeue 0 ends. dequeue 3 ends. --------------------------------
2.1邻接表
邻接矩阵用两个数组保存数据。一个一维数组存储图中顶点信息，一个二维数组存储图中边或弧的信息。邻接表：数组和链表相结合的存储方法为邻接表。有向图也可以用邻接表，出度表叫邻接表，入度表尾逆邻接表。
2.2代码实现
//将矩阵形式转成了邻接表形式. #include#include #define QUEUE_SIZE 10 int* visitedPtr; typedef struct Graph{ int** connections; int numNodes; } *GraphPtr; GraphPtr initGraph(int paraSize, int** paraData) { int i, j; GraphPtr resultPtr = (GraphPtr)malloc(sizeof(struct Graph)); resultPtr -> numNodes = paraSize; //resultPtr -> connections = (int**)malloc(paraSize * paraSize * sizeof(int)); resultPtr -> connections = (int**)malloc(paraSize * sizeof(int*)); for (i = 0; i < paraSize; i ++) { resultPtr -> connections[i] = (int*)malloc(paraSize * sizeof(int)); for (j = 0; j < paraSize; j ++) { resultPtr -> connections[i][j] = paraData[i][j]; }//Of for j }//Of for i return resultPtr; }//Of initGraph //A queue with a number of indices. typedef struct GraphNodeQueue{ int* nodes; int front; int rear; }GraphNodeQueue, *QueuePtr; QueuePtr initQueue(){ QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(struct GraphNodeQueue)); resultQueuePtr->nodes = (int*)malloc(QUEUE_SIZE * sizeof(int)); resultQueuePtr->front = 0; resultQueuePtr->rear = 1; return resultQueuePtr; }//Of initQueue // Is the queue empty? bool isQueueEmpty(QueuePtr paraQueuePtr){ if ((paraQueuePtr->front + 1) % QUEUE_SIZE == paraQueuePtr->rear) { return true; }//Of if return false; }//Of isQueueEmpty //Add a node to the queue. void enqueue(QueuePtr paraQueuePtr, int paraNode){ if ((paraQueuePtr->rear + 1) % QUEUE_SIZE == paraQueuePtr->front % QUEUE_SIZE) { printf("Error, trying to enqueue %d. queue full.rn", paraNode); return; }//Of if paraQueuePtr->nodes[paraQueuePtr->rear] = paraNode; paraQueuePtr->rear = (paraQueuePtr->rear + 1) % QUEUE_SIZE; }//Of enqueue // Remove an element from the queue and return. int dequeue(QueuePtr paraQueuePtr){ if (isQueueEmpty(paraQueuePtr)) { printf("Error, empty queuern"); return NULL; }//Of if paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE; printf("dequeue %d ends.rn", paraQueuePtr->nodes[paraQueuePtr->front]); return paraQueuePtr->nodes[paraQueuePtr->front]; }//Of dequeue //Aajacent node. typedef struct AdjacencyNode { int column; AdjacencyNode* next; }AdjacencyNode, *AdjacentNodePtr; //Aajacent list. typedef struct AdjacencyList { int numNodes; AdjacencyNode* headers; }AdjacencyList, *AdjacencyListPtr; //Construct an adjacent list. AdjacencyListPtr graphToAdjacentList(GraphPtr paraPtr) { //Allocate space. int i, j, tempNum; AdjacentNodePtr p, q; tempNum = paraPtr->numNodes; AdjacencyListPtr resultPtr = (AdjacencyListPtr)malloc(sizeof(struct AdjacencyList)); resultPtr->numNodes = tempNum; resultPtr->headers = (AdjacencyNode*)malloc(tempNum * sizeof(struct AdjacencyNode)); //Fill the data. for (i = 0; i < tempNum; i ++) { //Initialize headers. p = &(resultPtr->headers[i]); p->column = -1; p->next = NULL; for (j = 0; j < tempNum; j ++) { if (paraPtr->connections[i][j] > 0) { //Create a new node. q = (AdjacentNodePtr)malloc(sizeof(struct AdjacencyNode)); q->column = j; q->next = NULL; //Link. p->next = q; p = q; }//Of if }//Of for j }//Of for i return resultPtr; }//Of graphToAdjacentList //Print an adjacent list. void printAdjacentList(AdjacencyListPtr paraPtr) { int i; AdjacentNodePtr p; int tempNum = paraPtr->numNodes; printf("This is the graph:rn"); for (i = 0; i < tempNum; i ++) { p = paraPtr->headers[i].next; while (p != NULL) { printf("%d, ", p->column); p = p->next; }//Of while printf("rn"); }//Of for i }//Of printAdjacentList //Width first tranverse. void widthFirstTranverse(AdjacencyListPtr paraListPtr, int paraStart){ printf("width first rn"); //Use a queue to manage the pointers int i, j, tempNode; AdjacentNodePtr p; i = 0; //Initialize data visitedPtr = (int*) malloc(paraListPtr->numNodes * sizeof(int)); for (i = 0; i < paraListPtr->numNodes; i ++) { visitedPtr[i] = 0; }//Of for i QueuePtr tempQueuePtr = initQueue(); printf("%dt", paraStart); visitedPtr[paraStart] = 1; enqueue(tempQueuePtr, paraStart); printf("After enqueuern"); while (!isQueueEmpty(tempQueuePtr)) { printf("First whilern"); tempNode = dequeue(tempQueuePtr); for (p = &(paraListPtr->headers[tempNode]); p != NULL; p = p->next) { j = p->column; // printf("j = %d rn", j); if (visitedPtr[j]) continue; printf("%dt", j); visitedPtr[j] = 1; enqueue(tempQueuePtr, j); }//Of for }//Of while printf("rn"); }//Of widthFirstTranverse void testGraphTranverse() { int i, j; int myGraph[5][5] = { {0, 1, 0, 1, 0}, {1, 0, 1, 0, 1}, {0, 1, 0, 1, 1}, {1, 0, 1, 0, 0}, {0, 1, 1, 0, 0}}; int** tempPtr; printf("Preparing datarn"); tempPtr = (int**)malloc(5 * sizeof(int*)); for (i = 0; i < 5; i ++) { tempPtr[i] = (int*)malloc(5 * sizeof(int)); }//Of for i for (i = 0; i < 5; i ++) { for (j = 0; j < 5; j ++) { //printf("i = %d, j = %d, ", i, j); //printf("%drn", tempPtr[i][j]); tempPtr[i][j] = myGraph[i][j]; //printf("i = %d, j = %d, %drn", i, j, tempPtr[i][j]); }//Of for j }//Of for i printf("Data readyrn"); GraphPtr tempGraphPtr = initGraph(5, tempPtr); AdjacencyListPtr tempListPtr = graphToAdjacentList(tempGraphPtr); printAdjacentList(tempListPtr); widthFirstTranverse(tempListPtr, 4); }//Of testGraphTranverse int main(){ testGraphTranverse(); return 1; }//Of main
2.3结果
Preparing data Data ready This is the graph: 1, 3, 0, 2, 4, 1, 3, 4, 0, 2, 1, 2, width first 4 After enqueue First while dequeue 4 ends. 1 2 First while dequeue 1 ends. 0 First while dequeue 2 ends. 3 First while dequeue 0 ends. First while dequeue 3 ends. --------------------------------
