para que puedas hacer esto, es necesesario que tu variable $link contenga informacion sobre su categoria. por ejemplo $link.cat
ahi tenes el identificador de la categoria del link, y lo siguiente seria poner una imagen a un lado del <a>, de esta forma...
si $categs esta indexado por id
<img src="{$smarty.const.DOC_ROOT}/images/cat/{$categs.$link.cat}.png">
si el arreglo $categs no esta indexado por los id, para conocer la ubicacion de la imagen vas a tener que recorrer todo $categs.
{foreach from=$categs item=cat name=categs}
{if cat.ID == $link.cat}
<img src="{$smarty.const.DOC_ROOT}/images/cat/{$cat.ID}.png">
{/if}
{/foreach}